Разбиения чисел

Чтобы доказать, что количества элементов в двух множествах одинаковы, бывает удобно установить между ними взаимно-однозначное соответствие.

Пусть есть какое-то разбиение на различные слагаемые. Из него можно получить разбиение на нечётные слагаемые, если каждое чётное число разбивать на две половинки до тех пор, пока не останутся только нечётные.

Пример: 20 + 6 + 3 → 10 + 10 + 3 + 3 + 3 → 5 + 5 + 5 + 5 + 3 + 3 + 3.

А как по «нечетному» разбиению получить исходное «строгое»? Вот это и есть суть задачи...

Утверждение задачи впервые было доказано Леонардом Эйлером около 1740 года с помощью производящих функций.

Леонард Эйлер (1707–1783). Портрет работы Я. Э. Хандманна, 1753 г. Изображение с сайта ru.wikipedia.org

Теорема Эйлера. Количество разбиений числа N на попарно различные слагаемые («строгие разбиения») равно количеству разбиений N на нечётные слагаемые («нечётные разбиения»).

В подсказке был указан способ, позволяющий получить из любого строгого разбиения нечётное. Для этого каждое чётное число, входящее в разбиение на различные слагаемые, нужно было разделить пополам, то есть представить в виде суммы двух равных половинок. А затем повторять этот процесс до тех пор, пока чётных чисел не останется.

Например, из разбиения

Чтобы доказать взаимную однозначность такого соответствия, теперь нужно объяснить, как по нечётному разбиению (например, 15 + 13 + 9³ + 7 + 1¹³) восстановить исходное строгое. С теми нечётными числами, которые встречаются всего один раз, всё понятно — они были и в исходном разбиении. А вот из чего получилось 9³? Так как число повторений нечётно, то само число 9 в разбиении было. Кроме него, остаётся еще 9², которое могло быть получено только из числа 18. Итак, мы восстановили, что 9³ ← (9, 18). Подобным же образом можно последовательно разобраться и с 1¹³:

1¹³ ← (1, 2⁶) ← (1, 4³) ← (1, 4, 4²) ← (1, 4, 8).

Вы уже поняли закономерность? Она столь же проста, сколь и красива: каждый «показатель степени» записывается в виде суммы различных степеней двойки (то есть выписывается его двоичная запись), после чего каждой из имеющихся степеней соответствует своё слагаемое в исходном «строгом» разбиении. Это становится совсем понятным, если сообразить, что из одного чётного слагаемого в строгом разбиении могли получиться только 2, 4, 8, 16 и т. д. нечётных — то есть «вклад» каждого слагаемого в общее количество всегда является степенью двойки, а так как равных слагаемых нет, то все степени оказываются различными.

Джеймс Уитбред Ли Глейшер (1848–1928). Изображение с сайта ru.wikipedia.org

Это замечательное соответствие было придумано в конце XIX века английским математиком Джеймсом Уитбредом Ли Глейшером (увы, его научные результаты в основном касались областей математики, которые не изучаются ни в средней школе, ни даже в нематематических вузах, поэтому широкой публике он абсолютно неизвестен). Тем не менее он был удостоен двух очень значимых математических наград своего времени — медали де Моргана в 1908 году (это высшая награда Лондонского математического общества, присуждается раз в три года) и медали Сильвестра в 1913 году (высшая награда Лондонского королевского общества).

В задаче о нечетных разбиениях заслуга Глейшера в том, что он придумал не только новый подход к решению, но и дал замечательное обобщение задачи:

Теорема Глейшера. Количество разбиений целого числа N на части, не делящиеся на число d, равно количеству разбиений N на слагаемые, в которых никакая часть не повторяется d или более раз.

Но рассказ о соответствиях между нечётными и строгими разбиениями был бы заведомо неполон без упоминания другого замечательного соответствия между ними, придуманного Джеймсом Джозефом Сильвестром (тем самым, в честь которого названа упомянутая выше медаль).

Джеймс Джозеф Сильвестр (1814–1897). Изображение с сайта ru.wikipedia.org

Сильвестр был, по-видимому, первым математиком, который исследовал разбиения чисел на слагаемые с помощью клетчатых картинок. Впоследствии эти картинки получили название «диаграммы Юнга» или «диаграммы Феррерса» в честь двух других британских математиков, младших современников Дж. Сильвестра.

Пусть есть разбиение на нечётные слагаемые. Сильвестр предлагал нарисовать диаграмму, в которой этим слагаемым соответствуют горизонтальные ряды (строки), причем располагать эти ряды симметрично относительно центра (это можно сделать именно благодаря нечётности всех слагаемых, рис. 1). А для установления соответствия он рассматривал «крюки», которые на рисунке 1 изображены чередующимися цветными рядами. Первый крюк идет снизу по центральному ряду до верхней строки, а потом продолжается по этой строке вправо. Следующий крюк — по соседнему слева ряду снова до верхней строки, а затем по первой строке до конца влево. Потом — снова крюк справа, но уже до второй строки, и так далее. В итоге получается уже знакомое нам по соответствию Глейшера разбиение (18, 15, 13, 9, 8, 7, 4, 1). Не правда ли, красиво? К сожалению, столь же красивого обратного соответствия Сильвестр не дал. Вместо этого он просто привёл алгебраическое доказательство того, что такое соответствие является взаимно-однозначным.

Рис. 1.

К слову, Сильвестр не ограничился одним новым соответствием, а попутно в той же работе доказал и несколько других новых фактов про нечётные и строгие разбиения. В частности, он обнаружил соответствие между нечётными разбиениями, содержащими ровно k различных чисел, и разбиениями на различные числа, содержащими ровно k «цепочек» — подпоследовательностей из идущих подряд натуральных чисел. Это привело его к следующей теореме.

Теорема Сильвестра (1882). Количество разбиений числа N на нечётные части, среди которых ровно k различных чисел, равно количеству разбиений N на различные части, в которых встречаются ровно k цепочек.

Ясно, что исходный результат Эйлера получается в качестве следствия из теоремы Сильвестра — простым сложением по всем k.

Однако математика не стоит на месте, и красивое соответствие все-таки было найдено, причём совсем недавно, в самом конце ХХ века. Сделали это два корейских математика Ким Донсу и И Эчжа (в тот момент второй из них был еще студентом, а ныне он — профессор в Университете штата Пенсильвания). Я приведу картинку, взятую из их статьи A note on partitions into distinct parts and odd parts, и кратко прокомментирую ее, предоставляя возможность читателю самостоятельно додумать детали.

Нарисуем картинку разбиения на различные части, начав с самых маленьких частей, то есть с единицы: 1 + 4 + 7 + 8 + 9 + 13 + 15 + 18 (рис. 2). Если количество частей нечётно, то в качестве самой маленькой части добавим 0. Первую часть поместим в первую строку, вторую — в строку под ней, причем выровняв ее по левому краю первой строки. Третью часть поместим в третью строку, но выровняем ее со второй строкой по правому краю, и так далее, чередуя выравнивание по левому и по правому краям. Так как все части различны, то в результате все вертикальные края (и левые, и правые), кроме последнего, будут иметь высоту 2.

Рис. 2.

Кроме того, нарисуем жирную вертикальную черту — разделитель — на расстоянии от правого края, равном знакочередующейся сумме частей

Тогда все столбцы правее разделителя содержат нечётное число клеток (ведь каждая вертикаль состоит из одной нижней строки и чётного числа других строк) и могут рассматриваться как сумма нечётных слагаемых:

(эти числа подписаны в первом ряду под диаграммой, справа от разделителя). При этом все последовательные нечётные числа от 1 до 7 встречаются хотя бы один раз. Следовательно, к 1 можно прибавить число клеток в паре нижних строк слева от разделителя (то есть 14), к 3 — число клеток в паре следующих строк (10), к 5 — клетки из следующей пары (8), а к 7 — клетки последней пары строк (2). Эти слагаемые подписаны во второй строке под диаграммой. Наконец, в третьей строке выписаны суммы первой и второй строки — тоже нечётные, поскольку вся вторая строка состоит из чётных чисел. Ясно, что каждая клетка диаграммы учтена ровно один раз — клетки правее разделителя вошли в слагаемые первой строки. А клетки левее разделителя вошли в слагаемые второй строки. Тем самым мы получили соответствие между различными слагаемыми и нечётными слагаемыми, причём — то же самое соответствие, которое было предложено Сильвестром.

А как построить обратное соответствие? Метод Кима – И здесь во многом повторяет способ Сильвестра, но выглядит, пожалуй, даже естественнее.

Выпишем убывающую последовательность из чисел нечётного разбиения (a₁ = 15, a₂ = a₃ = 13, a₄ = 9, a₅ = a₆ = 7, a₇ = a₈ = a₉ = 3, a₁₀ = a₁₁ = 1) и будем от первого члена отнимать 1, от второго — 3, от третьего — 5, и так далее до тех пор, пока разности будут положительны. То есть запишем равенства 15 = 1 + 14, 13 = 3 + 10, 13 = 5 + 8, 9 = 7 + 2. Это сразу даст нам нужное разбиение третьей строчки под диаграммой на первую и вторую. Затем все числа первой строчки перенесём в диаграмму справа от разделителя, а каждое чётное число второй строчки «уложим» в две строки слева от разделителя. В результате получим диаграмму, в которой нижняя строка будет самой длинной, а каждая следующая строка будет короче предыдущей. Суммируя клетки этой диаграммы по строкам, получим разбиение на различные слагаемые.

Результат Кима – И — даже при том, что они фактически просто переформулировали Сильвестра — использует понятие разделителя, которого не было в оригинале. А значит, тоже позволяет доказать более сильный факт. Но удивительно даже не это, а то, что этот факт был открыт на несколько лет раньше, чем появилась красивая картинка от корейцев!

Теорема о разбиениях на d нечётных частей (М. Буске-Мело, К. Эриксон, 1997). Количество разбиений числа N на попарно различные части, имеющие знакочередующуюся сумму d, равно количеству разбиений N на d нечётных частей.