Статья: Разбиение чисел
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 > ...