И обратно — если диагональ строго меньше наименьшего слагаемого, то отрежем её и перенесём эти клетки вниз, в качестве нового наименьшего слагаемого.
Собственно — вот скриншот из лекции Е. Ю. Смирнова из его курса по перечислительной комбинаторике на Coursera (Image credit: Coursera + HSE + E. Smirnov)
И вот так эта биекция и работает — за исключением тех случаев, когда диагональ доходит аж до самого наименьшего слагаемого, причём или равна ему по длине, или на 1 меньше: тогда её отрезать и убрать вниз не получится.
А это и есть числа в правой части пентагональной теоремы: это же и есть почти совсем правильные пятиугольники, только нарисованные на квадратной решётке, так что получается квадрат + треугольник.
И видно, почему между парами чисел действительно расстояния совпадают с номером пары. Давайте я покажу ещё один кадр из того же видео Mathologer-а:
Image credit: Mathologer, "The hardest "What comes next?" (Euler's pentagonal formula)".
Коллеги напоминают про обзор Игоря Пака, «Partition bijections, а Survey» — и я присоединяюсь к рекомендации (это и вообще очень интересный обзор, и там есть эта биекция).
Telegram
Непрерывное математическое образование
https://www.math.ucla.edu/~pak/papers/psurvey.pdf
в связи с биективным доказательство пентагональной теоремы Эйлера, хочется напомнить еще про обзор «Partition bijections, а Survey» Игоря Пака
в связи с биективным доказательство пентагональной теоремы Эйлера, хочется напомнить еще про обзор «Partition bijections, а Survey» Игоря Пака
Математические байки
Photo
Да, я не сказал — эта инволюция именная, и называется инволюцией Франклина. Вот тут — в Comptes Rendus — в 1881 году она опубликована; а вот 80-страничная статья J. J. Sylvester and F. Franklin, American Journal of Mathematics, 1882, Vol. 5, No. 1 (1882), pp. 251-330 с отдельно замечательным названием:
Несколько относящихся к биекции Франклина кусочков из этой большой статьи:
Математические байки
Но — если замкнутой формулы нет, то как можно (при желании) вычислять p(n) при большом n? Скажем, если перебор всех p(100)=190569292 разбиений числа n=100 ещё можно поручить компьютеру, то перебирать все p(1000)=24061467864032622473692149727991 разбиения…
Да, ещё — к рекуррентной формуле для 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 обратно к последнему добавить нельзя).
Тогда:
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 обратно к последнему добавить нельзя).