Теорема 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 . Составим таблицу 2.3 для нахождения чисел Стирлинга

Таблица 2.3

Числа Стирлинга

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можно вычислить по формуле. Рассмотрим более простые формулы для нахождения чисел Белла.