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

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

Первая скобка отвечает за единицы, вторая за двойки, и так далее — так что (сгруппировав одинаковые слагаемые) разбиению 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).

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

=== Один из самых классических объектов в комбинаторике — это число разбиений p(n): сколькими способами число n можно представить в виде суммы натуральных слагаемых, если мы не различаем способы, отличающиеся только порядком слагаемых (или, что то же самое, предполагаем, что слагаемые упорядочены по неубыванию). Так, p(1)=1, p(2)=2 (потому что 2=1+1), p(3)=3 (потому что 3=2+1=1+1+1), p(4)=5 (потому что 4=3+1=2+2=2+1+1=1+1+1+1), p(5)=7 (упражнение), и так далее. Разбиению числа n можно сопоставить диаграмму Юнга: фигуру из клеток в первом квадранте, у которой число клеток в k-й строке это k-е слагаемое. Например, вот диаграмма Юнга для разбиения 15=6+5+3+1:

В ответ на мой вчерашний пост в личку пришло сразу несколько бдительных математиков с разумными комментариями, которые я выношу в этот мини пост. Конечно, число 42 я взял с потолка (ведь уже скоро день Полотенца), и вместо него могло быть другое число. И действительно, если немного подумать, то можно аналитически показать, что в n-мерном пространстве такую ось можно провести для любых n невырожденных точек (доказывается, например, построением базиса из векторов к этим точкам, а потом построением нужной оси в этом базисе). Спасибо, Федя, Витя и все остальные, кто пишет мне уточнения и комментарии к моим постам :)

(+Иллюстрация к поведению куба)

Напишу немного про проклятье размерности. Это термин, которым, в частности, называют странности многомерных пространств, от которых человеческая интуиция начинает давать сбои. Один популярный пример выглядит так: возьмём квадрат на плоскости и впишем в него круг. Ясно, что круг закроет большую часть площади квадрата. Дальше, возьмём куб и впишем в него шар. Опять же, шар займёт большую часть объёма куба. Но вот в четырёхмерном случае гиперсфера займёт меньше трети объёма гиперкуба, а при дальнейшем повышении размерности отношение их объёмов сходится к нулю. При этом евклидово расстояние от центра n-мерного куба до любого из его 2^n углов растёт как sqrt(n), т.е. неограниченно; а основной объём пространства (т.е., например, основная часть равномерно случайно взятых точек) внутри такого куба оказывается на расстоянии от центра с матожиданием sqrt(n/3) и с убывающей к нулю дисперсией. Короче, n-мерный куб — это очень странное место, с кучей углов и пустым центром. Другой пример — гипотеза Борсука о возможности разбиения n-мерного тела диаметром 1 на n+1 тел диаметром меньше 1. Она доказана для n<=3 и опровергнута для n>=64. Посредине — томящая неизвестность. Всё это обычно выглядит как игры разума, не отягощённого бытовыми мелочами, однако бум нейросетей принес нам популярность всяких многомерных эмбеддингов и представлений — слов, текстов или картинок, и там такие пакости случаются регулярно. Недавно, в одной из задач мне пришлось столкнуться с такой штукой: Возьмём, скажем, 100-мерное пространство и выберем в нём равномерно случайно из единичного гиперкуба 42 точки. Пронумеруем их в некотором случайном, но фиксированном порядке, от 1 до 42. Какова вероятность, что в нашем пространстве найдётся такая ось, в проекции на которую наши точки выстроятся в нужном порядке? Ответ: больше 99%. Кому интересно, можете посмотреть мой скрипт на питоне, которым это эмпирически можно проверить (работает довольно долго, решает системы линейных неравенств, пересекая полупространства для каждой пары точек).

Это, конечно, оффтопик для этого канала — но поздравляю всех с первым аппаратом тяжелее атмосферы, аэродинамически поднявшимся в воздух на другой планете! Формулировка про "тяжелее воздуха" тут точная — в атмосфере Венеры летали (надувавшиеся прямо в атмосфере после торможения) аэростатные зонды советских АМС Вега-1 и Вега-2. А без слова "аэродинамически" формально-верно из-за слова "планета", но всё-таки тогда стоило было бы вспомнить про Луну (откуда взлетали как Apollo, так и советские Луна-16, Луна-20, Луна-24, недавний китайский Чанъэ-5), да и с астероидов тоже были взлёты — можно вспомнить японские Хаябусу и Хаябусу-2, летящий сейчас OSIRIS-REx... А ещё этот вертолётик несёт на себе микроскопический кусочек ткани с того самого самолёта братьев Райт; жест совершенно символический — но очень красивый. Кадр из только что закончившейся прямой трансляции NASA : показания альтиметра (взлёт, зависание, посадка) + см. новость N+1. Момент полёта — https://youtu.be/p1KolyCqICI?t=2524

Присоединюсь к коллегам: задача очень хорошая, а послесловие про контекст действительно стоит посмотреть!