.
Доказательство. Рассмотрим как ящики сомножители произведения
.
Произведение состоит из слагаемых вида . Каждое такое слагаемое встречается столько раз, сколько существует упорядоченных разбиений множества ящиков. Разбиение будет состоять из следующих подмножеств: первое подмножество состоит из ящиков, откуда выбран x1, второе состоит из подмножеств, откуда выбран x2 и т.д. Отсюда коэффициент при будет равен P(k1, k2, ×××, km). Что и требовалось доказать.
Разбиения и перечисление сюръекций. Пусть {B1, ×××, Bk } – разбиение множества X, состоящего из n элементов. Обозначим через Pk(X) множество разбиений X на k блоков, а через P(X) – множество всех разбиений. Число S(n,k) = |Pk(X)| называется числом Стирлинга второго рода, Bn=|P(X)| – числом Белла. Ясно, что . Каждому разбиению мы сопоставили отношение эквивалентности и заметили, что разбиения составляют решетку относительно включения соответствующих отношений эквивалентности. Отсюда множество разбиений будет решеткой относительно неравенства p£s Û каждый блок BÎs является объединением некоторых блоков из p. Например, {{1},{2},{3}}£{{1},{2,3}}.
|
|
Пусть sn,k – число сюръекций f:{1,2, ×××,n}® {1,2, ×××, k}. Каждой сюръекции соответствует разбиение {f –1(y): 1 £ y £ k}. Отсюда легко видеть, что sn,k =k!S(n,k). Положим S(0,0)=1.
Пример 2. Число S(4,2) равно 7, ибо все разбиения множества {1,2,3,4, 5, 6, 7} на два блока исчерпываются следующими:
{{1},{2,3,4}}, {{2},{1,3,4}}, {{3},{1,2,4}}, {{4},{1,2,3}},
{{1,2},{3,4}}, {{1,3},{2,4}}, {{1,4},{2,3}}.
Теорема 2. Имеют место следующие свойства чисел Стирлинга второго рода:
· S(n,k)=0, при k > n.
· S(n,0)=0 и S(n,n)=1, при n>0.
· S(n,k)=S(n-1,k-1)+kS(n-1,k), при 0 < k < n.
Доказательство. Докажем последнее соотношение. Множество разбиений множества {1,2, ×××,n} состоит из двух классов:
(1) разбиения, содержащие блок {n};
(2) разбиения, для которых n принадлежит блокам, имеющим более одного элемента.
В первом классе S(n-1,k-1) разбиений.
Во втором классе получаем kS(n-1,k) разбиений, ибо каждому разбиению множества {1, 2, ×××, n-1} на k блоков B1, B2, ×××, Bk соответствует k разбиений
B1 È {n}, B2, ×××, Bk,
B1, B2È {n}, ×××, Bk,
×××××××××××××××××××××××××××××××
B1, B2 , ×××, Bk È {n},
Следовательно, S(n,k)=S(n-1,k-1)+kS(n-1,k), при 0 < k < n.
Составим таблицу для нахождения чисел Стирлинга:
n k | |||||||||
Пример 3. Найдем число сюръекций {1,2,3,4,5,6}®{1,2,3,4}. Оно равно 4!S(6,4). Число S(6,4) находим из таблицы. Отсюда искомое число = 4!∙65 = 1∙2∙3∙4∙65 = 1560.
|
|
Положим B0=1. Число Белла Bn можно вычислить по формуле .
Рассмотрим более простые формулы для нахождения чисел Белла.
Теорема 3. , " n ³ 0.
Доказательство. Множество разбиений X={1,2, ×××, n+1} состоит из классов, зависящих от блока A содержащего n+1. Для таких A будет справедливо включение X\A Í{1, 2, ×××, n}. Отсюда каждое разбиение можно получить, выбрав блок A ' n+1 и разбиение pÎP(X\A). Выбор блока A с | A|=k+1, будет осуществляться выбором подмножества из {1,2, ×××,n}, состоящего из k элементов. Следовательно, .