Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-02-26

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

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

3 <h2>Что такое производящая функция</h2>

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

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

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

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

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

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

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

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

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

13 <ul><li>x^2 + x^3 + x^6 + x^7</li>

14 <li>x^3 + x^4 + x^5 + x^8</li>

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

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

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

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

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

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

21 (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

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

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

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

25 <ul><li>x^2 * x^8</li>

26 <li>x^6 * x^4</li>

27 <li>x^7 * x^3</li>

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

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

30 <h2>Выводы</h2>

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