Теорема 2.

где q₁, …, q_т являются различными простыми делителями числа n.

Доказательство. Находим число не взаимно простых с n по формуле включения и исключения, пользуясь тем, что количество делящихся среди {1,2, …, n} на число q равно n/q . Затем это число отнимаем от n.

§2.4. Разбиения

Напомним, что разбиением множества A называется семейство {A_i} его непустых попарно непересекающихся подмножеств, таких что _iA_i = A. Подмножества A_i называются блоками разбиения. Если в семействе учитывается порядок подмножеств, и если допускаются пустые блоки, то оно называется упорядоченным разбиением.

Упорядоченные разбиения и обобщенный бином Ньютона. Будем говорить, что упорядоченное разбиение ( A₁ , A₂ ,  , A_m ) множества E={e₁, e₂, , e_n} имеет тип ( k₁ , k₂ ,  , k_m ), если |A₁| = k₁ , |A₂| = k₂ , , |A_m| = k_m . Число таких разбиений обозначается через P(k₁ , k₂ ,  , k_m) или P_n(k₁ , k₂ ,  , k_m), где n= k₁ + k₂ +  + k_m .

Лемма 1.

.

Доказательство. Подмножество A₁ можно выбрать способами. ПодмножествоA₂ выбирается из оставшихся n-k₁ элементов, его можно будет выбрать способами. ПодмножествоA₃ – способами, и т.д. Выбор подмножестваA_m определен предшествующими подмножествами. Отсюда получаем .

Поскольку n – k₁ – ∙∙∙ – k_m-1 = k_m , то после сокращения дроби получаем нужное равенство.

Теорема 1.

.

Доказательство. Рассмотрим как ящики сомножители произведения

.

Произведение состоит из слагаемых вида . Каждое такое слагаемое встречается столько раз, сколько существует упорядоченных разбиений множества ящиков. Разбиение будет состоять из следующих подмножеств: первое подмножество состоит из ящиков, откуда выбранx₁, второе состоит из подмножеств, откуда выбран x₂ и т.д. Отсюда коэффициент при будет равенP(k₁, k₂,  , k_m). Что и требовалось доказать.

Разбиения и перечисление сюръекций. Пусть {B₁,  , B_k } – разбиение множества X, состоящего из n элементов. Обозначим через _k(X) множество разбиений X на k блоков, а через (X) – множество всех разбиений. Число S(n,k) = |_k(X)| называется числом Стирлинга второго рода, B_n=|(X)| – числом Белла. Ясно, что . Каждому разбиению мы сопоставили отношение эквивалентности и заметили, что разбиения составляют решетку относительно включения соответствующих отношений эквивалентности. Отсюда множество разбиений будет решеткой относительно неравенства  каждый блок B является объединением некоторых блоков из . Например, {{1},{2},{3}}{{1},{2,3}}.

Пусть s_n,k – число сюръекций f:{1,2,  ,n} {1,2,  , k}. Каждой сюръекции соответствует разбиение {f ^–1(y): 1  y  k}. Отсюда легко видеть, что s_n,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 блоков B₁, B₂,  , B_k соответствует k разбиений

B₁  {n}, B₂,  , B_{k ,}

B₁, B₂ {n},  , B_{k ,}



B₁, B₂ ,  , B_k  {n}_,

Следовательно, S(n,k)=S(n-1,k-1)+kS(n-1,k), при 0 < k < n .

Составим таблицу для нахождения чисел Стирлинга:

n k	1	2	3	4	5	6	7	8	9
1	1
2	1	1
3	1	3	1
4	1	7	6	1
5	1	15	25	10	1
6	1	31	90	65	15	1
7	1	63	301	350	140	21	1
8	1	127	966	1701	1050	266	28	1
9	1	255	3025	7770	6951	2646	462	36	1
10	1	511	9330	34105	42525	22827	5880	750	45

Пример 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.

Положим B₀=1. Число Белла B_n можно вычислить по формуле .

Рассмотрим более простые формулы для нахождения чисел Белла.