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

Собственно — вот скриншот из лекции Е. Ю. Смирнова из его курса по перечислительной комбинаторике на Coursera (Image credit: Coursera + HSE + E. Smirnov)

И обратно — если диагональ строго меньше наименьшего слагаемого, то отрежем её и перенесём эти клетки вниз, в качестве нового наименьшего слагаемого.

получится вот такое:

После чего, если самое маленькое слагаемое не превосходит этой диагонали — отрежем его и перенесём к диагонали, по одной клетке сверху. Скажем, из такого разбиения —

И инволюция эта очень простая. Давайте возьмём какое-нибудь разбиение n в сумму различных слагаемых и отметим на его диаграмме Юнга как самое маленькое слагаемое, так и "последнюю диагональ":

И очень естественная идея — если нужно доказывать, что два множества одной мощности, то можно попробовать между ними построить биекцию (а если множества отличаются на 1 по мощности — то какой-то элемент из области определения выпустить). Именно так это доказательство и проводится — а именно, на множестве разбиений n на различные слагаемые строится инволюция (отображение, в квадрате равное тождественному), гарантированно меняющая чётность числа слагаемых. И иногда (как раз для тех самых n) определённая не на всех разбиениях, а на всех, кроме одного.

Итак, пентагональная теорема Эйлера сформулирована. Осталось её доказать. Я знаю два её доказательства. Первое чуть более "лобовое": давайте раскроем все скобки в левой части — в произведении всех (1-q^j), и посмотрим, из чего складывается коэффициент при q^n. А именно — вклад получается из разложения n в сумму различных слагаемых. Причём из-за минусов перед каждым q^j разложение входит со знаком, отвечающим чётности числа слагаемых. Поэтому в чуть-чуть изменённом виде пентагональная теорема звучит так: для всех n, кроме появляющихся в правой части тождества, число N_E(n) способов разбить n в сумму чётного числа различных слагаемых совпадает с числом N_O(n) способов разбить в сумму нечётного числа различных. А для появляющихся в правой части N_O(n) и N_E(n) отличаются на 1 (в нужную сторону).

Да, пока я не забыл — Mathologer в своём ролике угадывает всю последовательность через последовательные разности, раскрашивая их в два цвета. Тоже очень наглядно!

Вот из-за этих пятиугольных чисел соответствующее утверждение о том, как устроен ряд Q, обратный к производящей функции P, и называется пентагональной теоремой Эйлера. Я продолжу цитировать брошюру Е. Ю. Смирнова (собственно, из неё — и из его курса в ЛШСМ — я в первый раз этот сюжет и узнал):

А как устроена последовательность первых чисел в паре? 1, 5, 12, 22... Давайте я тут процитирую дубнинскую брошюру Е. Ю. Смирнова, "Диаграммы Юнга, плоские разбиения и знакочередующиеся матрицы":

Если посмотреть на разницу между числами пар, идущих с одинаковым знаком, то закономерность бросается в глаза: 2-1= 1 7-5= 2 15-12= 3 26-22= 4.

Остаётся понять, что же это за последовательность — 1, 2, 5, 7, 12, 15, 22, 26, ...

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

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

Знакомая последовательность? И уже понятно, откуда взялась рекуррентная формула выше: это мы записали произведение 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.