Подсчет числа размещений, перестановок, сочетаний без повторов и с повторами


Число размещений без повторений
Теорема: Число размещений без повторений из 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.

Число перестановок данной спецификации
Пусть обозначение Pn(k1, k2,…,kr), k1+k2+…+kr = n, имеет следующий смысл. Пусть набор (к,к,ж,ж,ж,с) из шести шаров, из которых два красных, три желтых и один синий. Набор (2,3,1) – называется спецификацией этого набора шаров. Например, перестановка (ж,с,к,ж,к,ж) той же самой спецификации.
Пусть P6(2,3,1) означает число всех перестановок спецификации (2,3,1). Пусть имеем n элементов, из которых
K1 элементов вида 1
Все ki > 0 и ∑ki = n
K2 элементов вида 2
……..
Kr элементов вида r
Пусть Pn(k1,k2,…kr) означает все число перестановок спецификации (k1,k2,…kr).

Теорема: Pn(k1,k2,…kr) = n!/ (k1!k2!…kr!)
Доказательство: k1 элементов вида 1 можно разместить на n местах Cnk способами. k2 элементов вида 2 на оставшихся n-k1 местах можно разместитьCn-k1k2 способами. k3 элементов вида 3 на оставшихся n-k1-k2 местах — Cn-k1-k2k3 способами. И т.д. kr элементов вида r на оставшихся n-k1-…- местах — Cn-k1-..-kr-1kr способами.

По правилу умножения:
Pn(k1, …, kr) = n!/k1!…kr!

Число размещений данной спецификации
Пусть Arn(k1,…kn), k1+…kn=r, означает множество всех размещений спецификации (k1,k2,…,kn). n-размещение из n различных элементов по r спецификации (k1,…,kn) есть набор из r таких элементов, в которых:
K1 элементов вида 1
Все ki > 0 и ∑ki = r
K2 элементов вида 2
……..
Kn элементов вида n
Пусть ki1, .., kip есть ненулевые числа среди k1,k2,…,kn. Очевидно, что ki1 + … + kip. С учетом 0!=1 число всех перестановок Arn(k1,…,kn)= Pr(ki1,…,kip) = r!/ (ki1!*…*kip!)= r!/ (k1!*…*kn!).
Например, пусть имеет 7 шаров к,о,ж,з,г,с,ф. Тогда 1234567, число шаров n=7.
1 2 3 4 5 6 7
к о ж з г с ф цвета шаров
k1 k2 k3 k4 k5 k6 k7 число шаров одного цвета.
2 0 3 0 0 1 0

ki1+ki2+…+kip=2+3+1=6
Тогда A76 = P6(k1, k3, k6) = 6!/2!3!1! = 60.


Комментарии запрещены.




Статистика