2014-02-02
1415
Напомним определение и основную формулу числа сочетаний:
– это число способов выбрать m различных (т.е. без повторений) предметов из n различных (0<= m <= n), без учета порядка выбора.
Они могут быть вычислены по следующим формулам:
Сnm=Anm/m!
Cnm=(n*(n-1)*(n-2)*...*(n-m+1))/m!
Cnm=n!/(m!*(n-m)!)
Из формул видно, что:
Cn0=1, Cn1=n,
Cn2=n*(n-1)/2=(n2-n)/2,
Cn3=n*(n-1)*(n-2)/6... Cnn-1=n, Cnn=1.
Свойство 1. Cnm=Cnn-m (при всех n>=0 и всех m от 0 до n; обычно говорят кратко – "при всех n и m").
Доказательство: Их у этого свойства будет два: первое – из формулы, второе – комбинаторное рассуждение.
1.) – из формулы:
Cnm=n!/(m!*(n-m)!),
а Cnn-m=n!/((n-m)!*(n-(n-m))!)=n!/((n-m)!*m!) – то же самое, что и Cnm, ч.т.д.
2.) – комбинаторное рассуждение:
Когда мы выбираем m предметов из n, то n-m предметов мы оставляем. Если мы, наоборот, выбранные m предметов оставим, а оставленные n-m – выберем, то получим способ выбора n-m предметов из n. Заметим, что мы получили взаимно-однозначное соответствие способов выбора m и n-m предметов из n. Значит, тех и других способов поровну. Но одних Cnm, а других а Cnn-m, поэтому они равны, ч.т.д.
|
|
|
Свойство 2. Cn+1m+1=Cnm+Cnm+1, "при всех n и m".
Доказательство: Их опять будет два, различных по тому же принципу.
1.) Cnm=n!/(m!*(n-m)!), Cnm+1=n!/((m+1)!*(n-m-1)!),
а Cn+1m+1=(n+1)!/((m+1)!*(n-m)!).
Теперь приведем первые два равенства к общему знаменателю и сложим:
Cnm + Cnm+1 = n!*(m+1)/((m+1)!*(n-m)!)+n!*(n-m)/((m+1)!*(n-m)!) = n!*(m+1+n-m)/((m+1)!*(n-m)!) = (n+1)!/((m+1)!*(n-m)!) = Cn+1m+1, ч.т.д.
2.) Cn+1m+1 – это количество способов выбрать m+1 предметов из n+1. Посчитаем его, зафиксировав один предмет (назовем его "крапленым"). Если мы не берем крапленый предмет, то нам надо выбрать m+1 предмет из n оставшихся, а если мы его берем, то надо выбрать из n оставшихся еще m предметов. Первое можно сделать Cnm+1 способами, второе – Cnm способами. Всего как раз Cnm + Cnm+1, ч.т.д.
