При решении комбинаторных задач

Если

f (z) 

∞

∑ ak z k, (16)

k  0

то f (z) называют производящей функцией числовой последовательности a 0, a 1, …, ak, …. Если последовательность конечна или, начиная с некоторого места, все ее члены равны

нулю, то наряду с (16) пишут также

f (z) 

n

∑ ak z k,

k  0

предполагая, что члены последовательности с номерами больше чем n отсутствуют или равны нулю. Иногда производящей функцией последовательности a 0, a 1, …, ak, … называют ряд в правой части (16) и говорят, что производящая функция представлена в замкнутом виде, если для f (z) указано конечное аналитическое выражение.

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

последовательности биномиальных коэффициентов

C 0, C 1, …, C n

служит функция f (z) = (1 + z) n; для бесконечной

n n n

 б 

последовательности биномиальных коэффициентов

 ,

 k 

k = 0, 1, …, производящей функцией служит f (z) = (1 + z).

Обоснование для последних двух примеров дается в курсе анализа.

0,1, 2, 3, 4 … ∑ k

ln1− z

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

Задача о «размене». Требуется найти число способов разменять заданную сумму n рублей монетами достоинством 1,

2 и 5 рублей.

Обозначим искомое число способов размена через Pn, n = 0, 1, 2,…. Для малых значений n числа Pn легко вычисляются непосредственно:

P 0 = 1; P 1 = 1; P 2 = 2 (1 + 1, 2); P 3 = 2 (1 + 1 + 1, 1 + 2);

P 4 = 3 (1 + 1 + 1 + 1, 1 + 1 + 2, 2 + 2).

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

P (z) = P 0 + P 1 z + P 2 z 2 +….

Рассмотрим произведение

(1 + z + z 2 +…)(1 + z 2 + z 4 +…)(1 + z 5 + z 10 +…). (17) После раскрытия скобок и приведения подобных коэффициент при zn окажется равным Pn. В самом деле, коэффициент при zn в (17) – это число способов представить zn в виде произведения степеней zu, z 2 v, z 5 w, равное числу решений в целых неотрицательных числах уравнения

u + 2 v + 5 w = n.

Но это как раз и есть число «разменов» числа n единицами,

двойками и пятерками, т. е. число Pn. Следовательно,

P (z) = (1 + z + z 2 +…)(1 + z 2 + z 4 +…)(1 + z 5 + z 10 +…).

Суммируя геометрические прогрессии в скобках, получаем:

P (z)  1 ⋅ 1

⋅ 1. (18)

1 − z

1− z 2 1− z 5

Используя производную, можно найти явное выражение

для Pn:

P (n) (0)

Pn  n!.

Впрочем, представление (18) позволяет получить рекуррентные соотношения для вычисления чисел Pn. Вместе с

P (z)  1 ⋅ 1

⋅ 1 = P

+ P z + P

z 2 +…

пусть

1 − z

1− z 2 1− z 5 0 1 2

Q (z) 

1 − z

⋅ 1

1− z 2

= Q 0

+ Q 1

z + Q 2

z 2 +…,

Тогда:

R (z) 

1 − z

= R 0

+ R 1

z + R 2

z 2 +….

(1 – z) R (z) = 1;

(1 – z 2) Q (z) = R (z); (1 – z 5) P (z) = Q (z).

Приравнивая коэффициенты при одинаковых степенях,

получаем уравнения:

R 0 = 1, Rn – Rn –1 = 0 (n ≥ 1);

Qn – Qn –2 = Rn (n ≥ 2);

Pn – Pn –5 = Qn (n ≥ 5).

Отсюда выводятся следующие рекуррентные соотношения:

R 0 = 1, Rn = Rn –1 (n ≥ 1);

Qn = Rn (n < 2), Qn = Qn –2 + Rn (n ≥ 2);

Pn = Qn (n < 5), Pn = Pn –5 + Qn (n ≥ 5).

Последовательные вычисления можно свести в таблицу.

Задача о «счастливых билетах». Автобусный билет с шестизначным номером считается «счастливым», если сумма первых трех цифр равна сумме последних трех цифр. Например, билет 054 342 «счастливый». Требуется найти число счастливых билетов. Считается, что допустимы любые шестизначные номера.

Пусть x 1 x 2 x 3 y 1 y 2 y 3 – номер билета. Билет счастливый, если

x 1 + x 2 + x 3 = y 1 + y 2 + y 3.

Заменив последние три цифры их дополнениями до 9, т. е. полагая x 4 = 9 – y 1; x 5 = 9 – y 2; x 6 = 9 – y 3, предыдущее уравнение можно переписать так:

x 1 + x 2 + x 3 + x 4 + x 5 + x 6 = 27. (19)

Задача о счастливых билетах может быть переформулирована теперь следующим образом: требуется

найти число целых решений уравнения (19), удовлетворяющих следующим условиям:

0 ≤ xi < 10, i = 1, 2,…, 6.

Рассмотрим более общую задачу. Требуется найти число целых решений следующей системы:

x 1 + x 2 +…+ xk = n; 0 ≤ xi < m, i = 1, 2,…, k. (20)

Обозначим число решений (20) через Cn (k, m) (число счастливых билетов в этих обозначениях равно C 27(6, 10)). Если в выражении

(1 + z +…+ zm –1) k

раскрыть скобки и привести подобные, то коэффициент при zn окажется равен числу способов представить n в виде суммы k слагаемых, которые могут принимать значения 1, 2,…, m – 1. Но это как раз и есть число Cn (k, m). Таким образом,

(1 + z +…+ zm –1) k =  n Cn (k, m) zn.

Суммируя геометрическую прогрессию в левой части равенства, получаем представление производящей функции чисел Cn (k, m) в свернутом виде:

(1 – zm) k (1 – z)– k =  n Cn (k, m) zn.

По формулам бинома Ньютона имеем:

 k 

(1− z)− k

 ∑ (−1) s 

 z s;

(1− z m) k

 ∑ (−1) t 

 ztm.

s  s 

 t 

  t  

После перемножения этих рядов получится ряд с

коэффициентами Cn (k, m). Следовательно,

 − k  k 

Cn (k, m) = ∑

(−1) s  t 

 . (21)

s  tm  n

 s  t 

Используя формулу (21), заменяя s на n – tm и

получаем

k −1

n − tm k  n −

−1,

Cn (k, m) = ∑ (−1)2 s  t C s 

− C t =

(−1) t C k −1

C t.

s  tm  n

k s 1 k

∑

tm ≤ n

k  n − tm −1 k

В частности, если m = 10, n = 27, то tm ≤ n при t = 0, 1, 2.

Следовательно,

C 27(6, 10) =

C 5 C 0 – C 5

C 1 + C 5 C 2

= 55252.

32 6

22 6

12 6

Не нашли, что искали? Воспользуйтесь поиском: