Бином Ньютона
Числа сочетаний Cnr присутствуют в известной формуле бино-
ма Ньютона, откуда они получили название биномиальных коэффициентов.
n |
|
Теорема 2.4. (x + y)n = ∑Cnr xr yn−r . |
(2.1) |
r =0
Доказательство. По индукции. База индукции: проверим при n =1
1
(x + y)1 =1 x1 y0 +1 x0 y1 = C10 x1 y0 +C11x0 y1 = ∑C1r xr y1−r .
r =0
(2.1) – верна.
Индуктивное предположение. Предположим, что формула (2.1) верна для n = k −1 :
k −1
(x + y)k −1 = ∑Cr− xr yk −r −1.
k 1
r=0
Шаг индукции. Необходимо доказать, что формула верна для n = k .
7
|
k −1 |
|
(x + y)k = (x + y)(x + y)k −1 = (x + y)∑Ckr−1 xr yk |
−r −1 = |
|
|
r =0 |
|
k −1 |
k −1 |
|
= ∑xCkr−1 xr yk −r −1 + |
∑yCkr−1 xr yk −r−1 = |
|
r=0 |
r =0 |
|
k −1 |
k −1 |
|
= ∑Ckr−1 xr +1 yk −r −1 + |
∑Ckr−1 xr yk −r ={распишем суммы} = |
|
r=0 |
r =0 |
|
= Ck0−1 x1 yk −1 +Ck1−1 x2 yk −2 +... +Ckk−−12 xk −1 y1 +Ckk−−11 xk y0 + |
||
+Ck0−1 x0 yk |
+Ck1−1 x1 yk −1 +... +Ckk−−12 xk −2 y2 +Ckk−−11 xk −1 y1 = |
|
={приведем подобные}= |
||
=x1 yk −1 (Ck0−1 +Ck1−1 ) + x2 yk −2 (Ck1−1 +Ck2−1 ) +... + |
||
+xk −2 y2 (Ckk−−13 +Ckk−−12 ) + xk −1 y1 (Ckk−−12 +Ckk−−11 ) + |
||
+Ckk−−11 xk y0 |
+Ck0−1 x0 yk |
={по свойству Ckr−−11 +Ckr−1 = Сkr } = |
= x1 yk −1Ck1 |
+ x1 yk −1Ck2 |
+... + xk −2 y2Ckk −2 + xk −1 y1Ckk −1 +Cnn xk y0 + |
k |
|
+Cn0 x0 yk = ∑Ckr (n, r)xr yk |
−r . Теорема доказана. |
r =0 |
|
n |
|
Следствие 1. ∑Cnr = 2n . |
|
r =0 |
|
Доказательство. Пусть x =1, y =1. |
|
n |
n |
2n = (1+1)n = ∑Cnr 1r 1n−r = ∑Cnr . |
|
r =0 |
r =0 |
n |
|
Следствие 2. ∑(−1)r Cnr |
= 0 . |
r =0 |
|
Доказательство. Пусть x = −1, y =1. |
|
n |
n |
0 = (−1+1)n = ∑Cnr (−1)r1n−r = ∑(−1)r Cnr . |
|
r=0 |
r =0 |
Биномиальные коэффициенты обладают рядом интересных
8
свойств, некоторые из которых сформулированы в следующих теоремах.
n
Теорема 2.5. ∑rCnr = n2n−1.
r =0
Доказательство.
Рассмотрим следующую последовательность из чисел 1,…,n. Сначала все подмножества длины 0, потом все подмножества дли-
ны 1 и т.д. Имеется Cnr подмножеств мощности n, и каждое из них
имеет длину n. Таким образом, всего в этой последовательности
n
∑rCnr чисел. С другой стороны, каждое число x входит в эту по-
r =0
следовательность 2 {1,...,n}\{x} = 2n−1 раз, а всего чисел n.
k
Теорема 2.6. Cnk+r = ∑Cni Crk −i . i=0
Доказательство.
Cnk+r – это число способов выбрать k предметов из n+r предме-
тов. Предметы можно выбирать в два приема: сначала выбрать i предметов из первых n предметов, а затем выбрать остальные k-i предметов из оставшихся r предметов.
Треугольник Паскаля
Из теоремы 2.2 следует способ вычисления биномиальных коэффициентов, известный как треугольник Паскаля.
|
|
|
1 |
|
|
|
|
1 |
1 |
|
|
|
|
1 |
2 |
1 |
|
|
1 |
3 |
3 |
1 |
|
|
1 |
4 |
6 |
4 |
1 |
|
|
|
|
|
|
Рисунок 3. Треугольник Паскаля.
В этом треугольнике каждое число (кроме единиц на боковых сторонах) является суммой двух чисел, стоящих над ним. Число
сочетаний Cnr находится в (n+1)-м ряду на (r+1)-м месте.
9
Лекция 3.Разбиения множества. Числа Стирлинга второго рода. Число Белла. Числа Стирлинга первого рода.
Разбиения множества
Под разбиением n-элементного множества А на k блоков будем
понимать |
произвольное |
семейство |
π ={B1 ,..., Bk } , такое |
что |
B1 ... Bk = A , Bi ∩B j O/ для |
1 ≤ i < j ≤ k и Bi ≠ O/ |
для |
||
1 ≤i ≤ k . |
Подмножества |
B1 ,..., Bk |
будем называть блоками се- |
|
мейства π . Множество всех разбиений множества А на k блоков будем обозначать Π k (A) , а множество всех разбиений через
Π ( A) .
Числа Стирлинга второго рода
Определение. Число Стирлинга второго рода S(n,k) есть число разбиений n-элементного множества на k блоков:
S(n,k) = Π k ( A) , где A = n.
Пример 3.1. S(4,2)=7, так как множество {1,2,3,4} можно разбить на 2 блока семью различными способами:
{{1,2,3},{4}}
{{1,2,4},{3}}
{{1,3,4},{2}}
{{1,2},{3,4}}
{{1,3},{2,4}}
{{1,4},{2,3}}
{{1},{2,3,4}}
Очевидно, что S(n,k)=0 для k>n. Положим также S(0,0)=1, т.к. по определению пустое семейство блоков является разбиением пустого множества.
Докажем теперь тождество, аналогичное тождеству, связанному с треугольником Паскаля.
Теорема 3.1.
S(n, k) = S(n −1, k −1) + kS(n −1, k) для 0 < k ≤ n, |
(3.1) |
S(n, n) = 1 для n ≥ 0, |
(3.2) |
S(n,0) = 0 для n >0, |
(3.3) |
Доказательство.
Формулы (3.2) и (3.3) очевидны. Докажем (3.1). Рассмотрим множество всех разбиений множества {1,…,n} на k блоков. Оно
10
распадается на два различных класса: множество тех разбиений, которые содержат одноэлементный блок {n}, и тех разбиений, для которых n является элементом большего (по крайней мере, двухэлементного) блока. Мощность первого класса равна S(n-1,k-1), т.е. равна числу разбиений множества {1,…,n-1} на k-1 блоков. Мощность второго класса составляет kS(n-1,k), т.к. каждому разбиению множества {1,…,n-1} на k блоков соответствует в этом классе в точности k разбиений, образованных добавлением элемента n поочередно к каждому блоку.
Теорема (3.1) позволяет легко вычислять S(n,k) даже для больших значений n и k. В следующей таблице представлены числа
S(n,k) для 0 ≤ n, k ≤ 8 . |
|
|
|
|
|
|
|
|||||
|
k |
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
|
|
|||||||||||
|
n |
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
|
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
||
2 |
|
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
||
3 |
|
0 |
1 |
3 |
1 |
0 |
0 |
0 |
0 |
0 |
||
4 |
|
0 |
1 |
7 |
6 |
1 |
0 |
0 |
0 |
0 |
||
5 |
|
0 |
1 |
15 |
25 |
10 |
1 |
0 |
0 |
0 |
||
6 |
|
0 |
1 |
31 |
90 |
65 |
15 |
1 |
0 |
0 |
||
7 |
|
0 |
1 |
63 |
301 |
350 |
140 |
21 |
1 |
0 |
||
8 |
|
0 |
1 |
127 |
966 |
1701 |
1050 |
266 |
28 |
1 |
||
Таблица 3.1. Числа Стирлинга второго рода. Данную таблицу можно трактовать как «треугольник Стирлин-
га», в котором каждое значение кроме крайних, равных единице, можно получить как сумму числа, расположенного над ним и умноженного на k, и числа над ним с левой стороны.
n−1
Теорема 3.2. S(n, k) = ∑ Cnk S(i, k −1), k ≥ 2.
i=k −1
Доказательство.
Рассмотрим множество всех разбиений множества А={1,…,n}. Это множество распадается на различные классы, соответствующие разным подмножествам множества А, которые являются блоками, содержащими элемент n. Для каждого b-элементного под-
11