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

Рис. 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 года, пришёл в восхищение. *)
При чтении этой статьи у вас, может быть,