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

19

РАЗБИЕНИЕ ЧИСЕЛ

Ф. В. ВАЙНШТЕЙН

Разбienем называется представленное натурального числа в виде суммы натуральных слагаемых, а сами слагаемые — частями разбиения. Порядок слагаемых не играет роли; так разбиения 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$ без помощью компьютера немыслimo. Между тем $p(100)$ было известно еще в прошлом веке. Мы познакомим вас со многими интересными свойствами разбиений и научим нахождение $p(n)$, не выписьвая всех разбиений числа $n$.

Задача вычисления $p(n)$ имеет почтенный возраст. Первые она была формулирована Лейбницем в 1654 году, а в 1740 — предложена немецким математиком Филиппом Ноде Леонарду Эйлеру. Занимаясь разбиениями, Эйлер открыл целый ряд их свойств, среди которых главное место занимала знаменитая «пентагональная теорема». С исследованием Эйлера начинается история теории разбиений, в развитию которого принимали участие крупнейшие математики последующих поколений.

22

ле, и т. д., пока не достиг до числа $k_q$.

Например, разбению на нечетные части (9, 9, 5, 1, 1) числа 25 будет отвечать картина, изображенная на рисунке 1. Она состоит из симметричных относительно диагонали углов, так что в самом верхнем уголке $2k_1+1$ точек, в следующем $2k_2+1$ точек и т. д., а всего точек будет $n$. Тепер проведем на той же картике линей так, как показано на рисунке 2, подсчитаем количество точек на каждой из этих линей и образуется из полученных таким образом чисел разбиения. Оказывается, все части этого разбиения различны.

Упражнение 5. Докажите это утверждение.

В нашем примере получится разбиение (9,6,5,4,1). Подумайте, как построить по разбиению на различные части разбиение на нечетные, т. е. восстанавливать по такому разбиению исходную симметриную картику.

Отступление: решение задачи M1065

В этом разделе используется более сложная техника, чем в остальной части статьи. При желании вы можете пробежать его, не вникая в детали, и продолжить чтение со следующero раздела. Итак, займемся решением задачи M1065 из «Задачика «Кванта» (1987, № 9). Напомним ее формулировку.

Вудем рассматривать векторы $(x, y)$ с целыми неотрицательными координатами, причем хотя бы одна из координат отлична от 0. Наозем такой вектор образующим, если $|x-y|=1$.

a) Докажите, что рассматриемый вектор $(x, y)$ можно представить в виде суммы различных образующих (или он сам — образующей) тогда и только тогда, когда величана $k(x, y)=x+y-(x-y)^2$ неотрицательна.

б) Докажите, что число $N(x, y)$ различных (с точностью до порядка) представленный вектора $(x, y)$ в виде суммы различных образующих зависит только от числа $k=k(x, y)$. Найдите $N(13, 18)$.

Решение задачи наименем с того, что найдем общий вид целочисленных решений неравенства $k(x, y) \geq 0$. Числа $x+y$ и $x-y$ имеют одинаковую четность, поэтому $k(x, y)$ при любых целых $x, y$ — четное число. Следовательно, для любого целого $m \geq 0$ достаточно найти целочисленные решения уравнения $x+y-(x-y)^2=2m$. Положим $x-y=q$. Тогда $x+y=2m+q^2$. Из этих двух равенств немедленно получаем:

$$\begin{align*} (x, y) &= (m+q(q+1)/2, \\ m+q(q-1)/2), \end{align*}$$

где $q$ — любое целое число, а $m \geq 0$.

Смысл чисел $m$ и $q$ становится более важным, если представляется себе векторы вида (3) при $m=0$ как точки с целыми координатами парабoles $k(x, y)=0$, лежащей в плоскости $(x, y)$. (Вы понимаете, почему это парабола?) Тогда полученные нами целочисленные решения неравенства $k(x, y) \geq 0$ показывают, что все точки с целыми координатами, лежащие на параболе $k(x, y)=0$ и внутри нее, получаются сдигами целых точек этой парабoles на векторы $(m, m)$ (рис. 3). Удобно считать, что число $m(m=0, 1, 2, ...)$ — номер парабoles, на котором лежит точка $(x, y)$, а $q=x-y=0, \pm 1, \pm 2, ...$ — номер точки на этой параболе.

Поскольку задачи симметрицы относительно перестановки координат векторов, достаточно вывести все утверждения для таких векторов $(x, y)$, что $x \geq y$, т. е. для векторов вида (3) с $q \geq 0$.

Докажем достаточно условия в пункте a) задачи. По формуле суммы арифметической прогрессии

$$\begin{align*} 1+2+\dots+(q-1)+m+q &= m+q(q+1)/2; \\ 0+1+\dots+q-2+m+(q-1) &= m+q(q-1)/2. \end{align*}$$

23

Позному формулы $(x, y) = (1, 0) + (2, 1) + \dots + (q-1, q-2) + (m+q, m+q-1)$ при $q > 0$ и $(m, m) = (1, 0) + (m-1, m)$ при $q = 0$, $m > 0$ дают представления $(x, y)$ в виде суммы различных образующих.

Доказать необходимость условия тоже несложно. Пусть
$x = r_1 + \dots + r_a + s_1 + \dots + s_b$
$y = r_1 + \dots + r_a - a + s_1 + \dots + s_b + b$
позному $x - y = a - b$. Положим $q = x - y$ и
$m = (r_1 - q) + (r_2 - (q - 1)) + \dots$
$\dots + (r_q - 1) + r_{q+1} + \dots + r_a +$
$+ s_1 + \dots + s_b = x + y - q(q + 1)/2$
(здесь мы снова воспользовались формулой суммы арифметической прогрессии). Из неравенств (4) следует, что $r_a \geq 1, r_{a-1} \geq 2, r_{a-2} \geq 3, \dots$ и вообще $r_i \geq q - i + 1$. Позному $m \geq 0$, т. е. $(x, y)$ — вектор вида (3), что и требовалось.

В геометрических терминах утверждение 6) означает, что число

$$N(x, y)$$ зависит лишь от номера $m$ парабoles и не зависит от номера $q$ точки на параболе.

Пусть $T(m, q)$ — множество представлений вектора (3) в виде суммы различных образующих и $t(m, q)$ — число таких представлений. Задача будет решена, если мы докажем, что для любого целого $q$ имеет место равенство $t(m, q) = t(m, q - 1)$ (это и значит, что $t(m, q)$, а вместе с ним $N(x, y)$, не зависит от $q$). Мы отложенные выше множество $T(m, q)$ с множеством таких пар последовательностей, удовлетворяющих неравенствам (4), что $r_1 + \dots + r_a + s_1 + \dots + s_b = m + q(q + 1)/2$ при $q = a - b$. Такую пару мы будем записать в виде $(r_1, \dots, r_a | s_1, \dots, s_b)$.

Рассмотрим отображение $\varphi$ множество $T(m, q)$ в множество $T(m, q - 1)$, заданной формулой
$$\varphi(r_1, \dots, r_a | s_1, \dots, s_b) = \begin{cases} (r_1 - 1, \dots, r_a - 1 | s_1 + 1, \dots, s_b + 1, 0), \\ \text{если } r_a > 1, \\ (r_1 - 1, \dots, r_{a-1} - 1 | s_1 + 1, \dots, s_b + 1), \\ \text{если } r_a = 1. \end{cases}$$

Упражнение 6. Проверьте, что $\varphi(r_1, \dots, r_a | s_1, \dots, s_b) \in T(m, q - 1)$.

Чтобы доказать, что $\varphi$ — взаимно однозначное отображение, построим обратное отображение $\psi$: $T(m, q - 1) \rightarrow T(m, q)$, прочитав правило, заданное $\varphi$, следваем:

$$\psi(r_1, \dots, r_a | s_1, \dots, s_b) = \begin{cases} (r_1 + 1, \dots, r_a + 1, 1 | s_1 - 1, \dots, s_b - 1), \\ \text{если } s_b > 0, \\ (r_1 + 1, \dots, r_a + 1 | s_1 - 1, \dots, s_b - 1), \\ \text{если } s_b = 0. \end{cases}$$

Построенные отображения взаимно обратны, поэтому $\varphi$ — взаимно однозначное соответствие. Значит, $t(m, q) = t(m, q - 1)$, что и утверждалось.

Чтобы научиться вычислять значения $N(x, y)$, установить между числами $t(m, q)$ и $p(m)$.

Утверждение: $t(m, q) = p(m)$.

Мы уже знаем, что $t(m, q) = t(m, 0)$, поэтому достаточно доказать, что $t(m, 0) = p(m)$. Воспользовемся простым и полезным графическим средством, называемым «диаграммой Юнса раз-

24

бценя. Рассмотрим, например, разбиение (6, 4, 4, 2, 1). Его диаграмма Юнга изображена на рисунке 4 (в первой строке стоит 6 точек, во второй — 4, в третьей — 4, в четвертой — 2, в пятой — 1). Всякое разбиение можно изображать в виде диаграммы Юнга и по всей диаграмме Юнга — записать разбиение.

Проведем на диаграмме Юнга диагональ — черная линия на рисунке 4. Пусть $r_1$ — число точек в первой строке, лежащих на диагонали и справа от нее, $r_2$ — число точек в третьей строки, лежащих на диагонали и справа от нее, и т. д.; $s_1$ — число точек первого столбца под диагональю, $s_2$ — число точек второго столбца под диагональю и т. д. Поставим в соответствии диаграмме Юнга, изображаемо разбиение числа $m$, пару последовательности

$$\left( r_1, r_2, \dots | s_1, s_2, \dots \right),$$
$$r_1 + r_2 + \dots + s_1 + s_2 + \dots = m,$$

т. е. элемент множества $T(m,0)$. Например, диаграмме на рисунке 4 соответствует пара (6, 3, 2|4, 2, 0). Знай пару последовательностей, можно легко восстановить диаграмму Юнга. Следовательно, мы установили взаимно однозначное соответствие между множеством разбиений и множеством $T(m,0)$. Утверждение доказано.

Теперь ничего не стоит ответить и на последний вопрос задачи — о значении $N(13,18)$. Поскольку $13 = 3 + 5 \cdot 4/2$, $18 = 3 + 6 \cdot 5/2$, точка (13,18) лежит на третьей параболе. Значит, $N(13,18) = t(3,0) = p(3) = 3$.

Следующие упражнения — на применение диаграммы Юнга.

Упражнения

7. Число разбиений $n$ не более чем с $k$ частями, равно числу разбиений $n$ с частями, не превысordingными $k$. Подсказка: отразите диаграмму Юнга относительно диагонали.

8. Число разбиений $n$ с различными частями равно числу разбиений $n$, диаграмма Юнга которых симметрина относительно диагонали. Подсказка: вспомните соответствие Сильвестра.

Формула Гаусса — Якоби

Решая задачу M1065, мы проделали большую работу. Нельзя ли снова воспользоваться произвольными функциями и извлечь из равенства $t(m,q) = p(m)$ какое-нибудь красное тоjdество?

$N(x,y)$ — это число способов, которые можно представить вектор $(x,y)$ как сумму различных образующих вида $(k,k-1)$ и $(k-1,k)$. Рассуждая так же, как при выводе формулы произвольшей функции числа разбиений с различными частями, мы запишем произвольную функцию для $N(x,y)$ (это ряд от двух переменных $u$ и $v$):

$$\prod_{k=1}^{\infty} \left( 1 + u^{k-1} v^k \right) \left( 1 + u^k v^{k-1} \right) = \sum_{x,y=0}^{\infty} N(x,y) u^x v^y.$$

Поскольку $N(x,y) = t(m,q)$, где $x = m + q(q+1)/2, y = m + q(q-1)/2$, равенство можно проделить:

$$\sum_{q=-\infty}^{\infty} \left( \sum_{m=0}^{\infty} t(m,q) u^m v^m \right) \times u^{q(q+1)/2} v^{q(q-1)/2}.$$

Воспользовемся теперь, что $t(m,q) = p(m)$ и продолжим равенство:

$$\sum_{q=-\infty}^{\infty} \left( \sum_{m=0}^{\infty} p(m) u^m v^m \right) \times u^{q(q+1)/2} v^{q(q-1)/2}.$$

Ряд, стоящий в скобках, — произвольная функция чисел разбиения $p(m)$, которое мы знаем (формула (1)), поэтому продолжаем:

$$\prod_{k=1}^{\infty} \left( 1 - u^k v^k \right)^{-1} \sum_{q=-\infty}^{\infty} u^{q(q+1)/2} v^{q(q-1)/2}.$$

Теперь приравняем левую часть первого и правую часть последнего равенства, умножив обе части на $\Pi(1 - u^k v^k)^{-1}$. Получим окончательный результат:

$$\prod_{k=1}^{\infty} \left( 1 + u^{k-1} v^k \right) \left( 1 + u^k v^{k-1} \right) =$$

25

$$\sum_{q=-\infty}^{\infty} u^{q(q+1)/2} v^{q(q-1)/2}.$$

Это тожество — цель наших преобразований. Оно называется формулой Гаусса—Якоби. Из этого замечательного тожества с двумя переменными можно получить много разных тожеств с одной переменной.

Упражнение 9. Подставьте в формулу Гаусса—Якоби $u=-t$, $v=-t^2$ и получите пентагональный теорему Эйлера.

Тепер подставим в формулу Гаусса—Якоби $u=v=-t$. В левой части получится:

$$\prod_{k=1}^{\infty} (1-t^{2k-1})^2 (1-t^{2k}) = \prod_{k=1}^{\infty} (1-t^{2k-1}) \prod_{k=1}^{(1-t^k)}.$$

Заменяя произведение $\Pi(1-t^{2k-1})$ на $\Pi(1+t^k)^{-1}$ по формуле (2), мы преобразуем левую часть в $(1-t)(1-t^2)(1-t^3).../(1+t)(1+t^2)(1+t^3)...$.

Правая часть формулы Гаусса—Якоби при подстановке $u=v=-t$ превращается в $\sum_{-\infty}^{\infty} (-1)^q t^q$. Мы получаем следующее формулу:

$$\frac{(1-t)(1-t^2)(1-t^3)...}{(1+t)(1+t^2)(1+t^3)...} = 1-2t+2t^4-2t^9+2t^{16}-...$$

Подстановка $u=t$, $v=1$ в формулу Гаусса—Якоби аналогичным образом приводит к формуле:

$$\frac{(1-t^2)(1-t^4)(1-t^6)...}{(1-t)(1-t^3)(1-t^5)...} = 1+t+t^3+t^6+t^{10}+...$$

Эти две формулы получены Гаусом. Нечего и говорить, что это удивинительно красивые формулы!

Тождества Роджерса — Рамануджана

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

Первое тожество. Число разбиений натурального числа $n$, в которых разность между любыми двумя частями превозходит единицу, равно числу разбиений числа $n$ на части, дающие при делении на 5 остаток 1 или 4.

Второе тожество. Число разбиений натурального числа $n$, в которых разность между любыми двумя частями и каждая часть превозходит единицу, равно числу разбиений числа $n$ на части, дающие при делении на 5 остаток 2 или 3.

Конечно, закономерность, утверждаемая этими тожествами, в высшей степени красива и нетривиальная, и неудивительно, что крупнейший английский математик нацелого века Г. Харди, узнаший о них из письма Рамануджана датированного 16 января 1913 года, пришел в восхшение.*)

При чтении этой статьи у вас, может быть, сложилось впечатление, будто теория разбиения наполинает кунсткамеру, в котором заботливо собраны различные экзотические эксперименты, никак или почти никак между собой не связаны. До недавнего времени так оно и было. Ситуация коренным образом изменилась лишь в 70-х годах нацелого века, когда английскому математнику И. Макдональду удалось найти единий подход к доказательству большого класса тожеств теории разбиения и открыть много новых, объединив их в стройную теорию (тождество Гаусса — Якоби включается в нее).**) Для тожеств Роджерса — Рамануджана и многих аналогичных тожеств общего подхода не найдено, хотя в последнее время и появились алгебраические методы их доказательств.

Так что, понимание истинной природы этих тожеств, верятоно, еще впереди.

*) О жизни и творчества замецательного индисккого математика вы можете прочитать в статье С. Г. Гиндикина «Загадка Рамануджана» («Квант», 1987, № 10).

**) Волее детальную информацию об этом вы можете найти в статье Д. В. Фукса «О раскрытии скобок, об Эйлере, Гауссе и Макдональде и об упущенныхвозможностях» («Квант», 1981, № 8).