C n			(2n)!
	Cn =	2n		=			.
		n +1			n!(n +1)!

5.7. Производящие функции

Метод производящих функций является одним из самых развитых методов комбинаторного анализа и опирается на понятия функционального ряда.

Стандартная задача для использования производящих функций ставится следующим образом. Сколькими способами можно выполнить некоторое действие в ситуации, которая зависит от некоторого целого неотрицательного параметра n (им может быть, например, число каких-то объектов)?

К такому вопросу сводится большое число комбинаторных задач, ответ во всех таких задачах определяется этим параметром n, так что можно считать, что решением является последовательность a0 ,a1 ,a3 ,..., an .

Рекуррентное соотношение, если задано несколько первых членов последовательности (сколько - зависит от задачи), полностью определяет последовательность. Мощным методом решения вопросов подобного рода является метод производящих функций.

Производящей функцией последовательности {an}, n ≥ 0 на-

зывается формальный степенной ряд

F(z) = a0 + a1z + a2 Z 2 +... = an Z n .

Переход от последовательностей к их производящим функциям позволяет операции над последовательностями заменить операциями над их производящими функциями. Можно использовать то, что сумме двух последовательностей соответствует сумма их производящих функций, произведению последовательности на число - произведение ее производящей функции на это же число, и, что особенно замечательно, свертке двух последовательностей соответствует произведение производящих функций этих последовательностей.

Идея метода производящих функций состоит в том, что рекуррентное соотношение, определяющее последовательность {an},

136

переписывают как уравнение для ее производящей функции, это уравнение решают и по найденной производящей функции получают зависимость общего члена последовательности {an} от n.

5.8. Числа Стирлинга второго и первого рода

Числа Стирлинга первого рода s(n, k) – это коэффициенты при последовательных степенях переменной x в многочлене k:

n

(x)n = ∑s(n, k)xk ,

k =0

где (x)n – убывающий факториал: (x)n = x (x – 1)(x – 2) … (x – n +1).

Абсолютные значения чисел Стирлинга первого рода задают количество перестановок множества, состоящего из n элементов с k циклами.

Для них определяются рекуррентные соотношения: s(n, n) = 1 для n ≥ 0,

s(n, 0) = 0 для n > 0,

s(n, k) = s(n−1, k−1) + (n−1)s(n−1, k) для 0 < k < n.

Доказательство. Для n = 1 это равенство проверяется непосредственно. Пусть перестановка (n-1)-го порядка распадается на k циклов. Число n можно добавить после любого числа в соответствующий цикл. Все полученные перестановки – различные и содержат k циклов, их количество (n – 1)s(n – 1, k). Из любой перестановки (n

– 1)-го порядка, содержащей (k – 1) цикл, можно сформировать единственную перестановку n порядка, содержащую k циклов, добавив цикл образованный единственным числом n. Очевидно, что эта конструкция описывает все перестановки n-го порядка, содержащие k циклов. Тем самым равенство доказано.

Число Стирлинга второго рода S(n, k) – это число разбиений n-элементного множества на k блоков, т. е.

S(n, k) = |Πk(X)|,

где множество X состоит из n элементов. Например, S(4, 2) = 7. Рассмотрим некоторые утверждения, связанные с числами

Стирлинга второго рода:

•S(n, n) = 1 для n ≥ 0,

137

•S(n, 0) = 0 для n > 0,

•S(n, k) = S(n−1, k−1) + kS(n−1, k) для 0 < k < n

n

• xn = ∑S(n, k)[x]k для n ≥ 0, где [x]k = x(x−1)…(x−k+1).

k =0

Число Белла Bn – это число всех разбиений n-элементного множества:

Bn = |Π(X)|, где |X| = n.

Рассмотрим несложное рекуррентное соотношение:

n

Bn+1 = ∑C(n,i)Bi .

i=0

Для доказательства достаточно заметить, что множество всех разбиений множества X = {1, …, n+1} можно разделить на различные классы в зависимости от блока B, который содержит элемент n+1, или в зависимости от множества X/B. Далее для каждого множества X/B из {1, …, n} имеется |Π(X/ B)| = B|X\B| разбиений множества X, которое содержит B в качестве блока. Группируя классы в зависимости от мощности множества X/B, доказываем утверждение.

Контрольные вопросы и задания

5.1. В ящике 10 качественных и 5 бракованных деталей. Опыт состоит в выборе только одной детали. Событие А – вынули качественную деталь. Событие В – вынули бракованную деталь. Какое утверждение для этих событий будет неверным:

•событие А невозможно;

•событие В невозможно;

•события А и В равновероятны;

•события А и В несовместимы?

5.2.В слове SHUT меняют местами буквы. Чему равно количество всех возможных различных слов?

5.3.Чему равно количество различных способов выбора (порядок не имеет значения) 4 томов из 7-томного собрания сочинений А.П. Чехова?

138

5.4.Чему равно количество различных трехбуквенных комбинаций, которые можно составить из букв слова ЦВЕТОК (все буквы в комбинации различны)?

5.5.Чему равно количество различных двухбуквенных комбинаций, которые можно составить из букв слова КОМАР (все буквы

вкомбинации различны)?

5.6.В первой урне 4 белых и 6 черных шаров. Во второй урне 1 белый и 9 черных шаров. Из наудачу взятой урны вынули один шар. Сколькими способами можно выбрать один белый шар?

139