Лекции. Теория графов и комбинаторика (стр. 11 )

Метод построения производящей функции для самих сочетаний с заданной спецификацией .

– число вхождений элементов типа в сочетание.

1.  Если входит в сочетание ровно раз, то ему соответствует множитель

2. 

3.  Сочетания будут коэффициенты при в разложении .

Пример.

С помощью ПФ найти из 3 по 4 и сами сочетания.

Лекция № 14.

ЭКСПОНЕНЦИАЛЬНЫЕ ПРОИЗВОДЯЩИЕ ФУНКЦИИ.

В предыдущей лекции рассматривались производящие функции для последовательности комбинаторных чисел , в которых комбинаторное число являлось коэффициентом при в этом формальном степенном ряде. С помощью производящих функций можно находить число сочетаний заданной спецификации (набором условий на число вхождений элементов в сочетание).

Определение 1.

Пусть – последовательность комбинаторных чисел (целых, неотрицательных). Экспоненциальной производящей функцией (ЭПФ) для этой последовательности называется степенной ряд , т. е. число является коэффициентом при .

Пример.

Рассмотрим последовательность для числа размещений из n элементов. Эля неё ЭПФ является функция .

Замечание.

Очевидно, ЭПФ обладает свойством линейности: если , то .

Рассмотрим примеры ЭПФ для некоторых часто встречающихся последовательностей.

1. 

2. 

3. 

4. 

ЭПФ применяются для нахождения числа размещений (упорядоченных сочетаний) заданной спецификации , где – условие на число вхождений элемента типа в размещение .

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

– число вхождений элементов типа в сочетание.

1.  Если входит в сочетание ровно раз, то ему соответствует множитель

2. 

3.  Числом размещений будет коэффициент при в разложении .

Пример.

С помощью ЭПФ найти число размещений из 3 по 4.

Замечание.

Мы вычислили также и т. д. как коэффициенты при соответствующих .

Пример.

С помощью ЭПФ найти число размещений из n по k.

Т. к. ограничения на число вхождений отсутствуют, то каждый элемент может входить 0, 1, 2 ... k раз.

Разложим в ряд и найдём коэффициент при :

Коэффициент при равен .

Лекция № 15.

ЛИНЕЙНЫЕ РЕКУРРЕНТНЫЕ УРАВНЕНИЯ.

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

Пример. (задача о разрезании пиццы).

На сколько частей делят плоскость n прямых, из которых любые 2 пересекаются и никакие 3 не пересекаются в 1 точке?

– искомое число.

Очевидно:

Пусть есть прямых . Проведём ещё одну , она пересекает в точках . Эти точки разбивают на n частей, принадлежащих новым n частям плоскости . Это и есть рекуррентное уравнение для последовательности .

С учётом начального условия можем вычислить .

Таким образом является решением уравнения .

Пример.

Известно рекуррентное соотношение для :

Пример.

Числа Стирлинга II рода – число разбиений n-множества на k непустых блоков, .