Статья: Разбиение чисел
Ф. В. Вайнштейн
Разбиением называется представление натурального числа в виде суммы натуральных слагаемых, а сами слагаемые — частями разбиения. Порядок слагаемых не играет роли; так разбиения 3=1+2 и 3=2+1 не различаются. Мы будем записывать разбиения, перечисляя их части через запятую в невозрастающем порядке. Например, разбиение 4=2+1+1 записывается как (2, 1, 1).
Пусть p(n) обозначает количество всех разбиений натурального числа n. Для небольших n легко вычислить p(n), просто выписав все разбиения. Например, p(5) = 7. Вот все 7 разбиений числа 5: (5), (4, 1), (3, 2), (3, 1, 1), (2, 2, 1), (2, 1, 1, 1), (1, 1, 1, 1, 1). Однако получить таким способом, скажем, p(100) = 190 569 292 без помощи компьютера немыслимо. Между тем p(100) было известно ещё в XIX веке. Мы познакомим вас со многими интересными свойствами разбиений и научим находить p(n), не выписывая всех разбиений числа n.
Задача вычисления p(n) имеет почтенный возраст. Впервые она была сформулирована Лейбницем в 1654 году, а в 1740 — предложена немецким математиком Филиппом Ноде Леонарду Эйлеру. Занимаясь разбиениями, Эйлер открыл целый ряд их свойств, среди которых главное место занимала знаменитая «пентагональная теорема». С исследований Эйлера начинается история теории разбиений, в развитии которой принимали участие крупнейшие математики последующих поколений.
Две теоремы Эйлера
Изучение функции p(n) Эйлер начинает с рассмотрения бесконечного произведения
(1 + x + x2 + ...)(1 + x2 + x4 + ...) ... (1 + xk + x2k + ...) ...
Каждый член произведения получается в результате умножения мономов, взятых по одному из каждой скобки. Если в первой скобке взять xm1, во второй — x2m2 и т.д., то их произведение будет равно xm1+2m2+3m3+.... Значит, после раскрытия скобок получится сумма мономов вида xm1+2m2+3m3+....
Сколько раз в этой сумме встретится хn? Столько, сколькими способами можно представить n как сумму m1 + 2m2 + 3m3 + ... Каждому такому представлению отвечает разбиение числа n на m1 единиц, m2 двоек и т.д. Так получаются все разбиения, так как каждое из них, конечно, состоит из нескольких единиц, нескольких двоек и т.д. Поэтому коэффициент при xn равен числу разбиений p(n).
Посмотрим теперь на выражения в скобках. Каждое из них — бесконечная геометрическая прогрессия. По формуле суммирования
| 1 + x + x2 + x3 + ... = |
1 1 – x |
, |
| 1 + x2 + x4 + x6 + ... = |
1 1 – x2 |
и т.д. Теперь наш результат можно записать так:
|
(1) |
Эта формула была открыта Эйлером в 1740 году. Ряд, стоящий в левой части, называется производящей функцией последовательности чисел p(0), p(1), p(2), ... Производящая функция позволяет компактно записать информацию о последовательности, хотя извлечение этой информации из производящей функции порой требует большого искусства. Сейчас вы увидите, как это делал Эйлер.
Обозначим через d(n) количество разбиений числа n на различные слагаемые, а через l(n) — на нечётные. Например, среди выписанных выше разбиений числа 5 различные части имеют (5), (4, 1) и (3, 2), а нечётные — (5), (3, 1, 1) и (1, 1, 1, 1, 1). Значит, d(5) = l(5) = 3.
Такие же рассуждения, как при выводе формулы (1), позволяют выписать производящие функции последовательностей d(n) и l(n):
| d(0) + d(1) x + d(2) x2 + d(3) x3 + ... = (1 + x)(1 + x2)(1 + x3) ... , | ||
| l(0) + l(1) x + l(2) x2 + l(3) x3 + ... = |
1 (1 – x)(1 – x3)(1 – x5) ... |
. |
Упражнение 1. Докажите эти формулы.
Воспользуемся формулой
| 1 + xk = |
1 – x2k 1 – xk |
, |
верной при всех k:
| (1 + x)(1 + x2)(1 + x3) ... = |
1 – x2 1 – x |
· |
1 – x4 1 – x2 |
· |
1 – x6 1 – x3 |
· ... |
В правой части равенства все числители сокращаются со знаменателями, содержащими x в чётной степени. Поэтому в знаменателе останутся только сомножители вида 1 – x2k–1. Итак,
|
(2) |
Значит, производящие функции последовательностей d(n) и l(n) совпадают! Мы доказали теорему Эйлера: d(n) = l(n). Это доказательство хорошо иллюстрирует силу метода производящих функций.
Но вернёмся к вычислению p(n). Изучая производящую функцию последовательности p(n), Эйлер сосредоточил внимание на произведении (1–x)(1–x2)(1–x3)..., т.е. на знаменателе правой части формулы (1). Раскрывая в нём скобки, Эйлер получил удивительный результат:
(1 – x)(1 – x2)(1 – x3) ... = 1 – x – x2 + x5 + x7 – x12 – x15 + x22 + x26 – x35 – x40 + ...
Показатели в правой части — пятиугольные числа, т.е. числа вида (3q2 ± q)/2, а знаки при соответствующих мономах равны (–1)q. Исходя из этого наблюдения, Эйлер предположил, что должна быть верна
Пентагональная теорема:
| ∞ | ∞ | ||
| ∏ | (1 – xk) = | ∑ | (–1)qx(3q²+q)/2. |
| k=1 | q=–∞ |
Пентагональная теорема оказалась «крепким орешком» — Эйлер сумел доказать её лишь 14 лет спустя. Эта теорема позволяет сравнительно просто вычислять значения p(n). Вот как это делается.
Умножим обе части равенства (1) на
| ∞ | |
| ∏ | (1 – xk) |
| k=1 |
и воспользуемся пентагональной теоремой:
( p(0) + p(1) x + p(2) x2 + ...)(1 – x – x2 + x5 + x7 – x12 – x15 + ...) = 1.
Раскрыв скобки в левой части, получим, что коэффициенты при ненулевых степенях x равны нулю. Отсюда мы получаем замечательную формулу Эйлера, позволяющую последовательно находить числа p(n):
| p(n) = p(n–1) + p(n–2) – p(n–5) – p(n–7) + ... + (–1)q+1 | ( | p | ( | n– |
3q² – q 2 |
) | + p | ( | n– |
3q² + q 2 |
) | ) | . |
(Мы считаем, что p(n) = 0 при n < 0.)
Упражнение 2. Найдите p(10).
Пользуясь формулой Эйлера, можно составить таблицу значений p(n) для n ≤ 200, что и проделал в начале XX века известный английский специалист по комбинаторике майор Мак-Магон. В то время это была наиболее полная таблица чисел p(n).
Итак, мы сформулировали две теоремы, одну из которых — d(n) = l(n) — доказали. Согласитесь, что при всей элегантности этого доказательства, оно всё же оставляет чувство неудовлетворённости. Два множества разбиений — на нечётные и на неравные части — неожиданно оказались состоящими из одинакового числа элементов, но причина этого равенства осталась скрытой от нас. Хотелось бы думать, что существует какой-то естественный способ каждому элементу одного множества ставить в соответствие элемент другого.
Соответствия Глэйшера и Сильвестра
Приведём ещё два доказательства теоремы Эйлера: d(n) = l(n).
Первое соответствие между разбиениями на различные слагаемые и разбиениями на нечётные слагаемые строится так:
Каждую часть разбиения нужно поделить на максимально возможную степень двойки. Частное будет нечётным числом и нужно включить это число в новое разбиение столько раз, каков делитель.
Например, разбиению (6, 2, 1) соответствует разбиение (3, 3, 1, 1, 1). Это остроумное соответствие придумано в конце XIX века английским математиком Дж. Глэйшером.
Чтобы доказать взаимную однозначность соответствия Глэйшера, достаточно построить обратное соответствие между разбиениями с нечётными частями и разбиениями с неравными частями. Вот это соответствие:
Пусть в разбиении некоторая нечётная часть r встречается k раз. Запишем k в виде суммы различных степеней двойки
k = 2a1 + 2a2 + ..., a1 > a2 > ...
и заменим (..., r, r, ..., r, ...) (k раз) на (..., 2a1r, 2a2r, ...). То, что получится, будет разбиением с различными частями.
Например, разбиение (5, 5, 5, 1, 1, 1, 1, 1, 1) соответствует разбиению (10, 5, 4, 2), поскольку число пятёрок равно 3 = 21 + 20, а число единиц равно 6 = 22 + 21.
Упражнения
3. Докажите, что в результате второго преобразования получается разбиение с различными частями.
4. Докажите, что если сначала выполнить преобразование Глэйшера, а затем обратное, то получится исходное разбиение.
Существует другое, не менее интересное и совершенно неожиданное доказательство теоремы Эйлера, принадлежащее американскому математику XIX века Дж. Сильвестру. Вот конструкция Сильвестра: пусть имеется разбиение числа n на нечётные части: (2k1+1, 2k2+1, ..., (2kq+1), где k1 ≥ k2 ≥ ... ≥ kq. На листе клетчатой бумаги в некотором её узле поставим точку x1. Справа от x1, поставим в узлах k1 точек и столько же точек поставим в узлах, расположенных под точкой x1. Затем проделаем то же самое с числом k2, взяв в качестве исходной точку x2, расположенную в следующем за точкой x1 по диагонали направо вниз узле, и т.д., пока не дойдём до числа kq.
Например, разбиению на нечётные части (9, 9, 5, 1, 1) числа 25 будет отвечать картинка, изображённая на рис. 1.
|
Рис. 1. |
Рис. 2. |
Она состоит из симметричных относительно диагонали уголков, так что в самом верхнем уголке 2k1+1 точек, в следующем 2k2+1 точек и т.д., а всего точек будет n. Теперь проведём на той же картинке линии так, как показано на рис. 2, подсчитаем количество точек на каждой из этих линий и образуем из полученных таким образом чисел разбиение. Оказывается, все части этого разбиения различны.
Упражнение 5. Докажите это утверждение.
В нашем примере получится разбиение (9, 6, 5, 4, 1). Подумайте, как построить по разбиению на различные части разбиение на нечётные, т.е. восстановить по такому разбиению исходную симметричную картинку.
Отступление: решение задачи М1065
В этом разделе используется более сложная техника, чем в остальной части статьи. При желании вы можете пробежать его, не вникая в детали, и продолжить чтение со следующего раздела. Итак, займёмся решением задачи М1065 из «Задачника «Кванта» (1987, № 9). Напомним её формулировку.
Будем рассматривать векторы (x, y) с целыми неотрицательными координатами, причём хотя бы одна из координат отлична от 0. Назовём такой вектор образующим, если |x–y| = 1.
а) Докажите, что рассматриваемый вектор (x, y) можно представить в виде суммы различных образующих (или он сам — образующий) тогда и только тогда, когда величина k(x, y) = x + y – (x–y)2 неотрицательна.
б) Докажите, что число N(x, y) различных (с точностью до порядка) представлений вектора (x, y) в виде суммы различных образующих зависит только от числа k = k(x, y). Найдите N(13, 18).
Решение задачи начнём с того, что найдём общий вид целочисленных решений неравенства k(x, y) ≥ 0. Числа x+y и x–y имеют одинаковую чётность, поэтому k(x, y) является чётным при любых целых x, y. Следовательно, для любого целого m≥0 достаточно найти целочисленные решения уравнения x + y – (x–y)2 = 2m. Положим x–y = q. Тогда x+y = 2m+q2. Из этих двух равенств немедленно получаем:
|
(3) |
где q — любое целое число, а m ≥ 0.
Смысл чисел m и q станет более наглядным, если представлять себе векторы вида (3) при m=0 как точки с целыми координатами параболы k(x, y) = 0, лежащей в плоскости (x, y). (Вы понимаете, почему это парабола?) Тогда полученные нами целочисленные решения неравенства k(x, y) ≥ 0. показывают, что все точки с целыми координатами, лежащие на параболе k(x, y) = 0 и внутри неё, получаются сдвигами целых точек этой параболы на векторы (m, m) (рис. 3). Удобно считать, что число m (m=0, 1, 2, ...) — номер параболы, на которой лежит точка (x, y), a q = x–y = 0, ±1, ±2, ... — номер точки на этой параболе.
Рис. 3.
Поскольку условия задачи симметричны относительно перестановки координат векторов, достаточно доказать все утверждения для таких векторов (x, y), что x ≥ y, т.е. для векторов вида (3) с q ≥ 0.
Докажем достаточность условия в пункте а) задачи. По формуле суммы арифметической прогрессии
| 1 + 2 + ... + (q–1) + m + q = m + |
q(q + 1) 2 |
; |
| 0 + 1 + ... + (q–2) + m + (q–1) = m + |
q(q – 1) 2 |
. |
Поэтому формулы
(x, y) = (1, 0) + (2, 1) + ... + (q–1, q–2) + (m+q, m+q–1) при q>0
и
(m, m) = (1, 0) + (m–1, m) при q=0, m>0
дают представления (x, y) в виде суммы различных образующих.
Доказать необходимость условия тоже несложно. Пусть
(x, y) = (r1, r1–1) + ... + (ra, ra–1) + (s1, s1+1) + ... + (sb, sb+1)
— представление вектора (x, y) с x ≥ y в виде суммы различных образующих, где
|
r1 > r2 > ... > ra > 0, s1 > s2 > ... > sb ≥ 0. |
(4) |
Для такого вектора
x = r1 + ... + ra + s1 + ... + sb,
y = r1 + ... + ra – a + s1 + ... + sb + b,
поэтому x–y = a–b. Положим q = x–y и
m = (r1–q) + (r2–(q–1)) + ... + (rq–1) + rq+1 + ... + ra + s1 + ... + sb =
| = x – |
q(q + 1) 2 |
= |
x + y 2 |
+ |
x – y 2 |
– |
q(q + 1) 2 |
= |
x + y 2 |
– |
q² 2 |
(здесь мы снова воспользовались формулой суммы арифметической прогрессии). Из неравенств (4) следует, что rq ≥ ra ≥ 1, rq–1 ≥ 2, rq–2 ≥ 3, ... и вообще rk ≥ q–k+1. Поэтому m ≥ 0, т.е. (x, y) — вектор вида (3), что и требовалось доказать.
В геометрических терминах утверждение б) означает, что число N(x, y) зависит лишь от номера m параболы и не зависит от номера q точки на параболе.
Пусть T(m, q) — множество представлений вектора (3) в виде суммы различных образующих и t(m, q) — число таких представлений. Задача будет решена, если мы докажем, что для любого целого q имеет место равенство t(m, q) = t(m, q–1) (это и значит, что t(m, q), а вместе с ним N(x, y), не зависит от q). Мы отождествили выше множество T(m, q) с множеством таких пар последовательностей, удовлетворяющих неравенствам (4), что
| r1 + ... + ra + s1 + ... + sb = m + |
q(q + 1) 2 |
при q = a–b. |
Такую пару мы будем записывать в виде (r1, ..., ra | s1, ..., sb).
Рассмотрим отображение φ множества T(m, q) в множество T(m, q–1), заданной формулой
| φ(r1, ..., ra | s1, ..., sb) = |
|
|
Упражнение 6. Проверьте, что φ(r1, ..., ra | s1, ..., sb) T(m, q–1).
Чтобы доказать, что φ — взаимно однозначное отображение, построим обратное отображение ψ: T(m, q–1) → T(m, q), прочитав правило, задающее φ, слева направо:
| ψ(r1, ..., ra | s1, ..., sb) = |
|
|
Построенные отображения взаимно обратны, поэтому φ — взаимно однозначное соответствие. Значит, t(m, q) = t(m, q–1), что и утверждалось.
Чтобы научиться вычислять значения N(x, y), установим связь между числами t(m, q) и p(m).
Утверждение: t(m, q) = p(m).
Рис. 4.
Мы уже знаем, что t(m, q) = t(m, 0), поэтому достаточно доказать, что t(m, 0) = p(m). Воспользуемся простым и полезным графическим средством, называемым диаграммой Юнга разбиения. Рассмотрим, например, разбиение (6, 4, 4, 2, 1). Его диаграмма Юнга изображена на рис. 4 (в первой строчке стоят 6 точек, во второй — 4, в третьей — 4, в четвёртой — 2, в пятой — 1). Всякое разбиение можно изобразить в виде диаграммы Юнга и по всякой диаграмме Юнга — записать разбиение.
Проведём на диаграмме Юнга диагональ — чёрная линия на рис. 4. Пусть r1 — число точек в первой строке, лежащих на диагонали и справа от неё, r2 — число точек второй строки, лежащих на диагонали и справа от неё, и т.д.; s1 — число точек первого столбца под диагональю, s2 — число точек второго столбца под диагональю и т.д. Поставим в соответствие диаграмме Юнга, изображающей разбиение числа m, пару последовательностей
(r1, r2, ... | s1, s2, ...),
r1 + r2 + ... + s1 + s2 + ... = m,
т.е. элемент множества T(m, 0). Например, диаграмме на рис. 4 соответствует пара (6, 3, 2 | 4, 2, 0). Зная пару последовательностей, можно легко восстановить диаграмму Юнга. Следовательно, мы установили взаимно однозначное соответствие между множеством разбиений и множеством T(m, 0). Утверждение доказано.
Теперь ничего не стоит ответить и на последний вопрос задачи — о значении N(13, 18). Поскольку 13 = 3+5·4/2, 18 = 3+6·5/2, точка (13, 18) лежит на третьей параболе. Значит, N(13, 18) = t(3, 0) = p(3) = 3.
Следующие упражнения — на применение диаграмм Юнга.
Упражнения
7. Число разбиений n не более чем с k частями, равно числу разбиений n с частями, не превосходящими k. Подсказка: отразите диаграмму Юнга относительно диагонали.
8. Число разбиений n с различными нечётными частями равно числу разбиений n, диаграмма Юнга которых симметрична относительно диагонали. Подсказка: вспомните соответствие Сильвестра.
Формула Гаусса–Якоби
Решая задачу М1065, мы проделали большую работу. Нельзя ли снова воспользоваться производящими функциями и извлечь из равенства t(m, q) = p(m) какое-нибудь красивое тождество?
N(x, y) — это число способов, которыми можно представить вектор (x, y) как сумму различных образующих вида (k, k–1) и (k–1, k). Рассуждая так же, как при выводе формулы производящей функции числа разбиений с различными частями, мы запишем производящую функцию для N(x, y) (это ряд от двух переменных u и v):
| ∞ | ∞ | ||
| ∏ | (1 + uk–1 vk)(1 + uk vk–1) = | ∑ | N(x, y)ux vy. |
| k=1 | x,y=0 |
Поскольку N(x, y) = t(m, q), где x = m + q(q+1)/2, y = m + q(q–1)/2, равенство можно продолжить:
| ∞ | ∞ | |||||
| = | ∑ | ∑ | t(m, q)um vm | uq(q+1)/2 vq(q–1)/2. | ||
| q=–∞ | m=0 |
Воспользуемся теперь тем, что t(m, q) = p(m) и продолжим равенство:
| ∞ | ∞ | |||||
| = | ∑ | ∑ | p(m)um vm | uq(q+1)/2 vq(q–1)/2. | ||
| q=–∞ | m=0 |
Ряд, стоящий в скобках, — производящая функция чисел разбиения p(m), которую мы знаем (формула (1)), поэтому продолжаем:
| ∞ | ∞ | |||
| = | ∏ | (1 – uk vk)–1 | ∑ | uq(q+1)/2 vq(q–1)/2. |
| k=1 | q=–∞ |
Теперь приравняем левую часть первого и правую часть последнего равенства, умножив обе части на ∏ (1–uk vk). Получим окончательный результат:
| ∞ | ∞ | ||
| ∏ | (1 + uk–1 vk)(1 + uk vk–1)(1 – uk vk) = | ∑ | uq(q+1)/2 vq(q–1)/2. |
| k=1 | q=–∞ |
Это тождество — цель наших преобразований. Оно называется формулой Гаусса–Якоби. Из этого замечательного тождества с двумя переменными можно получить много разных тождеств с одной переменной.
Упражнение 9. Подставьте в формулу Гаусса–Якоби u = –t, v = –t2 и получите пентагональную теорему Эйлера.
Теперь подставим в формулу Гаусса–Якоби u = v = – t. В левой части получится:
| ∞ | ∞ | ∞ | |||
| ∏ | (1 – t2k–1)2 (1 – t2k) = | ∏ | (1 – t2k–1) | ∏ | (1 – tk). |
| k=1 | k=1 | k=1 |
Заменяя произведение ∏ (1 – t2k–1) на ∏ (1 + tk)–1 по формуле (2), мы преобразуем левую часть в
|
(1 – t)(1 – t2)(1 – t3) ... (1 + t)(1 + t2)(1 + t3) ... |
. |
Правая часть формулы Гаусса–Якоби при подстановке u = v = – t превращается в
| ∞ | |
| ∑ | (–1)q² tq², |
| q=–∞ |
и мы получаем следующую формулу:
|
(1 – t)(1 – t2)(1 – t3) ... (1 + t)(1 + t2)(1 + t3) ... |
= 1 – 2t + 2t4 – 2t9 + 2t16 – ... |
Подстановка u = t, v = 1 в формулу Гаусса–Якоби аналогичным образом приводит к формуле:
|
(1 – t2)(1 – t4)(1 – t6) ... (1 – t)(1 – t3)(1 – t5) ... |
= 1 + t + t3 + t6 + t10 + ... |
Эти две формулы получены Гауссом. Нечего и говорить, что это удивительно красивые формулы!
Тождества Роджерса–Рамануджана
В заключение я хочу познакомить вас с двумя знаменитыми тождествами теории разбиений, для которых до сих пор не найдено прозрачных доказательств, хотя эта задача и по сей день остаётся в сфере интересов многих математиков.
Первое тождество. Число разбиений натурального числа п, в которых разность между любыми двумя частями превосходит единицу, равно числу разбиений числа п на части, дающие при делении на 5 остаток 1 или 4.
Второе тождество. Число разбиений натурального числа п, в которых разность между любыми двумя частями и каждая часть превосходят единицу, равно числу разбиений числа п на части, дающие при делении на 5 остаток 2 или 3.
Конечно, закономерность, утверждаемая этими тождествами, в высшей степени красива и нетривиальна, и неудивительно, что крупнейший английский математик начала XX века Г. Харди, узнавший о них из письма Рамануджана, датированного 16 января 1913 года, пришёл в восхищение. *)
При чтении этой статьи у вас, может быть, сложилось впечатление, будто теория разбиений напоминает кунсткамеру, в которую заботливо собраны различные экзотические экспонаты, никак или почти никак между собой не связанные. До недавнего времени так оно и было. Ситуация коренным образом изменилась лишь в 70-х годах XX века, когда английскому математику Яну Макдональду удалось найти единый подход к доказательству большого класса тождеств теории разбиений и открыть много новых, объединив их в стройную теорию (тождество Гаусса–Якоби включается в неё). **) Для тождеств Роджерса–Рамануджана и многих аналогичных тождеств общего подхода не найдено, хотя в последнее время и появились алгебраические методы их доказательств. Так что, понимание истинной природы этих тождеств, вероятно, ещё впереди.