Метод производящий функций

Этот метод используется для перечисления комбинаторных чисел и установления комбинаторных тождеств.

Исходным пунктом являются последовательность {a_i} комбинаторных чисел и последовательность функций {φ_i(x)} (i = 0, 1, …).

Рассмотрим ряд

,

который, в случае, когда последовательность {a_i} конечна, т.е. 0 ≤ i ≤ n, будет многочленом.

При определенных ограничениях данный ряд будет сходящимся и тогда он в некоторой области будет задавать функцию F(x):

Эта функция называется производящей функцией.

Пример 1.

(i=0,1, …, n), φ_i(x)-xⁱ

В этом случае имеем

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

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

Для этого возьмем тождество

Оно эквивалентно тождеству

Сравнивая коэффициенты при xⁿ, получим

Пример 1.

Применение метода производящей функции, когда функция определяется степенным рядом.

Последовательность чисел f_n называется числами Фибоначчи, задается рекуррентными соотношениями f_n = f_n-1+ f_n-2 и f₀ = f₁ = 1

Возьмем φ_n(x) = xⁿ (n = 0,1, 2, …). С этой последовательностью связан ряд

который в силу f_n ≤ 2ⁿ (поскольку f_n ≤ 2f_n-1) сходится при │ x│ < ½ и определяет производящую функцию F(x)

Так как

и

то

или

(1-x-x²)F(x) =1

Отсюда находим явный вид производящей функции F(x):

Решая уравнение x² + x – 1 = 0 находим его корни

Найдем разложение F(x) на элементарные дроби

Имеем ax₂ + bx₁ – (a + b)x = -1

Это справедливо, если a = - b и .

Далее, воспользовавшись формулой для суммы убывающей геометрической прогрессии (при ) получим

откуда

что дает явное выражение для чисел Фибоначчи.

Контрольные вопросы

1. Что такое комбинаторика и для чего она нужна?

2. Что называется:

— перестановкой п-элементного множества;

— размещением из п элементов по т элементов;

— сочетанием из п элементов по т элементов?

3. В чем отличие размещений от перестановок?

4. В чем отличие сочетаний от размещений?

5. Сколькими способами можно разместить три книги на книжной полке?

6. Запишите формулу для вычисления числа сочетаний элементов, исполь­зуемую в формуле бинома Ньютона.

7. Как найти число перестановок с повторениями?

8. Сколько существует пятизначных чисел, у которых каждая следующая цифра:

—меньше предыдущей,

— больше предыдущей.

9. Сколько прямых можно провести через п точек, если никакие три из них не лежат на одной прямой?

10. Сколько разных слов можно составить перестановкой букв в слове «чачача»?

11. Вычислите: (а + b + с)2; (а + b + с)3.

12. Покажите, что сумма делится на р, где р — простое число.

13. Докажите свойства биномиальных коэффициентов.

14. Какая разница между декартовым квадратом некоторого непустого мно­жества A и множеством всех двухэлементных подмножеств множества A?

15. Сколько отношений эквивалентности можно построить на множестве, ко­торое состоит из двух, трех, четырех элементов? Сколько бинарных отно­шений можно задать на множестве из п элементов?

16. Сколько существует функций из множества A в множество В, если \А\ = т, а |B| = n?

Лекция № 6

В самой математике главные средства достигнуть истины – индукция и аналогия.

Лаплас, Опыт философии теории вероятностей, М., 1908, стр.7.

АЛГЕБРАИЧЕСКАЯ СИСТЕМА