Реферат Курсовая Конспект
Правило произведения - раздел Образование, Правила суммы и произведения в комбинаторике Правило Произведения: Если Элемент A Можно Выбрат...
|
Правило произведения: если элемент A можно выбрать n различными способами и независимо от него элемент B можно выбрать m различными способами, то все различные комбинации элементов «A и B» можно выбрать n*m способами.
Пример: На первой полке стоит 10 книг, а на второй 5. Сколькими способами можно взять книги с обеих полок?
Решение: |X|=10, |Y|=5. По правилу произведения: |X|*|Y|=10*5=50.
Ответ: 50 способами.
Правила суммы и произведения естественным образом обобщаются и на случай комбинаций многих элементов, а именно, если первый элемент совокупности из k различных элементов можно выбрать n1 способами, второй — n2 способами и так далее, k-й элемент — nk способами, то всевозможных комбинаций соответственно n1+n2+...+nk и n1*n2*...*nk.
Число размещений без повторений
Теорема: Число размещений без повторений из n элементов по r Anr = n(n-1)(n-2)…(n-r+1) = n!/(n-r)!.
Доказательство: В r-размещении (а1,a2,…,ar) n-элементного множества M элемент а1 можно выбрать n способами. После этого элемент a2 можно выбрать n-1 способами (из оставшихся n-1 элементов множества M). После этого элемент a3 можно выбрать n-2 способами. И так далее. Наконец, элемент аr можно выбрать n-г+1 способами. По правилу произведения = n (n-1) (n-2)… (n-r+1);
умножив и разделив правую часть равенства на (n-r)(n-r-1)…3*2*1. Получим Anr = n!/(n-r)!.
Следствие: Число перестановок n-элементного множества без повторений Pn = n!.
Число размещений с повторениями
Теорема: Число размещений с повторениями A’nr = nr.
Доказательство: В r-размещении (а1, a2,…,ar) элемент а1 в n-элементном множестве M можно выбрать n способами, элемент a2 – тоже n способами, наконец, элемент ar – n способами. По правилу произведения A’nr.
Следствие: Число перестановок с повторениями Cnr = n!/(r!(n-r)!).
Число сочетаний без повторений
Теорема: Число сочетаний без повторений Cnr = n!/(r! (n-r)!).
Доказательство: Каждому r-сочетанию (а1, a2,…, ar) n-элементного множества соответствует r! перестановок. Тогда число размещений A’nr = Cnrr! откуда и следует требуемая формула.
Число сочетаний с повторениями
Теорема: Число сочетаний с повторениями C’nr = C’n+1-r.
Доказательство: Каждому r-сочетанию из n-элементного множества M сопоставим набор (k1, k2,…, kn) из натуральных чисел, указывающих число повторов каждого элемента из M в выбранном сочетании. При этом k1 +k2 +…+ kn = r. Например, если M = {a,b,c,d,e}, то сочетанию (a,a,c,c,c,e,e) сопоставим набор (2,0,3,0,2), то есть элементы a,b,c,d,e множества M встречаются в сочетании (а,а,с,с,с,е,е) соответственно 2,0,3,0,2 раз. Каждому полученному набору (k1, k2, …, kn) сопоставим набор (l1, l2,…,ln), где li = k1 +1, i = 1,2,…, n. Тогда l1+l2+…+ln = k1+k2 +…+kn +n = r+n. Каждый полученный набор (l1, l2, …, ln) взаимнооднозначно соответствует числу n+r ненулевых слагаемых l1, l2,…,ln. Разделим n+r последовательно записанных звездочек вертикальными разделительными черточками на n непустых частей, состоящих соответственно из l1, l2,…,ln звездочек. Для нашего примера получим следующее разбиение:
* * * | * | * * * * | * | * * *
l1 =3 l2 =1 l3 =4 l4 =1 l5=3
k1 =2 k2 =0 k3 =3 k4 =0 k5=2
Каждому разбиению числа n+r на n ненулевых слагаемых взаимнооднозначно соответствует распределение n-1 разделителей, которые можно расставить в n+r-1 пробелах между звездочками Cn+r-1n-1 способами. Следовательно, число сочетаний с повторениями C’nr = Cn+r-1.
Перестановка без повторении
Задача. Из цифр 1, 2, 3, 4, 5 составлены всевозможные пятизначные числа без повторения цифр. Сколько среди этих чисел таких, которые начинаются цифрой 3?
РЕШЕНИЕ
1) Поставим цифру 3 на первое место и зафиксируем ее. А остальные четыре цифры будем переставлять для получения различных чисел. Таким образом, количество чисел будет определяться количеством перестановок среди чисел 1, 2, 4, 5. Чтобы его найти, воспользуемся формулой комбинаторики:
N = n! ,
де N – количество вариантов перестановок,
n – количество цифр.
N = 4! = 24
ОТВЕТ: Из цифр 1, 2, 3, 4, 5 можно составить 24 пятизначных числа без повторения цифр, которые начинаются цифрой 3?
задача на формулу сочетаний |
Задача. Расписание одного дня содержит 5 уроков. Определить количество таких расписаний при выборе из 11 дисциплин. РЕШЕНИЕ Количество различных расписаний можно определить с помощью формулы комбинаторики для размещения по 5 из 11 элементов. Выбор размещения определяется тем, что при построении расписания необходимо учитывать порядок следования уроков. ОТВЕТ: При данных условиях можно составить 55440 различных расписаний |
– Конец работы –
Эта тема принадлежит разделу:
Перейти к навигация поиск... Все разнообразие комбинаторных формул может быть выведено из двух основных... Содержание Количество размещений Размещение с повторениями Количество размещений с...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Правило произведения
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов