5. Применение производящих функций в комбинаторике

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

Производящие функции дают еще более простой и универсальный метод решения рекуррентных соотношений. Данный метод основан на нахождении для рекуррентного соотношения соответствующей ему производящей функции такой, что ее коэффициент при является решением этого рекуррентного соотношения.

Задача 5. Найти решение рекуррентного соотношения , удовлетворяющее условию .

Решение.

Во многих задачах удается осуществлять пересчет комбинаторных конфигураций, предварительно не находя рекуррентных соотношений, связывающих искомые комбинаторные числа. Сейчас же заметим следующее: при решении подобных задач важно научиться извлекать из производящей функции информацию о «считающей» функции , с помощью которой подсчитывается число тех или иных комбинаторных конфигураций. Производящие функции – часто наиболее эффективный способ представления информации о функциях . Важно также уметь представлять неявно заданную «считающую» функцию в явном виде.

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

.

Найти рекуррентное соотношение

Решение.

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

Задача 7. Найти комбинаторный смысл выражения

.

Решение.

Исследователь, искусный в комбинаторном анализе, по заданному алгебраическому выражению, как правило, может определить, имеет оно или не имеет какой-либо комбинаторный смысл.

Как можно было убедиться ранее для «конструирования» необходимых производящих функций необходимо знать не только методы комбинаторики, но и методы математического анализа. При этом необходимо различать, когда в решении комбинаторной задачи используются только коэффициенты производящих многочленов, а когда используются и значения всех слагаемых ряда с учетом его радиуса сходимости. Если, например, положить в формуле для вычисления суммы членов геометрической прогрессии , то получим абсурдное равенство

,

в левой части которого стоит отрицательное дробное число, а в правой – сумма положительных целых чисел.

Тема №3. Целочисленные функции

1. Функция Антье

Эта функция задана на множестве действительных чисел . Она обозначается и определяется так: если , , то . Иными словами, функция антье – целая часть , т.е. наибольшее целое число, не превосходящее . Например, , , , ,

Основные приложения функции в комбинаторике связаны с теоремами.

Теорема 1. Количество натуральных чисел, кратных и не превосходящих ,

равно .

Доказательство.

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

. (1)

Представление числа в виде (1) называется его каноническим разложением.

Теорема 2. Показатель , с которым простое число входит в каноническое разложение числа , равен сумме

(2)

где показатель последнего слагаемого определяется условиями .

Доказательство.

Задача 1. Найти степень, в которой число 5 входит в каноническое разложение числа 360!

Решение.

Остальные рассматриваемые функции заданы на множестве натуральных чисел.