Числа 
=
называются биномиальными коэффициентами.
- Свойства биномиальных коэффициентов
обладает следующими свойствами: 
; 2. 
; 3. 
Доказательство.
1. 
≡
=
=
≡
2. 
= 
= 
= 
= 
= =
= 
= 
.
3.
⋅
= 
= 
= 
=
= 
. <
. Доказательство: По индукции.
База: 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 = 
.<
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(n, k) находится в (n+1) ряду на (k+1) месте. 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 |
… | … | … | … | … | … | … |
- Контрольные вопросы
- Перестановки с повторениями
Пусть совокупность элементов X содержит n объектов k различных типов, причем имеется n1 неразличимых объектов типа 1, n2 неразличимых объектов типа 2, …, ni неразличимых объектов типа i. Обозначим количество различных размещений элементов множества X через P(n; n1, n2, …, nk). Тогда такие размещения называются перестановками с повторениями и их количество вычисляется по формуле
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 |
