Число размещений без повторений
Теорема: Число размещений без повторений из n элементов по r A_n^r = n(n-1)(n-2)…(n-r+1) = n!/(n-r)!.

Доказательство: В r-размещении (а₁,a₂,…,a_r) n-элементного множества M элемент а₁ можно выбрать n способами. После этого элемент a₂ можно выбрать n-1 способами (из оставшихся n-1 элементов множества M). После этого элемент a₃ можно выбрать n-2 способами. И так далее. Наконец, элемент аr можно выбрать n-г+1 способами. По правилу произведения = n (n-1) (n-2)… (n-r+1);
умножив и разделив правую часть равенства на (n-r)(n-r-1)…3*2*1. Получим A_n^r = n!/(n-r)!.

Следствие: Число перестановок n-элементного множества без повторений Pn = n!.

Число размещений с повторениями
Теорема: Число размещений с повторениями A’_n^r = n^r.

Доказательство: В r-размещении (а₁, a₂,…,a_r) элемент а₁ в n-элементном множестве M можно выбрать n способами, элемент a₂ — тоже n способами, наконец, элемент a_r — n способами. По правилу произведения A’_n^r.

Следствие: Число перестановок с повторениями C_n^r = n!/(r!(n-r)!).

Число сочетаний без повторений
Теорема: Число сочетаний без повторений C_n^r = n!/(r! (n-r)!).

Доказательство: Каждому r-сочетанию (а₁, a₂,…, a_r) n-элементного множества соответствует r! перестановок. Тогда число размещений A’_n^r = C_n^rr! откуда и следует требуемая формула.

Число сочетаний с повторениями
Теорема: Число сочетаний с повторениями C’_n^r = C’_n+1-^r.

Доказательство: Каждому r-сочетанию из n-элементного множества M сопоставим набор (k₁, k₂,…, k_n) из натуральных чисел, указывающих число повторов каждого элемента из M в выбранном сочетании. При этом k₁ +k₂ +…+ k_n = 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 раз. Каждому полученному набору (k₁, k₂, …, k_n) сопоставим набор (l₁, l₂,…,l_n), где l_i = k₁ +1, i = 1,2,…, n. Тогда l₁+l₂+…+l_n = k₁+k₂ +…+k_n +n = r+n. Каждый полученный набор (l₁, l₂, …, l_n) взаимнооднозначно соответствует числу n+r ненулевых слагаемых l₁, l₂,…,l_n. Разделим n+r последовательно записанных звездочек вертикальными разделительными черточками на n непустых частей, состоящих соответственно из l₁, l₂,…,l_n звездочек. Для нашего примера получим следующее разбиение:
* * * | * | * * * * | * | * * *
l₁ =3 l₂ =1 l₃ =4 l₄ =1 l₅=3
k₁ =2 k₂ =0 k₃ =3 k₄ =0 k₅=2

Каждому разбиению числа n+r на n ненулевых слагаемых взаимнооднозначно соответствует распределение n-1 разделителей, которые можно расставить в n+r-1 пробелах между звездочками C_n+r-1^n-1 способами. Следовательно, число сочетаний с повторениями C’_n^r = C_n+r-1.

Число перестановок данной спецификации
Пусть обозначение P_n(k₁, k₂,…,k_r), k₁+k₂+…+k_r = n, имеет следующий смысл. Пусть набор (к,к,ж,ж,ж,с) из шести шаров, из которых два красных, три желтых и один синий. Набор (2,3,1) – называется спецификацией этого набора шаров. Например, перестановка (ж,с,к,ж,к,ж) той же самой спецификации.
Пусть P₆(2,3,1) означает число всех перестановок спецификации (2,3,1). Пусть имеем n элементов, из которых
K₁ элементов вида 1
Все k_i > 0 и ∑k_i = n
K₂ элементов вида 2
……..
K_r элементов вида r
Пусть P_n(k₁,k₂,…k_r) означает все число перестановок спецификации (k₁,k₂,…k_r).

Теорема: P_n(k₁,k₂,…k_r) = n!/ (k₁!k₂!…k_r!)
Доказательство: k₁ элементов вида 1 можно разместить на n местах C_n^k способами. k₂ элементов вида 2 на оставшихся n-k₁ местах можно разместитьC_n-k1^k2 способами. k₃ элементов вида 3 на оставшихся n-k₁-k₂ местах — C_n-k1-k2^k3 способами. И т.д. k_r элементов вида r на оставшихся n-k₁-…- местах — C_n-k1-..-kr-1^kr способами.

По правилу умножения:
P_n(k₁, …, k_r) = n!/k₁!…k_r!

Число размещений данной спецификации
Пусть A^r_n(k₁,…k_n), k₁+…k_n=r, означает множество всех размещений спецификации (k₁,k₂,…,k_n). n-размещение из n различных элементов по r спецификации (k₁,…,k_n) есть набор из r таких элементов, в которых:
K₁ элементов вида 1
Все k_i > 0 и ∑k_i = r
K₂ элементов вида 2
……..
K_n элементов вида n
Пусть k_i1, .., k_ip есть ненулевые числа среди k₁,k₂,…,k_n. Очевидно, что k_i1 + … + k_ip. С учетом 0!=1 число всех перестановок A^r_n(k₁,…,k_n)= P_r(k_i1,…,k_ip) = r!/ (k_i1!*…*k_ip!)= r!/ (k₁!*…*k_n!).
Например, пусть имеет 7 шаров к,о,ж,з,г,с,ф. Тогда 1234567, число шаров n=7.
1 2 3 4 5 6 7
к о ж з г с ф цвета шаров
k₁ k₂ k₃ k₄ k₅ k₆ k₇ число шаров одного цвета.
2 0 3 0 0 1 0

k_i1+k_i2+…+k_ip=2+3+1=6
Тогда A₇⁶ = P₆(k₁, k₃, k₆) = 6!/2!3!1! = 60.

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