Числа Стирлинга второго рода

Определение: Число Стирлинга второго рода S(n,k) есть число разбиений n -элементного множества на k блоков: S(n,k)= |П_k(A)| Где |A|=n.

Пример: S(4,2)=7 т.к. множество {1,2,3,4} Можно разбить на 2 блока семью способами.

1. {{1,2,3},{4}}

2. {{1,2,4},{3}}

3. {{1,3,4},{2}}

4. {{1,2},{3,4}}

5. {{1,3},{2,4}}

6. {{1,4},{2,3}}

7. {{1},{2,3,4}}

Очевидно, что S(n,k)=0 для k>n. Положим также S(0,0)=1, так как по определению пустое семейство блоков является разбиением пустого множества.

8. Числа Белла. Рекуррентное соотношение для вычисления чисел Белла (с доказательством).

ОТВЕТ:

Числа Белла – Числа Белла B_n есть число всех разбиений n-элементов множества B_n = |П(А)|, где |A| =n

Другими словами, B_n =

9. Числа Стирлинга I рода. Формула для вычисления чисел Стирлинга I рода (с доказательством).

ОТВЕТ:

Числа Стирлинга – s(n,k) есть коэффициенты при последовательных степенях переменной x в многочлене [x]_k:

Видно, что s(n,k)=0 для k>n.

ФОРМУЛЫ:

Формулы (4.5) и (4.6) очевидны. Формулу (4.4) получим, сравнивая коэффициенты при X^k обеих частях равенства.

[X]_n = [X]_n-1(x-n+1).

10. Беззнаковые числа Стирлинга I рода. Формула для вычисления беззнаковых чисел Стирлинга I рода (с доказательством).

11. Формула включений и исключений (с доказательством).

ОТВЕТ:

Формула (или принципе) включений и исключений – комбинаторная формула, позволяющая определить мощность объединения конечного числа конечных множеств, которые в общем случае могут пересекаться друг с другом.

Обозначим через |N| мощность множества N, из этого следует, что:

12. Решение задачи о беспорядках.

13. Формула для вычисления числа предметов, обладающих ровно n свойствами (с доказательством + доказательство леммы).

Формула для вычисления – Принцип включения и исключения.

Комбинируя выписанные три формулы, получим формулу включений и исключений для m+1 свойств а₁,а₂,…a_m,a_m+1. Что и требовалось доказать.

Лемма:

14. Формула для вычисления числа предметов, обладающих не менее чем, k свойствами (с доказательством).

15. Решение задачи о встречах.