7. В чем отличие сочетаний с повторениями от остальных конфигураций?
8. Пусть в киоске есть три вида открыток. Сколькими способами можно купить 6 открыток? А три открытки? Какая конфигурация используется?
2.3 Биномиальные коэффициенты
Число сочетаний C(n,k)=
– число различных k-элементных подмножеств n-элементного множества – встречается в формулах решения многих комбинаторных задач. Например, для определения числа подмножеств n-элементного множества, удовлетворяющих некоторому условию, задача разбивается на составные части: рассматриваются отдельно 1-элементные подмножества, 2-элементные и т. д., затем результаты складываются.
Числа =
называются биномиальными коэффициентами.
§ Свойства биномиальных коэффициентов
Теорема 2.4 Число 
обладает следующими свойствами:
1. 
; 2. 
; 3. 
Доказательство.
1. 
º
=
=
º
2. 
= 
= 
= 
= 
= =
= 
= 
.
3.
×
= 
= 
= 
=
= 
. <
Теорема 2.5 (Бином Ньютона) При любых x, y Î R (x+y)n = 
.
Доказательство: По индукции.
База: n =1: (x+y)1 = x+y = 1×x1y0+1×x0y1=
x1y0+ 
x0y1= 
.
Индукционный переход:
(x+y)n=(x+y)n–1(x+y) = x×
+ y×=
x1yn–1+
x2yn–2+ …+
xn–1y1+
xny0+x0yn +x1yn–1+
x2yn–2 + …+xn–1y1= (
+
)·x1yn–1+ (+
)·x2yn–2+…+(
+
)·xn–1y1+ (
xny0+ 
)·x0yn = |=
; =
| =
x1yn–1+
x2yn–2 +…+
xn–1y1+
xny0+ 
x0yn = .
Следствие 1. 2n = 
.
Действительно, 2n = (1+1)n = 
.<
Следствие 2. 
.
Действительно, 0= (–1+1)n = 
.<
Теорема 2.6
1. 
; 2. 
(Тождество Коши).
Доказательство:
1. 
0·
+1·
+2·
+…+(n–1)·
+n·
=(0+n)·+(1+n–1)·+
(2+n–2)· +…= n/2·
.
2. 
– это число способов выбрать k предметов из m+n предметов. Их можно выбирать в два приема: сначала выбрать i предметов из первых n предметов, а затем недостающие k–i предметов – из оставшихся m предметов. Отсюда общее число способов выбрать k предметов составляет 
.<
§ Треугольник Паскаля
Из второй формулы теоремы 2.4 следует удобный способ рекуррентного вычисления значений биномиальных коэффициентов, который можно представить в графической форме, известной как треугольник Паскаля.
C(5,2) | 1 | 0 | ||||||||||||
1 | 1 | 1 | ||||||||||||
1 | 2 | 1 | 2 | |||||||||||
1 | 3 | 3 | 1 | 3 | ||||||||||
1 | 4 | 6 | 4 | 1 | 4 | |||||||||
1 | 5 | 10 | 10 | 5 | 1 | 5 | ||||||||
… | … | … | … | … | … | … |
§ Контрольные вопросы
1. Запишите в виде многочлена (a+b)4, используя формулу бинома Ньютона.
2. Найдите значение выражения C(4,2)+C(4,0)+C(4,3)+C(4,1)+C(4,4).
3. Используя треугольник Паскаля, вычислите C(7,3). Проверьте полученное значение по формуле для числа сочетаний.
4. Найти n, если в разложении (1+x)n коэффициенты при x5 и x12 одинаковы.
2.4 Обобщенные перестановки и разбиения
§ Перестановки с повторениями
Пусть совокупность элементов X содержит n объектов k различных типов, причем имеется n1 неразличимых объектов типа 1, n2 неразличимых объектов типа 2, …, ni неразличимых объектов типа i. Обозначим количество различных размещений элементов множества X через P(n; n1, n2, …, nk). Тогда такие размещения называются перестановками с повторениями и их количество вычисляется по формуле
(2.3)
Пример 2.18 Сколько разных слов можно образовать при перестановке букв слова «математика»? Здесь типы объектов – это различные буквы (число типов k=6), количество неразличимых объектов каждого из типов – это число повторений конкретной буквы. Если бы все буквы были различны, то таких слов = 10!. Количество перестановок, в которых меняются местами только k одинаковых букв, равно k! Очевидно, что такие перестановки не меняют полученного слова Þ при подсчете нужно разделить 10! на k!, и выполнить это для всех повторяющихся элементов. В слове «математика» буква «м» встречается 2 раза, «а» – 3 раза, «т» – 2 раза, «е» – 1 раз, «и» – 1 раз, «к» – 1 раз. Поэтому число различных слов равно 
.
Аналогичную формулу можно получить при подсчете вариантов разбиений.
§ Разбиения и числа Стирлинга
Пусть B = {B1,…,Bk} есть разбиение множества X из n элементов на k подмножеств: "i Bi Ì X, ÈBi = X, Bi ¹ Æ, Bi Ç Bj = Æ "i¹j. |Bi | = ni,
n1+…+nk = n. Тогда набор (B1,…,Bk) называется упорядоченным разбиением множества X, а подмножества Bi называются блоками разбиения.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 |
