Учебная работа № 1987. Разбиение чисел

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (6 оценок, среднее: 4,67 из 5)
Загрузка...
Контрольные рефераты

Учебная работа № 1987. Разбиение чисел

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

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

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

p(0) + p(1) x + p(2) x2 + p(3) x3 + … =

1

(1 – x)(1 – x2)(1 – x3) …

.
(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. Итак,

(1 + x)(1 + x2)(1 + x3) … =

1

(1 – x)(1 – x3)(1 – x5) …

.
(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 века английским математиком Дж. Глэйшером.

Чтобы доказать взаимную однозначность соответствия Глэйшера, достаточно построить обратное соответствие между разбиениями с нечётными частями и разбиениями с неравными частями. Вот это соответствие:

Учебная работа № 1987. Разбиение чисел