Генератриса

У комбінаториці генератри́са або твірна функція (Шаблон:Lang-en) послідовності ${a_{n}}$ — це формальний степеневий ряд

f (x) = \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} (\binom{n}{k}) a_{k} b_{n - k}$ .

Приклади

Нехай $B_{n}$ дорівнює кількості варіантів представлення числа $n$ у вигляді $k_{1} + k_{2} + \dots + k_{m}$ , де ${k_{i}}$ — невід'ємні цілі числа і $m$ фіксовано, тоді

\sum_{n = 0}^{\infty} B_{n} x^{n} = (1 + x + x^{2} + \dots)^{m} = (1 - x)^{- m}

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

B_{n} = (- 1)^{n} (\binom{- m}{n}) = m (m + 1) \dots (m + n - 1) / n! = (\binom{m + n - 1}{n}) .

Додатково

Переклад «генератриса» терміна «generating function» з англійської є не досить вдалим. Краще використовувати натомість більш вживаний термін в українській математичній літературі — «твірна функція», якому відповідає російське «производящая функция» [1]Шаблон:Недоступне посилання.

Див. також

Посилання

Генератриса

Зміст

Властивості

Приклади

Додатково

Див. також

Посилання

Навігаційне меню

Генератриса

Властивості

Приклади

Додатково

Див. також

Посилання

Навігаційне меню

Пошук