3.6. Понятие производящей функции

Из математического анализа хорошо известен ряд Маклорена:

φ(x) = ∑ _k^∞ _{= 0} a_kx^k, (3.18)

где а_k = φ^k(0) / k!.

В разложении (3.18) произвольной аналитической в ок­рестности нуля функции φ(x) ставится в биективное соответ­ствие последовательность чисел а_k.

В комбинаторном анализе часто приходится сталкиваться с задачами оперирования числовыми последовательностями, отвечающими различным комбинаторным конфигурациям. Например, может потребоваться вычисление суммы биномиальных коэффициентов с различными весами, как то:

∑ _k^∞ _{= 0} C_n^k , ∑ _k^∞ _{= 0} kC_n^k,

а также вычисления произведений рядов, составленных из этих коэффициентов и другие.

В таком случае часто оказывается возможным уп­ростить процесс получения результата, если сопоставить ко­мбинаторной последовательности {a_k} функцию, опре­де­ля­емую формальным рядом

f(x) = ∑ _k^∞ _{= 0} a_kx^k (3.19)

Такая f(x) именуется производящей функцией.

Если в ряде (3.19) все a_k, начиная с некоторого k равны нулю, то суммирование осуществляется в конечных преде­лах и построенная, таким образом, производящая функция носит название полиномиальной.

Для произвольных производящих функций

f_а(x) = ∑ _k^∞ _{= 0} a_kx^k и f _b(x) = ∑ _k^∞ _{= 0} b_kx^k

определены операции сложения:

f_а(x) + f _b(x) = ∑ _k^∞ _{= 0}(a_k + b_k) x^k, (3.20)

умножения на число

λf(x) = ∑ _k^∞ _{= 0} λa_kx^k (3.21)

и произведение Коши

f_а(x) f _b(x) = ∑ _k^∞ _{= 0} с_kx^k, (3.22)

где c_k = ∑ _i^k _{= 0}(a_ib_k-i).

Поясним применение производящих функций на при­мере исследования свойств сочетаний.

Пусть x₁, x₂, …, x_n — элементы n‑X множества. Составим произведение

f(x) = (1 + x₁x)(1 + x₂x)…(1 + x_nx).

Раскрывая в этом произведении скобки, получим

f(x) = 1 + (x₁ + x₂ + …+ x_n)x + (x₁x₂ + x₁x₃ +…+ x_n-1x_n)x² +…

…+(x₁x₂…x_n)xⁿ. (3.23)

В этой формуле каждое слагаемое x₁x₂…x_k (1 < k  n) можно считать k‑сочетаниями из n элементов x₁, x₂, …, x_n. Число таких сочетаний равно C_n^k. Полагая в (3.23) значения x₁ = x₂ = … = x_n = 1, получим

f(x) = ∑ _kⁿ _{= 0} C_n^kx^k = (1 + x)ⁿ . (3.24)

В данном случае производящей функцией после­довательности C_n^k есть функция (1 + x)ⁿ. Это частный случай бинома Ньютона, с которым мы встречались в 3.5.

Полагая x = 1, также как в (3.13) получим

∑ _kⁿ _{= 0} C_n^k = 2ⁿ. (3.25)

Подставляя, например в формулу (3.24) x = -1, видим, что коэффициенты C_n^k обладают следующим свойством

∑ _kⁿ _{= 0} ( -1)^kC_n^k = 0. (3.26)

Это свойство вытекает из симметрии коэффициентов C_n^k и C_n^n-k, однако с помощью производящих функций оно доказывается проще, чем комбинаторными рассуждениями.

Докажем еще тождество

C_n^k_+m = ∑ _s^k _{= 0} C_m^sC_n^k-s. (3.27)

Для доказательства воспользуемся производящей функцией:

(1 + x)^n+m = (1 + x)ⁿ(1 + x)^m.

Перемножив соответствующие ряды по правилу произведения Коши, получим производящую функцию

∑ _kⁿ _{= 0} C_n^kx^k ∑ _k^m _{= 0} C_m^kx^k = ∑_k^{m+ n} _{= 0} ∑ _s^k _{= 0} C_m^sC_n^k-sx^k,

для которой

C_n^k_+m = ∑ _s^k _{= 0} C_m^sC_n^k-s,

что в точности совпадает с (3.27).

Ниже приведено комбинаторное доказательство этого же факта, которое выглядит более громоздко.

Предположим, что в урне имеется n + m шаров: n — белых и m — красных. Выбор k шаров можно выполнить C_n^k_+m способами. При этом все k‑подмножества можно клас­сифицировать по числу шаров одного цвета, например, крас­ного. Любое k‑подмножество, содержащее s красных шаров можно получить, выбирая s красных шаров одним из C_m^s способов, а затем k-s белых шаров, одним из C_n^k-s способов. Таким образом, число всех подмножеств, включающих s красных шаров равно C_m^s C_n^k-s. Суммируя это произведение от 0 до k, получим тождество (3.27).

Эти примеры показывают, что производящие функции позволяют в ряде случаев упростить доказательства комби­наторных построений.