Зарегистрируйтесь для доступа к 15+ бесплатным курсам по программированию с тренажером

Производящая функция Комбинаторика

eyJpZCI6IjI2YTBiYzI2NmUxNmU0MTgyMWQyYTI4MmIwMTYwOTQyLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=d28ee89b36901321fcebd085c9e808caefbe3b1606b87203c84d89874a03cb2b

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

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

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

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

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

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

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

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

Обычная производящая функция — это функция вида . Разберем на примере, как ее использовать.

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

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

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

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

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

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

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


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

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

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

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

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

Выводы

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


Самостоятельная работа

Задача №1

У Васи есть четыре вида лука в разном количестве:

  • Пурпурный — количество может быть любым неотрицательным целым числом

  • Зеленый — количество кратно 2

  • Красный — количество кратно 3

  • Синий — количество кратно 4

Если у Васи 23 луковицы, сколько различных распределений цветов может быть?

Нажмите, чтобы увидеть ответ

Мы хотим найти количество неотрицательных целочисленных решений задачи. Сначала обозначим цвета буквами:

  • Пурпурный —

  • Зеленый —

  • Красный —

  • Синий —

Далее обозначим общее количестов луковиц через формулу:

Таким образом, мы можем обозначить формулами луковицы всех цветов:

  • , где

  • , где

  • , где

  • , где

По формулам выше мы видим, что коэффициент в разложении равен .

Другой способ заключается в решении задачи по , через синий цвет.

Случай :

Мы видим, что подхоит: .

и также подхоят.

Получаем вартанта.

Случай

и варианта в этом подслучае, при .

в этом подслучае.

в этом подслучае.

Итого в этом случае вариантов.

Случай

здесь

здесь

здесь

здесь

здесь

На этом этапе вы должны увидеть закономерность: мы можем доказать это, взяв два случая: один, где нечетное, и другой, где четное.

Всего здесь случай.

Случай

здесь

здесь

Отсюда мы можем получить, что сумма для этого случая равна , по аналогии со случаем .

Случай

здесь

здесь

в этом случае.

Суммируя все это, получаем


Задача №2

Найдите количество неотрицательных целочисленных решений задачи .

Нажмите, чтобы увидеть ответ

В условии есть такие данные:

Пусть:

Следовательно:

Далее вычисляем — общее число интегральных решений:

Отсюда следует, что общее количество решений исходного уравнения равно 117:




Аватары экспертов Хекслета

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты

Об обучении на Хекслете

Для полного доступа к курсу нужен базовый план

Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
1000
упражнений
2000+
часов теории
3200
тестов

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно

  • 130 курсов, 2000+ часов теории
  • 1000 практических заданий в браузере
  • 360 000 студентов
Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»

Наши выпускники работают в компаниях:

Логотип компании Альфа Банк
Логотип компании Aviasales
Логотип компании Yandex
Логотип компании Tinkoff

Используйте Хекслет по-максимуму!

  • Задавайте вопросы по уроку
  • Проверяйте знания в квизах
  • Проходите практику прямо в браузере
  • Отслеживайте свой прогресс

Зарегистрируйтесь или войдите в свой аккаунт

Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»