флеров

2. Формула 2.

Доказательство. Рассмотрим множество всех разбиений множества X={1, 2, ..., n+1} на m классов. Количество таких разбиений есть S(n+1, m). Все разбиения распадаются на различные типы, соответствующие разным подмножествам множества X, содержащим элемент n+1. Для каждого k- элементного подмножества B  X, содержащего элемент n+1, существует в точности S(n+1 k, m-1) разбиений множества X на m-1 класс, содержащих B в качестве класса. Действительно, каждое такое разбиение однозначно соответствует разбиению множества X \ B на m-1 класс. k - элементное подмножество B  X, содержащее элемент n+1 можно выбрать способами. Таким образом имеем:

3. Вернемся еще раз к связи комбинаторных объектов с исчислением конечных разностей. Из формулы ( 1 .13) следует, что, например,

, (1.15)

откуда заключаем на основании разложения ( 1 .8):

1! S(4, 1) = 1, 2! S(4, 2)=14, 3! S(4, 3) = 36, 4! S(4, 4) = 24.

Указанная связь дает альтернативный способ вычисления последовательности S(n, k). 

Содержание