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

Доказал Эйлер её, собственно, далеко не сразу. В 1740-м, заинтересовавшись этой темой после письма Филиппа Науде (Philippe Naudé) — где был, среди прочего, вопрос "сколькими способами можно представить 50 в виде суммы 7 различных слагаемых" — Эйлер её открывает экспериментально. Упоминает в том же 1740-м в письме Даниилу Бернулли, и включает в свою статью "Observationes analyticae variae de combinationibus", которую подаёт в 1741 году. Вот тут можно посмотреть на скан, видимо, оригинального издания; вот тут — на неё в его полном собрании сочинений, тоже на латыни; а вот тут — на английский перевод. Кстати — выхода статьи ему пришлось ждать 10 лет(!):

А ещё можно задуматься — если инволюцию Франклина придумал аж в 1881-м Франклин, то как же пентагональную теорему (больше, чем на 120 лет раньше!) доказывал сам Эйлер? И там всё интересно! Собственно, когда я начинал эту байку записывать, я ответа не знал — спасибо Феде Петрову за рассказ и за ссылки!

Мы получаем сумму слагаемых вида p(n-s) со знаками. Причём, если раскрыть все скобки, то p(n-s) появляется по одному разу на способ его представить в виде суммы различных слагаемых: разница аргументов p(.,.) на каждом шаге либо сохраняется, либо уменьшается на j-1 (а на первом шаге, при сумме по j, равна n-j). При этом каждое увеличение на j-1 меняет знак. Вот и получается, что каждое p(n-s) в итоге участвует с весом, равным числу способов представить s как сумму нечётного числа различных слагаемых минус число способов как сумму чётного их числа.

Поэтому слагаемые p(n,1), p(n,2), p(n,3),..., составляющие p(n), переписываются как p(n,1) =p(n-1), p(n,2)=p(n-1,1)-p(n-2,1) =p(n-2)-p(n-3), p(n,3)=p(n-1,2)-p(n-3,2)=(p(n-2,1)-p(n-3,1))-(p(n-4,1)-p(n-5,1)) =p(n-3) - p(n-4) -p(n-5) + p(n-6), и так далее.

Да, ещё — к рекуррентной формуле для p(n) можно прийти и "лобовым" подходом (via). А именно, давайте опять посмотрим на более подробную информацию, но на этот раз ограничим не наибольшее слагаемое, а зафиксируем наименьшее: пусть p(n,j) это число разбиений n с наименьшим слагаемым, равным j. Тогда: p(n)=p(n+1,1) — потому что можно к любому разбиению дописать 1; иными словами, p(n,1)=p(n-1). p(n)=\sum_{j=1}^n p(n,j) — потому что последнее слагаемое должно быть хоть каким-нибудь. А дальше можно делать индукцию "уменьшением j": p(n,j) = p(n-1,j-1) - p(n-j,j-1), первое — это если мы на 1 уменьшили наименьшее слагаемое j, а второе — это лишние слагаемые, которые мы при этом посчитали (предыдущее слагаемое это тоже (j-1), а не хотя бы j, так что 1 обратно к последнему добавить нельзя).

(и — знакомые формы!)

Несколько относящихся к биекции Франклина кусочков из этой большой статьи:

Да, я не сказал — эта инволюция именная, и называется инволюцией Франклина. Вот тут — в Comptes Rendus — в 1881 году она опубликована; а вот 80-страничная статья J. J. Sylvester and F. Franklin, American Journal of Mathematics, 1882, Vol. 5, No. 1 (1882), pp. 251-330 с отдельно замечательным названием:

Да, пентагональная теорема сама по себе там тоже, конечно, есть.

И иллюстрирующая это картинка оттуда же —

I. Pak, «Partition bijections, а Survey»

Коллеги напоминают про обзор Игоря Пака, «Partition bijections, а Survey» — и я присоединяюсь к рекомендации (это и вообще очень интересный обзор, и там есть эта биекция).

Image credit: Mathologer, "The hardest "What comes next?" (Euler's pentagonal formula)".

И видно, почему между парами чисел действительно расстояния совпадают с номером пары. Давайте я покажу ещё один кадр из того же видео Mathologer-а:

Или так —