множества B A , содержащего элемент n, существует в точности
S(n-b,k-1) разбиений множества А на k блоков, содержащих B в качестве блока. Действительно, каждое такое разбиение однозначно соответствует разбиению множества А\В на k-1 блоков. b- элементное множество B A , содержащее элемент n, можно выбрать С(n-1,b-1) способами. Следовательно
S(n, k)
n−(k −1)
= ∑
b=1
n−(k −1)
= ∑ Cb−−1S(n −b, k −1) =
n 1
b=1
n−1
Cn−−b S(n −b, k −1) = ∑Ci − S(i, k −1).
n 1 n 1 i=k −1
Число Белла
Определение. Число Белла Bn есть число всех разбиений n- элементного множества Bn = Π (A) , где A = n.
Другими словами
n
Bn = ∑
k =0
Теорема
S(n, k).
n
3.3. B + = ∑Ci B .
n 1 n i i=0
Доказательство.
Множество всех разбиений множества A={1,…,n+1} можно разбить на различные классы в зависимости от блока В, содержа-
щего элемент n+1 |
(или в зависимости от множества А\В). Для каж- |
||||||||
дого множества |
A \ B {1,..., n} существует в точности |
||||||||
|
|
Π ( A \ B) |
|
= B |
|
A−B |
|
|
разбиений множества А, содержащих В в каче- |
|
|
||||||||
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
стве блока. Группируя классы в зависимости от мощности множества А\В, получаем требуемую формулу.
B(0)=1
B(1)=1
B(2)=2
B(3)=5
B(4)=15
B(5)=52
B(6)=203
Таблица 3.2. Числа Белла.
12
Числа Стирлинга первого рода
Введем следующее обозначение многочлена
[x]k |
= x(x −1)...(x −k +1) |
|
|
Для частных случаев: |
|
||
[x]0 |
=1, |
. |
|
[x]1 =1, |
|||
|
|||
[x]2 |
= x(x −1), |
|
|
[x]3 |
= x(x −1)(x −2). |
|
|
Определение. Числа Стирлинга первого рода s(n,k) есть коэффициенты при последовательных степенях переменной x в много-
члене [x]k :
n |
|
[x]n = ∑s(n, k)xk . |
|
k =0 |
|
Очевидно, что s(n,k)=0 для k>n. |
|
Теорема 3.4. |
|
s(n, k) = s(n −1, k −1) −(n −1)s(n −1, k) , для 0 < k < n, |
(3.4) |
s(n, n) =1 , для n ≥ 0, |
(3.5) |
s(n,0) = 0 , для n >0. |
(3.6) |
Доказательство.
Формулы (3.5) и (3.6) очевидны. Формулу (3.4) получим, сравнивая коэффициенты при xk в обеих частях равенства
[x]n =[x]n−1 (x −n +1).
Имеем
n |
|
n−1 |
|
|
|
|
|
|
|
∑s(n, k)xk = (x −n =1)∑s(n −1, k)xk = |
|
|
|||||||
k =0 |
|
k =0 |
|
|
|
|
|
|
|
n−1 |
|
|
n−1 |
|
|
|
|||
= ∑s(n −1, k)xk +1 −(n −1)∑s(n, k)xk = |
|
|
|||||||
k =0 |
|
|
k =0 |
|
|
|
|||
n−1 |
|
|
|
|
|
|
|
|
|
∑(s(n −1, k −1) −(n −1)s(n −1, k))xk + |
|
|
|||||||
k =1 |
|
|
|
|
|
|
|
|
|
+ s(n −1, n −1)xn −(n −1)s(n −1,0). |
|
|
|
||||||
|
k |
0 |
1 |
|
2 |
|
3 |
4 |
5 |
|
|
|
|
|
|
|
|
|
|
13
n |
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
2 |
0 |
-1 |
1 |
0 |
0 |
0 |
3 |
0 |
2 |
-3 |
1 |
0 |
0 |
4 |
0 |
-6 |
11 |
-6 |
1 |
0 |
5 |
0 |
24 |
50 |
35 |
-10 |
1 |
Таблица 3.3. Числа Стирлинга первого рода.
Лекция 4. Формулы включений и исключений.
Формулы включений и исключений
Лемма 4.1. Пусть дано N элементов и n свойств p1,…,pn. Пусть Ni1 ...ir - число элементов, обладающих, по крайней мере, свойст-
вами pi1 ,... pir ,r =1,n . Тогда число элементов N0 , не обладающих ни одним из указанных свойств определяется формулой
n |
|
∑Ni1 ...is |
|
N0 = N −∑Ni + ∑Ni1i2 +... +(−1)s |
+... |
||
i=1 |
i1 <i2 |
i1 <i2 <...<is |
(4.1) |
+(−1)n N12...n
Доказательство. Рассмотрим правую часть (4.1). Элемент, не обладающий свойствами p1,…,pn, учитывается только в слагаемом N. Любой элемент A, обладающий ровно r свойствами j1,…,jr учитывается в выражении
∑Ni1...is , s ≤ r, Crs раз.
i1<i2 <...<is
Следовательно, вклад A в правую часть (4.1) равен:
1−Cr1 +Cr2 +... +(−1)s Crs +... +(−1)r Crr = (1−1)r = 0r = 0 .
Пример 4.1. (пояснение к предыдущей формуле)
Рассмотрим множество шаров, которые могут быть окрашены в 4 цвета:
желтый – свойство 1; красный – свойство 2; синий – свойство 3; зеленый – свойство 4.
Пусть некоторый шар окрашен одновременно в желтый, красный и зеленый цвета. Тогда для него N0 = 0. Теперь рассмотрим,
14
какой вклад он дает в правую часть равенства (4.1).
В первом слагаемом он учитывается 1 раз. Во втором слагаемом он учитывается C31 =3 раза (т.к. N1 = 1, N2 = 1, N4 = 1). В
третьем слагаемом он учитывается C32 =3 раза (т.к. N12 = 1, N14 = 1, N24 = 1). В четвертом слагаемом он учитывается C33 =1 раз (т.к.
N124=1). В пятом (последнем для рассматриваемого примера) сла-
гаемом он учитывается 0 раз (т.к. N1234 = 0).
Таким образом, вклад рассматриваемого шара в правую часть равенства (4.1) равен 1 – 3 + 3 – 1 + 0 = 0.
Замечание. Формула (4.1) называется формулой включений и исключений.
Пример 4.2. (задача о беспорядках).
Определить количество перестановок a1,…,an, чисел 1,…,n та-
ких, что ai ≠ i,i =1,n .
Решение. Число всех перестановок N=n!
Свойство si : ai = i,i = 1, n .
Ni1 ,...,ir - число перестановок, оставляющих на месте по крайней мере числа i1,...,ir , следовательно, Ni1 ,...,ir = (n − r)!
В ∑Ni1 ,...,ir имеется Cnr слагаемых – количество способов
i1 <...<ir
выбора чисел i1,…,ir из 1,…,n. Итак, на основании (4.1):
N0 = n!−Cn1 (n −1)!+Cn2 (n − 2)!+... + (−1)r Cnr (n − r)!+...
+(−1)n Cnn 0! = n!(1−1+ |
1 |
+... + (−1)r |
1 |
|
+... + (−1)n |
1 |
) = |
||
|
r! |
|
|||||||
|
2! |
|
n! |
||||||
n |
1 |
|
|
|
|
|
|
|
|
= n!∑(−1)r |
|
|
|
|
|
|
|
|
|
r! |
|
|
|
|
|
||||
r =2 |
|
|
|
|
|
||||
Лемма 4.2 (вспомогательная) |
|
|
|
|
|
||||
n |
|
|
|
|
|
|
|
|
|
∑(−1)k −r CnkCkr = 0, n, r N, n ≥ r |
|
|
|
(4.2) |
|||||
k =r |
|
|
|
|
|
|
|
|
|
Доказательство. Рассмотрим тождество |
|
|
|||||||
n |
|
|
|
|
|
|
|
|
|
(1 + x)n = ∑Cnk xk |
|
|
|
(4.3) |
|||||
k =0
15
Дифференцируя (4.3) r раз по x, получим
|
|
|
|
|
n |
|
|
n(n −1)...(n − r +1)(1 + x)n−r = ∑Cnk k(k −1)...(k − r +1)xk −r . |
|||||||
|
|
|
|
|
k =r |
|
|
Последнее равенство преобразуется к виду |
|||||||
|
n! |
|
n |
|
k! |
|
|
|
(1+ x)n−r = ∑Cnk |
|
xk −r . |
||||
|
(n −r)! |
|
(k −r)! |
||||
|
k =r |
|
|
||||
Разделив обе части на r! приходим к соотношению |
|||||||
|
|
|
n |
|
|
|
|
Cnr (1 + x)n−r = ∑Cnk Ckr xk |
−r , |
|
|||||
|
|
|
k =r |
|
|
|
|
которое при x = −1 дает |
|
||||||
|
n |
|
|
|
|
|
|
∑(−1)k −r Cnk Ckr = 0 . |
|
|
|
|
|||
|
k =r |
|
|
|
|
|
|
Лемма 4.3. Пусть дано N элементов и n свойств s1,…,sn. Пусть Ni1...ir - число элементов, обладающих по крайней мере свойствами
i1,…,ir, r =1, n . Тогда число элементов N(r), обладающих ровно r свойствами определяются формулой
N (r) = ∑ Ni1 ...ir + |
+ (−1)s−r Csr |
∑ |
Ni1 ...is + |
1≤i1 <...<is ≤n |
1≤i1 |
<...<is ≤n |
(4.4) |
|
n |
|
|
+ (−1)n−r Cnr N12...n = ∑(−1)n−s Csr |
∑ |
Ni1 ...is . |
|
|
s=r |
1≤i1 <...<is ≤n |
|
Доказательство. В левой части (4.4) элемент с ровно r свойствами учитываются один раз. В правой части (4.4) элемент с ровно r свойствами учитываются один раз в первом слагаемом и не учитываются далее. Элемент с ровно t свойствами, t>r, учитывается
(−1)s−r CsrCts раз в слагаемом (−1)s−r Csr ∑ Ni1 ...is .
1≤i1 <...<is ≤n
Поэтому вклад от элементов с ровно t свойствами, t>r, состав-
t
ляет∑(−1)s−r Csr Cts . В силу леммы 4.2 эта сумма равна нулю.
s=r
Пример 4.3 (задача о встречах). Определить количество перестановок a1,…,an чисел 1,…,n , для которых ai=i ровно в r местах.
16