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