Генератриса

Матеріал з Вікіпедії — вільної енциклопедії.

У комбінаториці генератри́са послідовності ${a n}$ — це формальний степеневий ряд

$\sum_{n=0}^\infty a_n x^n$ .

Експоненційна генератриса — це формальний степеневий ряд

$\sum_{n=0}^\infty a_n \frac{x^n}{n!}$ .

Доволі часто генератриса послідовності ${a n}$ є одночасно рядом Тейлора відомої аналітичної функції, і це можна використовувати при дослідженні властивостей самої послідовності. Тим не менше, генератрисі необов'язково відповідає аналітична функція.

Наприклад, два ряди

$\sum_{n=0}^\infty (3^n)^n x^n$ і $\sum_{n=0}^\infty (2^n)^n x^n$

мають радіус збіжності нуль, тобто розбігаються в усіх точках , крім нуля, а в нулі обидва дають 1, тобто як функції вони співпадають; тим не менше, як генератриси (тобто формальні ряди) вони різні.

Генератриси надають можливість просто описувати складні послідовності в комбінаториці, а іноді допомагають знайти для них явні формули. Метод генератрис був розроблений Ейлером у 50-х роках XVIII століття.

[ред.] Властивості

(Експоненційна) генератриса суми (чи різниці) двох послідовностей дорівнює сумі (чи різниці)відповідних (експоненційних) генератрис.
Якщо $A(x)=\sum_{n=0}^\infty a_n x^n$ і $B(x)=\sum_{n=0}^\infty b_n x^n$ —генератриси послідовностей ${a n}$ і ${b n}$ , то $A(x)B(x)=\sum_{n=0}^\infty c_n x^n$ , де $c_n = \sum_{k=0}^n a_k b_{n-k}$ .
Якщо $A(x)=\sum_{n=0}^\infty a_n \frac{x^n}{n!}$ і $B(x)=\sum_{n=0}^\infty b_n \frac{x^n}{n!}$ — експоненційні генератриси послідовностей ${a n}$ і ${b n}$ , то $A(x)B(x)=\sum_{n=0}^\infty c_n \frac{x^n}{n!}$ , де $c_n = \sum_{k=0}^n {n\choose k} a_k b_{n-k}$ .

[ред.] Приклади

Нехай $B n$ дорівнює кількості варіантів представлення числа $n$ у вигляді $k_1+k_2+\cdots+k_m$ , где ${k i}$ — невід'ємні цілі числа і $m$ фіксовано, тоді

$\sum_{n=0}^\infty B_nx^n=(1+x+x^2+\cdots)^m=(1-x)^{-m}$

Тепер число $B n$ можна знайти як коефіцієнт при $x n$ в розкладі $(1 - x) - m$ по степеням $x$ . Для цього можна скористатися визначенням біноміальних коефіцієнтів або ж безпосередньо взяти n разів похідну в нулі: