Решение. Пусть свойство si: ai=i. Тогда Ni1 ,...,is = (n − s)!

В ∑ Ni1 ,...is имеется Cns слагаемых (см. пример 4.2). Далее

1≤i1 <...<is ≤n

Лекция 5. Производящие функции. Основные операции. Примеры использования.

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

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

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

Определение. Пусть дана последовательность a0,a1,a2,…. Ряд

∞

A(s) = ∑ak sn называется производящей функцией (ПФ) для по-

k =0

следовательности {an }, s R .

Замечание. Если ряд A(s) сходится к функции f(s), то функция f(s) также называется ПФ для {an}.

17

Основные операции

Пусть xk, yk, zk, k=0,1,2… - последовательности, а X(s), Y(s) и Z(s)

- соответствующие им ПФ.

Линейные операции

Если a и b - константы, то последовательность zn=axn+byn имеет ПФ z(s)=aX(s)+bY(s).

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

= aX (s) +bY (s)

Сдвиг начала

Последовательность yk=0, для k=0,…,i-1; yk=xk-i, k=i,i+1,… име-

ет производящую функцию Y(s)=X(s)si. Доказательство.

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

18

i =0

Z(s)=X(s)Y(s).

Примеры использования ПФ

Пример 5.1 Найти ∑t Cnj−i .

i=1

Решение: Обозначим xij = Cnj−i . Для каждого фиксированного i

будем рассматривать xij как последовательность, задаваемую индексом j. Тогда

Xi(s)=(1+s)n-i

Нам необходимо определить последовательность y j = ∑t xij .

i=1

ПФ для yj имеет вид:

Так как (1+s)n/s и (1+s)n-t/s являются сдвигами начала для функций (1+s)n и (1+s)n-t соответственно, то

y j = ∑t Cnj−i =Cnj+1 −Cnj−+t1. i=1

20