Викия

Математика

Две теоремы Эйлера

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Поделиться

Обнаружено использование расширения AdBlock.


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

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

См. также Теорема Эйлера (теория чисел)

Изучение функции разбиения числа p(n) Эйлер начинает с рассмотрения бесконечного произведения

(1 + x + x^2 + ...)(1 + x^2 + x^4 + ...) ... (1 + x^k + x^{2k} + ...) ...

Каждый член произведения получается в результате умножения мономов, взятых по одному из каждой скобки. Если в первой скобке взять x^{m1}, во второй — x^{2m2} и т.д., то их произведение будет равно x^{m1+2m2+3m3+...}. Значит, после раскрытия скобок получится сумма мономов вида x^{m1+2m2+3m3+...}.

Сколько раз в этой сумме встретится x^n? Столько, сколькими способами можно представить n как сумму m_1 + 2m_2 + 3m_3 + ... Каждому такому представлению отвечает разбиение числа n на m_1 единиц, m_2 двоек и т.д. Так получаются все разбиения, так как каждое из них, конечно, состоит из нескольких единиц, нескольких двоек и т.д. Поэтому коэффициент при x^n равен числу разбиений p(n).

Посмотрим теперь на выражения в скобках. Каждое из них — бесконечная геометрическая прогрессия. По формуле суммирования

1 + x + x^2 + x^3 + ... = \frac{1}{1 - x},
1 + x^2 + x^4 + x^6 + ... = \frac{1}{1-x^2}

и т.д. Теперь наш результат можно записать так:

p(0) + p(1) x + p(2) x^2 + p(3) x^3 + ... = \frac{1}{(1-x)(1-x^2)(1-x^3)}....

(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) x^2 + d(3) x^3 + ... = (1 + x)(1 + x^2)(1 + x^3) ... ,
l(0) + l(1) x + l(2) x^2 + l(3) x^3 + ... = \frac{1}{(1-x)(1-x^3)(1-x^5)} .

Воспользуемся формулой

1 + xk = \frac{(1-x)^{2k}}{(1-x)^k},

верной при всех k:

(1 + x)(1 + x2)(1 + x3) ... = \frac{1-x^2}{1-x}  \frac{1-x^4}{1-x^2}  \frac{1-x^6}{1-x^3}  ...

В правой части равенства все числители сокращаются со знаменателями, содержащими x в чётной степени. Поэтому в знаменателе останутся только сомножители вида 1 - x ^ {2k-1}. Итак,

(1 + x)(1 + x^2)(1 + x^3) ... = \frac{1}{(1-x)(1-x^3)(1-x^5)}... .

(2)

Значит, производящие функции последовательностей d(n) и l(n) совпадают! Мы доказали теорему Эйлера: d(n) = l(n). Это доказательство хорошо иллюстрирует силу метода производящих функций. Но вернёмся к вычислению p(n). Изучая производящую функцию последовательности p(n), Эйлер сосредоточил внимание на произведении (1-x)(1-x^2)(1-x^3)..., т.е. на знаменателе правой части формулы (1). Раскрывая в нём скобки, Эйлер получил удивительный результат:

(1 - x)(1 - x^2)(1 - x^3) ... = 1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + x^{22} + x^{26} - x^{35} - x^{40} + ...

Показатели в правой части — пятиугольные числа, т.е. числа вида (3q^2 \pm q)/2, а знаки при соответствующих мономах равны (-1)^q. Исходя из этого наблюдения, Эйлер предположил, что должна быть верна Пентагональная теорема:

 \prod_{k=1}^\infty \left(1-x^k \right) = \sum_{n=-\infty}^\infty (-1)^q x^{(3q^2+q)/2} .

Пентагональная теорема оказалась «крепким орешком» — Эйлер сумел доказать её лишь 14 лет спустя. Эта теорема позволяет сравнительно просто вычислять значения p(n). Вот как это делается.

Умножим обе части равенства (1) на
\prod_{k=1}^\infty \left(1-x^k \right)

и воспользуемся пентагональной теоремой:

 ( p(0) + p(1) x + p(2) x^2 + ...)(1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + ...) = 1
.

Раскрыв скобки в левой части, получим, что коэффициенты при ненулевых степенях x равны нулю. Отсюда мы получаем замечательную формулу Эйлера, позволяющую последовательно находить числа p(n):

p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + ... + (-1)^{q+1} (p(n-\frac{3q^2-q}{2})+p(n-\frac{3q^2+q}{2}))

(Мы считаем, что p(n) = 0 при n < 0.) Пользуясь формулой Эйлера, можно составить таблицу значений p(n) для n \leqslant 200, что и проделал в начале XX века известный английский специалист по комбинаторике майор Мак-Магон. В то время это была наиболее полная таблица чисел p(n). Итак, мы сформулировали две теоремы, одну из которых — d(n) = l(n) — доказали. Согласитесь, что при всей элегантности этого доказательства, оно всё же оставляет чувство неудовлетворённости. Два множества разбиений — на нечётные и на неравные части — неожиданно оказались состоящими из одинакового числа элементов, но причина этого равенства осталась скрытой от нас. Хотелось бы думать, что существует какой-то естественный способ каждому элементу одного множества ставить в соответствие элемент другого.

Смотрите такжеПравить

ЛитератураПравить

Викия-сеть

Случайная вики