Теория: Производящая функция

Представьте, что ребенок держит в руках несколько красных и желтых кубиков. Он выставляет их в ряд, потом перемешивает и выставляет в новый ряд. Таких комбинаций может быть много — число будет зависеть от количества кубиков каждого цвета.

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

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

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

Например, простая последовательность — это постоянная последовательность 1, 1, 1, . . ..

Производящая функция для нее:

G(s) = 1 + s + s^2 + s^3 + . . .

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

Как выглядит производящая функция

Обычная производящая функция — это функция вида f(x) = n=0suminftyanxn. Разберем на примере, как ее использовать.

Представим, что нам нужно найти, сколькими способами можно составить сумму 10. При этом можно использовать по одному элементу из каждого из следующих двух наборов: {2,3,6,7} и {3,4,5,8}.

Рассмотрим два многочлена:

• x^2 + x^3 + x^6 + x^7
• x^3 + x^4 + x^5 + x^8

x^n — это количество способов составить сумму n с помощью одного элемента из каждого набора.

Например, коэффициент x^4 во втором многочлене равен 1. Значит, существует один способ составить сумму из четырех, используя только один элемент из набора.

Теперь рассмотрим произведение многочленов:

(x^2 +x ^ 3 +x ^ 6 +x ^ 7 )(x ^ 3 +x ^ 4 +x ^ 5 +x ^ 8 )

В полиномиальном произведении x^n — количество способов составить сумму из n, когда берется по одному числу из каждого набора.

Разложим произведение:

(x^2 + x^3 + x^6 + x^7)(x^3 + x^4 + x^5 + x^8) = x^5 + 2x^6 + 2x^7 + x^8 + x^9 + 3x^10 + 3x^11 + x^12 + x^14 + x^15

Коэффициент x^n равен нулю при n > 15, так как мы не можем получить сумму больше 15. Если взять самые большие числа из каждого набора, то получится число 15 - 7 + 8.

То же самое относится и к (n > 5). Берем самые маленькие числа из наборов и получаем (5 - 2 + 3).

Когда n = 10, коэффициент равен трем. Это означает, что есть три способа получить число 10. Если c помощью формулы дистрибутивности мы развернем произведение полностью, то увидим, что три члена x^{10} получаются из произведений:

• x^2 * x^8
• x^6 * x^4
• x^7 * x^3

Производящая функция придает смысл коэффициенту x^n, но не придает смысла x. Она кодирует числа объектов с помощью формальных степенных рядов — многочленов с бесконечно большим количеством членов.

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

Выводы

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