ОСНОВИ ДИСКРЕТНОГО АНАЛІЗУ.
Автори: Н.Д.Федоренко,В.В.Демченко

     1.10. ТВІРНІ ФУНКЦІЇ

      В комбінаторних задачах на підрахунки числа об'єктів при деяких обмеженнях шуканим розв'язком часто є деяка послідовність, наприклад: при обчисленні числа розбиттів.
В цьому випадку послідовності можна поставити у відповідність формальний ряд
,
який називають твірною функцією послідовності . Функціяможе бути як функцією дійсної так і комплексної змінної. Виразне що інше, як розклад функціїв ряд Тейлора - Маклорена.
Для довільних рядів тa
визначимо операції.
1. Додавання

2. Множення на число

3. Добуток Коші

де

З математичного аналізу відомо:
1. ; послідовність .
2. ; послідовність .
3. ; послідовність ;;- довільне.
4. ; послідовність .
5. ; послідовність .
6. ; послідовність .
7. ; послідовність , - довільне ;

      Наприклад, знайти твірну функцію послідовності . Відомо, що
, ,
тобто твірна функція послідовностіє.
Наприклад. Відомо, що числа Фібоначчіє розв'язком рекурентного рівняння
;
з початковими умовами.
Твірна функціядля послідовностізадовольняє рівнянню



Звідси, твірна функція для чисел Фібоначчі
.
Знайдемо корені рівняння
;,
де
;.
Розкладемона елементарні дроби:
;

;, тобто
.
Звідки
.
Нехаймає місце рівняння
- добуток Коші
.
Розкладемов ряд Маклорена,
.
Виберемо додатній розв'язок для
,
звідки
.
Числаназиваються числами Каталана, які з'являються при розв'язанні комбінаторних задач.

ЗМІСТ