Композиции чисел.

Теорема 8. Пусть C(m,n) обозначает число композиций числа n точно с m частями, тогда C(m,n)=.

Доказательство 1.

Рассуждение, используемое в доказательстве теоремы 4, можно легко применить для доказательства того, что

= (t¹+ t²+ t³+ t⁴+…)^m==t^m==.

Приравнивая коэффициенты при tⁿ в крайних членах этой цепочки равенств, получаем требуемое.

Доказательство 2.

Введем графическое представление для композиций числа n. C композицией (a₁a₂…a_m) числа n связываем m сегментов интервала [0, n]; первый сегмент имеет длину а₁, второй – длину а₂ и т. д. Например, композиция (3 2 3 1 2) числа 11 представим в виде

0←1─2→3←4→5←6─7→8↔9←10→11

Заметим теперь, что можно построить каждую из С(m,n) композиций числа n c m частями, выбирая m-1 чисел из n-1 первых целых как конечные точки для таких m сегментов, разделяющих интервал [0, n]. Поскольку таких выборов может быть , видим, что C(m,n)=.

Простота теоремы 6 позволяет получать чисто асимптотические выражения для некоторых функций разбиений, связывая их с функциями композиций. Например,

Теорема 9. (Эрдеш – Ленер). Пусть Р_M(n) обозначает число разбиений числа n ровно с М частями, тогда при n→∞

Р_M(n)≈ , если M=o(n^1/3).

Задачи

1.Пусть F_n – n-е число Фибоначчи F₀=0, F₁=1, F_n=F_n-1+F_n-2, n>1. Показать, что число композиций n, в которых нет единиц, равно F_n-1.

2. В более общем виде – Пусть kF_n – определяется по правилу;

kF₀=…=kF_k-2, kF_k-1=1, kF_n=kF_n-1+kF_n-k.

Показать, что число композиций n, в которых все части ≥ k, равно kF_n-1.

3. Из задачи 2 следует, имеется 2^n-1 композиций числа n.

4. пусть С_k(m,n) обозначает число композиций n точно с m частями, каждая из которых не меньше k. Тогда

С_k(m,n)=

5. Из задач 2 и 4 следует, что

= kF_n-1

Принцип включения и исключения.

Пусть A₁,…,A_n некоторые подмножества (необязательно различные) конечного множества Х.

Теорема 1.(Принцип включения и исключения).

-+-…(-1)^n-1||

Доказательство

Применим математическую индукцию по n.

Для n=1 терема очевидно справедлива!

Предположим, что для произвольных A₁,…,A_n-1 выполняется

||=-+-…(-1)^n-2||

Применяя эту формулу к сумме

,

получаем

||=-+…(-1)^n-2||,

а отсюда

||==+|A_n|-||=

-+-…(-1)^n-1||.

Покажем несколько применений принципа включения и исключения

Теорема 2. Пусть |X|=n, |Y|=k, то число всех функций f:XY и f(X)=Y, равно

S_n,k=

Доказательство

Пусть У={y₁,…,y_k} и A_i={f : f:XY & y_if(X)}, тогда

f(X)Yf

Множество всех f:XY имеет мощность kⁿ. Определим , пусть 1p₁…p_ik пересечение есть множество всех функций f:XY таких, f(X), a, следовательно, мощность этого пересечения ровно (m-i)ⁿ. Согласно теоремы 1 имеем

S_n,k=kⁿ-||=kⁿ- =

Эта формула дает простое выражение для вычисления чисел Стирлинга 2^го рода

S(n,k)= S_n,k=

Рассмотрим вопрос об определении числа “беспорядков” на множестве {1,…,n}

Определение. Под беспорядком на множестве {1,…,n} будем понимать произвольную перестановку f этого множества, такую что f(i)i для 1in.

Пусть D_n – множество всех беспорядков на {1,…,n} и

A_i={fS_n: f(i)=i}, i=1,…,n.

Заметим, что fD_n f A_i для i{1,…,n}, следовательно

|D_n|=|S_n|-+-+…(-1)^n-1||

Для произвольной последовательности 1p₁…p_in пересечение является множеством таких перестановок f, для которых f(p_j)=p_j для 1jn, и значит, ||=(n-i)!. Заметив, что последовательность 1p₁…p_in можно выбрать способами, получаем в итоге

|D_n|== =n!( )

Отметим, что сумма в скобках является начальным членом ряда е^-1=. Это означает, что беспорядки составляют е^-1=0.36788… всех перестановок.