Математические байки

А вот статья "О раскрытии скобок, об Эйлере, Гауссе, Макдональде и об упущенных возможностях" Д. Фукса (да, того самого, который Фукс-Табачников) в Кванте, которую цитирует Ландо. И я её очень советую прочитать — даже если начало покажется простым, к концу становится ну очень интересно. На скриншоте выше один кусочек картинка оттуда — как раз из второй половины статьи.

Это — из "Лекций о производящих функциях" С. К. Ландо.

Знакомая последовательность? И уже понятно, откуда взялась рекуррентная формула выше: это мы записали произведение P(q)*Q(q)=1 и приравняли коэффициенты при q^n в левой и в правой частях равенства: при всех n>0 \sum_{j=0}^n c_j p(n-j) = p(n)-p(n-1)-p(n-2)+p(n-5)+p(n-7)-... =0.

Если действительно руками скобки пораскрывать, то вдруг (совершенно поразительно) окажется, что почти всё сократилось: Q(q) = 1 -q -q^2 +q^5 +q^7 - q^12 - q^15 +...

Из разложения P в произведение мы знаем и разложение Q; давайте раскроем скобки — и пусть c_n это получившиеся коэффициенты.

Теперь давайте посмотрим на обратный ряд к P(q) — просто формально записав Q(q)=1/P(q).

В скобках — очень забавно, что совсем похоже устроено произведение Эйлера для дзета-функции. Просто роль q^j играет p^{-s}, а по основной теореме арифметики каждое натуральное число ровно одним способом раскладывается в произведение простых, поэтому числители единичные.

Если ограничения на величину слагаемых нет — получается уже просто бесконечное произведение:

Первая скобка отвечает за единицы, вторая за двойки, и так далее — так что (сгруппировав одинаковые слагаемые) разбиению n, в котором a_1 единиц, a_2 двоек,..., a_k слагаемых, равных k, мы сопоставляем произведение мономов из этих скобок, где q^{1*a_1} взят из первой скобки, q^{2*a_2} из второй, и т. д.. А дальше — каждая скобка "собирается", как сумма геометрической прогрессии.

Если бы мы работали не со всеми разбиениями n, а только с разбиениями в сумму слагаемых, не превосходящих k, то производящая функция развалилась бы в произведение k скобок-сомножителей:

Как это соотношение можно получить? Беглый взгляд показывает, что это явно что-то нетривиальное. Поэтому давайте его временно отложим в сторону, и применим к последовательности p(n) стандартный молоток (а точнее, кувалду) комбинаторики — рассмотрим производящую функцию этой последовательности: P(q):=\sum_{n=0}^{\infty} p(n) q^n.

Применение этого равенства — кадр из великолепного видео Mathologer-а "The hardest "What comes next?" (Euler's pentagonal formula)" — которое я очень всем советую.

Но нас будет интересовать другой способ — оказывается, на сами p(n) тоже есть рекуррентное соотношение, только чуть более сложное! Вот оно: p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)+p(n-12)+p(n-15)-... (Сумма обрывается, как только аргумент у p становится отрицательным.)

Но — если замкнутой формулы нет, то как можно (при желании) вычислять p(n) при большом n? Скажем, если перебор всех p(100)=190569292 разбиений числа n=100 ещё можно поручить компьютеру, то перебирать все p(1000)=24061467864032622473692149727991 разбиения числа n=1000 кажется не очень продуктивной идеей. Один "технический" способ решения этого вопроса — это находить больше. А именно, пусть p_k(n) — число разбиений n в сумму (невозрастающих) слагаемых, которые все не превосходят данного k. Тогда, с одной стороны, p(n)=p_n(n), а с другой — числа p_k(n) уже несложно ищутся рекурсивно, когда мы перебираем варианты для самого большого слагаемого: p_k(n) = \sum_{j=1}^k p_j(n-j).

Хорошей замкнутой формулы (как формула Бине для чисел Фибоначчи) для чисел разбиения нет; интересно, что их количество растёт быстрее, чем любой полином, но медленнее, чем экспонента: