85025 (763952)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

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

Ф. В. Вайнштейн

Разбиением называется представление натурального числа в виде суммы натуральных слагаемых, а сами слагаемые — частями разбиения. Порядок слагаемых не играет роли; так разбиения 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

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

Эта формула была открыта Эйлером в 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. Итак,

Значит, производящие функции последовательностей 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

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

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

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов статьи