Числа разбиений с фиксированными частями

I. Определения.

А. - или E(n; m₁, m₂,…, m_k) - число способов помещения различных предметов в т различных ящиков, где п_k — число предметов в k-м ящике, k= 1,2,... .,., т.

— число перестановок символов, составленных из циклов длины k для k= 1,2,... .,., n,

илиD(n; k₁, k₂,…, k_n)— число всех возможных разбиений множества из различных предметов на подмножества , содержащие k предметов, k= 1,2,... .,., n.

В. Производящие функции:

С. Явные выражения:

В. Контрольные соотношения:

суммирование по ;

суммирование по и

Вопросы для контроля знаний и подведения итога прочитанной лекции

1. В чем суть метода математической индукции?

2. В чем состоят два основных правила перечисления в комбинаторике?

2. Что называют перестановкой без повторений?

3. Что называют перестановкой с повторениями?

4. Что называют размещением без повторений?

5. Что называют размещением с повторениями?

6. Что называют сочетанием без повторений?

7 Что называют сочетанием с повторениями?

8. Что называют упорядоченным разбиением множества A на k блоков?

9. Что называютчислами Стирлинга второго рода?

10. Что называют неупорядоченным разбиением множества A на k частей (композициями)?