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