Представьте, что ребенок держит в руках несколько красных и желтых кубиков. Он выставляет их в ряд, потом перемешивает и выставляет в новый ряд. Таких комбинаций может быть много — число будет зависеть от количества кубиков каждого цвета.
Мы можем узнать, сколькими способами можно расположить в ряд кубики красного и желтого цветов — для этого используется метод производящих функций. В этом уроке разберем, что такое производящая функция, рассмотрим ее обычный вид и научимся ее использовать.
Что такое производящая функция
Производящая функция — это многочлен, коэффициенты которого соответствуют членам последовательности чисел . Эту функцию используют, чтобы решать реккурентные соотношения, потому что она умеет кодировать информацию о целочисленной последовательности.
Например, простая последовательность — это постоянная последовательность .
Производящая функция для нее:
Когда функция используется без уточнения, ее называют обычной производящей функцией. Разберем подробнее, как она выглядит.
Как выглядит производящая функция
Обычная производящая функция — это функция вида . Разберем на примере, как ее использовать.
Представим, что нам нужно найти, сколькими способами можно составить сумму . При этом можно использовать по одному элементу из каждого из следующих двух наборов: и .
Рассмотрим два многочлена:
— это количество способов составить сумму с помощью одного элемента из каждого набора.
Например, коэффициент во втором многочлене равен . Значит, существует один способ составить сумму из четырех, используя только один элемент из набора.
Теперь рассмотрим произведение многочленов:
В полиномиальном произведении — количество способов составить сумму из , когда берется по одному числу из каждого набора.
Разложим произведение:
Коэффициент равен нулю при , так как мы не можем получить сумму больше . Если взять самые большие числа из каждого набора, то получится число .
То же самое относится и к . Берем самые маленькие числа из наборов и получаем .
Когда , коэффициент равен трем. Это означает, что есть три способа получить число . Если c помощью формулы дистрибутивности мы развернем произведение полностью, то увидим, что три члена получаются из произведений:
Производящая функция придает смысл коэффициенту , но не придает смысла . Она кодирует числа объектов с помощью формальных степенных рядов — многочленов с бесконечно большим количеством членов.
В разобранном примере можно было просто подсчитать количество способов получения числа 10 путем проверки. Но производящие функции полезны, когда многочлены выражены в более компактной форме — например, с помощью суммы геометрического ряда.
Выводы
В этом уроке мы изучили метод производящих функций, рассмотрели ее обычный вид и научились ее использовать. Теперь в вашем арсенале есть еще один инструмент для решения задач в комбинаторике.
Самостоятельная работа
Задача №1
У Васи есть четыре вида лука в разном количестве:
-
Пурпурный — количество может быть любым неотрицательным целым числом
-
Зеленый — количество кратно 2
-
Красный — количество кратно 3
-
Синий — количество кратно 4
Если у Васи 23 луковицы, сколько различных распределений цветов может быть?
Нажмите, чтобы увидеть ответ
Мы хотим найти количество неотрицательных целочисленных решений задачи. Сначала обозначим цвета буквами:
-
Пурпурный —
-
Зеленый —
-
Красный —
-
Синий —
Далее обозначим общее количестов луковиц через формулу:
Таким образом, мы можем обозначить формулами луковицы всех цветов:
-
, где
-
, где
-
, где
-
, где
-
По формулам выше мы видим, что коэффициент в разложении равен .
Другой способ заключается в решении задачи по , через синий цвет.
Случай :
Мы видим, что подхоит: .
и также подхоят.
Получаем вартанта.
Случай
и варианта в этом подслучае, при .
в этом подслучае.
в этом подслучае.
Итого в этом случае вариантов.
Случай
здесь
здесь
здесь
здесь
здесь
На этом этапе вы должны увидеть закономерность: мы можем доказать это, взяв два случая: один, где нечетное, и другой, где четное.
Всего здесь случай.
Случай
здесь
здесь
Отсюда мы можем получить, что сумма для этого случая равна , по аналогии со случаем .
Случай
здесь
здесь
в этом случае.
Суммируя все это, получаем
Задача №2
Найдите количество неотрицательных целочисленных решений задачи .
Нажмите, чтобы увидеть ответ
В условии есть такие данные:
Пусть:
Следовательно:
Далее вычисляем — общее число интегральных решений:
Отсюда следует, что общее количество решений исходного уравнения равно 117:
Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.
