О раскрытии скобок, об Эйлере, Гауссе, Макдональде и об упущенных возможностях

12

Д. Фукс

О раскрытини скобок,
об Эйлере, Гауссе, Макдональде
и об упущенных возможностях

Сколько раз каждому из вас доводилось раскрывать скобки в произведении? Тысячи, а может быть, десяти тысяч? Если и есть в этом занятии что-нибудь привлекательное, так это надежда, что результат умножения, после приведения подобных членов, примет благоприятный вид, как, скажем,

$$\begin{align*} (a+b) (a-b) &= a^2 - b^2, \\ (1-a) (1+a + \dots + a^n) &= 1 - a^{n+1}. \end{align*}$$

Ниже пойдет речь о подобных равенствах, только горячдо менее оченьидных и горячдо более глубоких. Они составляют результат более чем двухсотлетней работы крупнейших математиков мира. Своим читателем я посоветую вооружиться ручкой и бумагой и повторять за мной все выкладки: это помогет не только понять содержание статьи, но и оценить степень нетривиальности ее результатов.

1. Тождество Эйлера

В середине XVIII века — дело было в 1748 году или несколько годами раньше — Леонард Эйлер занитесовался коэффициентами многочлена

$$\varphi_n(x) = (1-x) (1-x^2) (1-x^3) \dots (1-x^n).$$

Он раскрыл скобки в произведении — и получил порозительный ре-

13

Зультат. Проделаем эту выкладку и мы:

$$\varphi_1(x) = 1 - x,$$
$$\varphi_2(x) = 1 - x - x^2 + x^3,$$
$$\varphi_3(x) = 1 - x - x^2 + x^4 + x^5 - x^6,$$
$$\varphi_4(x) = 1 - x - x^2 + 2x^5 - x^8 - x^9 + x^{10},$$
$$\varphi_5(x) = 1 - x - x^2 + x^5 + x^6 + x^7 - x^8 - x^9 - x^{10} \dots,$$
$$\varphi_6(x) = 1 - x - x^2 + x^5 + 2x^7 - x^9 - x^{10} \dots,$$
$$\varphi_7(x) = 1 - x - x^2 + x^5 + x^7 + x^8 - x^{10} \dots,$$
$$\varphi_8(x) = 1 - x - x^2 + x^5 + x^7 + x^9 \dots,$$
$$\varphi_9(x) = 1 - x - x^2 + x^5 + x^7 + x^{10} \dots,$$
$$\varphi_{10}(x) = 1 - x - x^2 + x^5 + x^7 \dots$$

Многооточная обозначют части многочленов $\varphi_n(x)$, содержащие $x$ в степени, больших 10 (выписать эти многочлены полностью не позволяет формату журнала: многочлен $\varphi_{10}(x)$, например, имеет степень 55).

Начнем с очередного, но важного наблюдания: коэффициенты многочлена $\varphi_n(x)$ с ростом $n$ «стабилизируются», то есть каждый из них начиная с некоторого $n$ не меняется. Это легко обязывает: переход от $\varphi_{n-1}(x)$ к $\varphi_n(x)$, состоящий в умножении на $1 - x^n$, не оказывает никакого воздействия на коэффициенты при $1, x, \dots, x^{n-1}$, так что при $n > k$ коэффициент при $x^k$ в многочлене $\varphi_n(x)$ от $n$ не зависит. (Например, вычисления часты многочлена $\varphi_{10}(x)$ не изменятся, если вместо $\varphi_{10}$ взять $\varphi_{11}, \varphi_{12}$ и т. д.) Ввиду этого мы можем говорить о «бесконечном произведении»

$$\varphi(x) = (1 - x)(1 - x^2)(1 - x^3)(1 - x^4) \dots,$$

поннима под этим, конечно, не многочлен, а «степенной ряд», то есть выражение вида

$$a_0 + a_1x + a_2x^2 + a_3x^3 + a_4x^4 + \dots,$$

где $a_0, a_1, a_2, a_3, a_4 \dots$ — числа; в нашем случае $a_0, a_1, a_2, a_3, a_4$ — стабилизирующиеся коэффициенты. Наше вычисление показывает, что

$$a_0 = a_5 = a_7 = 1,$$
$$a_1 = a_2 = -1,$$
$$a_3 = a_4 = a_6 = a_8 = a_9 = a_{10} = 0.$$

$\varphi(x)$ называется функцией Эйлера.

Слово «функция» здесь употреблено не случайно: при $-1 < x < 1$ значения $\varphi(x)$ можно вычислить (подобно тому, как вычислют сумму бесконечной геометрической прогрессии).

Тепер — главное. После раскрытия наших скобок очень многое уничтожается, можно сказать — почти все. Например, результат раскрытия скобок в произведении $(1 - x)(1 - x^2) \dots (1 - x^{10})$ содержит до приведения подобных 43 слагаемых с $x$ в степени, меньше или равных 10, в том числе 24 слагаемых с $x$ в степени 8, 9, 10. После приведения подобных из этих 43 слагаемых остается всего 5, в том числе ни одного с $x$ в степени 8, 9; 10. Более точно, как мы видели, среди коэффициентов $a_0, a_1, a_2, \dots, a_{10}$ три равны 1, два равны —1 и шесть равны 0. Высказем осторожную гипотезу: коэффициенты $a_k$ всегда равны 0, 1 или —1, причем большимство из них равно 0. Дальнейшее вычисление, которое читатель при желании может проверить сам, не только подтверждает эту гипотезу, но и позволяет ее уточнить. Вот, например, часть ряда $\varphi(x)$, содержащая $x$ в степени, не превозходящих 100:

$$\varphi(x) = 1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + x^{22} + x^{26} -$$
$$- x^{35} - x^{40} + x^{51} + x^{57} - x^{70} - x^{77} + x^{92} + x^{100} \dots$$

Надо полагать, что Эйлер, который не боялся длинных выкладок и отменно считал, примерно столько членов ряда $\varphi(x)$ и вычислил. А потом он просто не мог не заметить, что коэффициенты, отличные от 0, равны 1 или —1, и при этом единицы и минус единицы расположили.

14

Жены не как попало, а в строго определенном порядке: две единицы, две минут единицы, две минут единицы и т. д.*). В таблице выписаны показатели степени $x$, при которых стоит ненулевые коэффициенты.

Легко угадать, что это за показатели: в $n$-м столбце нашей таблицы в верхней строке стоит числа $\frac{3n^2 \pm n}{2}$, в нижней — число $(-1)^n$. Если это так при всех $n$, мы приходим к равенству

$$(1-x)(1-x^2)(1-x^3) \ldots = 1-x-x^2+x^5+x^7 \ldots +(-1)^n x^{\frac{3n^2-n}{2}} + (-1)^n x^{\frac{3n^2+n}{2}} + \ldots$$

или, пользоваться приняной в математике сокращенной символкой,

$$\prod_{n=1}^{\infty} (1-x^n) = 1 + \sum_{n=1}^{\infty} (-1)^n \left( x^{\frac{3n^2-n}{2}} + x^{\frac{3n^2+n}{2}} \right).$$

Это и есть тождество Эйлера. Последующие показания математков для этого тожеству несколько доказательств. Однако из них приводится в п. 3. (Читатель, который больше интересует фактами, чем доказательствами, без учерба для понимания дальнейшего может этот параграф пропустить.) А сейчас я расскажу об одном замечательном применении тождества Эйлера, которое украшает все учебники комбинаторики.

2. Тождество Эйлера и число разбиений

Пусть $n$ — натуральное число. Обозначим через $p(n)$ число способов, которые можно представить $n$ в виде суммы натуральных слагаемых (при этом слагаемые в суммах могут повторяться, и представления, различащие лишь порядком слагаемых, считаются одинаковыми).

Например:

$$p(1) = 1;$$
$$p(2) = 2 \quad (2=2; 2=1+1);$$
$$p(3) = 3 \quad (3=3; 3=2+1; 3=1+1+1);$$
$$p(4) = 5 \quad (4; 3+1; 2+2; 2+1+1; 1+1+1+1);$$
$$p(5) = 7 \quad (5; 4+1; 3+2; 3+1+1; 2+2+1; 2+1+1+1+1).$$

Числа $p(n)$ входят во многое математическое формулы, и их полезно уменьшить. Но как это сделать? Попробуйте, например, найти $p(10)$. Вам предется изрядно повозиться, и, если повезет, вы найдете правильный ответ: 42. А если нужно знать, скажем, $p(50)$? На помощь приходит тождество Эйлера.

*) Мемуар Эйлера на эту тему полностью приведен в книге Д. По й а «Matematika и праводопобные рассудения» (М., «Наука», 1975, с. 111). Чтение этого темуара, как и других глав книг Пойа, несомненно, доставит вам больше удобства.

15

Сначала немного «теории». Положим
$$\pi(x) = 1 + p(1)x + p(2)x^2 + p(3)x^3 + \dots = 1 + x + 2x^2 + 3x^3 + 5x^4 + 7x^5 + \dots$$

Как и $\varphi(x)$, $\pi(x)$ — функция, определяющая при $-1 < x < 1$. Но, опять-tаки, нас она интересует только как степенной ряд.

Теорема. Ряды $\varphi(x)$ и $\pi(x)$ взаимно обратны, то есть
$$\varphi(x) \cdot \pi(x) = 1.$$

Вы понIMAGE, в чем смысл этого равенства? Степенные ряды можно перемножать:
$$(a_0 + a_1x + a_2x^2 + \dots) (b_0 + b_1x + b_2x^2 + \dots) = a_0b_0 + a_0b_1x + a_0b_2x^2 + \dots$$
$$+ a_1b_0x + a_1b_1x^2 + a_1b_2x^3 + \dots + a_2b_0x^2 + a_2b_1x^3 + a_2b_2x^4 + \dots$$
$$= a_0b_0 + (a_0b_1 + a_1b_0)x + (a_0b_2 + a_1b_1 + a_2b_0)x^2 + \dots;$$

наше утверждение означает, что если перемножить таким образом ряды $\varphi(x)$ и $\pi(x)$, то полученное произведение сведется к 1: коэффициенты при $x, x^2, x^3, \dots$ будут равны нулю.

Доказательство.
$$\frac{1}{\varphi(x)} = \frac{1}{1-x} \cdot \frac{1}{1-x^2} \cdot \dots \cdot \frac{1}{1-x^k} \cdot \dots =$$
$$= (1+x+x^2+x^3+\dots) (1+x^2+x^4+x^6+\dots) \times \dots$$
$$\dots \times (1+x^k+x^{2k}+x^{3k}+\dots) \dots$$

При раскрытии скобок в последнем произведении получится сумма всевозможных выражений вида
$$x^{a_1}x^{2a_2} \dots x^{ka_k},$$

где $a_1, \dots, a_k$ — целые неотрицательные числа. Таким образом, $x^n$ войдет в эту сумму столько раз, сколькоими способами $n$ можно представить в виде
$$a_1 + 2a_2 + \dots + ka_k.$$

Но это представление можно переписать так:
$$\underbrace{1 + \dots + 1}_{a_1} + \underbrace{2 + \dots + 2}_{a_2} + \underbrace{k + \dots + k}_{a_k}.$$

Мы видим, что представленный числа $n$ в виде $a_1 + 2a_2 + \dots + ka_k$ столко же, сколько есть его представленный в виде суммы натуральных слагаемых, то есть $p(n)$. Таким образом, коэффициент при $x^n$ в нашем произведении равен $p(n)$, то есть $\frac{1}{\varphi(x)} = \pi(x)$. Теорема доказана.

Положив для удобства $p(0) = 1$, написем
$$(1-x-x^2+x^5+x^7-\dots) (p(0) + p(1)x + p(2)x^2 + \dots) = 1$$

(коэффициенты в первом множителе пишутся согласно теодесту Эйлера!). Раскроем скобки и приравняем нулю коэффициенты при $x, x^2, x^3, \dots, x^n$ в левой части. Получим:
$$p(1) - p(0) = 0;$$
$$p(2) - p(1) - p(0) = 0;$$
$$p(3) - p(2) - p(1) = 0;$$
$$p(n) - p(n-1) - p(n-2) + p(n-5) + p(n-7) - \dots = 0$$

(в левой части последней формулы нужно писать слагаемые до тех пор, пока аргумент у р остается неотрицательным). Итак,
$$p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + \dots$$

Эта формула позволяет быстро составить довольно длинуную таблицу чисел $p(n)$. Вот практический совет, как это сделать. Возьмите лист клетчатой бумаги — лучше всего двойной террадиный лист. Отрежьте вдоль его длиной стороны полоску шириной 3—4 клетки. Положите эту полоску перед собой вертикально и улевого среда в нижней клетке поставьте какой-нибудь знак, скажем звездочку. Затем, дивяясь вверх,

16

поставьте в первой клетке +, во второй +, в пятой -, в седьмой —, в двенадцатой +, в пятнадцатой + и т. д., насоклько хватит длины полоски (рис. 1). Оставшуюся часть листа также положите перед собой вертикальное и, отступя 10—15 клеток от ее левого среда, проведите на ней вертикальную черту — сверху донизу. В клетки, прилегающие к черте слева, дивяясь сверху вниз, выпишите уже известные вам числа $p(n)$, начиная с $p(0)$: 1, 1, 2, 3, 5, 7. Чтобы найти следующее значение, приложите отрезанную полоску справа к вертикальной черте так, чтобы звездочка оказалась против первой пустой клетки. Тепер из суммы чисел, стоящих против плосков, выпишите сумму чисел, стоящих против минусов. Что получится — выпишите в клетку против звездочки: это — следующее значение функции $p(n)$. Опустите полоску на одну клетку вниз и повторите то же самое. И так далее. Через несколько минут вы получите колонку чисел $p(n)$ высотой в ваш лист.

Пользовать этим решетом, я нашел числа $p(n)$ для $n \leq 50$. На это потребовалось — чисто, по часам — 17 минут. (Неколько первых шагов вычисления я привожу на рисунке 2; красные числа — это новые значения $p(n)$.) В частности,

$$p(50) = 204226.$$

Представьте себе, сколько потребовалось бы времени для нахождения этого числа кустарным способом!

3. Доказательство точкиства Эйлера

Раскроем скобки в нашем произведение

$$(1-x)(1-x^2)(1-x^3)(1-x^4)$$

Получится сумма (бесконечная), в которой $x^n$ встречается столько раз, сколькоми способами $n$ представляется в виде суммы возратающей последовательности натуральных чисел: $n=n_1+n_2+\dots+n_k$, $n_1<n_2<\dots<n_k$; при этом знак при $x^n$ будет +, если $k$ четно, и —, если $k$ нечетно. Ниже в этом параграфе набор们 $(n_1, \dots, n_k)$ с $n_1+\dots+n_k=n$ и $n_1<\dots<n_k$ называются просто «разбиениями».

Мы будем различать разбиения трех типов. Обозначим для разбиения $(n_1, \dots, n_k)$ через $s$ наиболее число такое, что $n_k-n_k-s+1=s-1$, то есть $s$ чисел $n_k-s+1, \dots, n_k$ идут подряд (очевидно, $s \leq k$). Например, для разбиения $12=2+4+6$ $s=1$, для разбиения $12=1+5+6$ $s=2$, для разбиения $33=4+5+7+8+9$ $s=3$. Мы скажем, что разбиение $(n_1, \dots, n_k)$ принимает

первому тину, если $n_1 \leq s$, исключая случай $n_1=s=k$;
второму тину, если $n_1>s$, исключая случай $n_1=s+1$, $s=k$;
третьему тину в исключениях случайх, то есть если $s=k$ и $n_1$ равно $s$ или $s+1$.

Поставим теперь в соответствие разбиению $(n_1, \dots, n_k)$ первого типа разбиения

$$\begin{cases} (n_2, \dots, n_k-n_1, n_k-n_1+1+1, \dots, n_k+1), \text{ если } k-n_1 \geq 2, \\ (n_2+1, \dots, n_k+1), \text{ если } k-n_1=1, \end{cases}$$

которое относится, оченьindo, ко второму типу (проверьте!)

17

Рис. 2

Более того, таким образом между разбиениями первого и второго типа получается взаимно однозначное соответствие: обратное отображение ставит в соответствие разбиению $(n_1, \dots, n_k)$ второго типа разбиение
$$\begin{cases} (s, n_1, \dots, n_{k-s}, n_{k-s+1}-1, \dots, n_k-1), \text{ если } k-s \geqslant 1, \\ (s, n_1-1, \dots, n_k-1), \text{ если } k-s=0 \end{cases}$$

(обозначение $s$ сохраняет прежний смысл), относится к первому типу (проверьте!). Посокльку наше соответствие связи дает разбиения, в которых числа слагаемых различаются на 1, соответствующие этим разбиениям $x^n$ уничтожаются, и в нашей сумме останут только слагаемые, отвечащие разбиениям третього типа. А разбиения этого типа, по определению, имеют вид
$$\begin{align*} (k, k+1, \dots, 2k-1), \\ (k+1, k+2, \dots, 2k), \end{align*}$$
и им соответствует $(-1)^k x^{\frac{3k^2-k}{2}}, (-1)^k x^{\frac{3k^2+k}{2}}$ (как вам известно, $k+(k+1)+\dots+(2k-1)=\frac{3k^2-k}{2}$ и $(k+1)+(k+2)+\dots+2k=\frac{3k^2+k}{2}$).

Доказательство окончено.

4. Тождество Гаусса

Прошло около 70 лет со времени открытия Эйлера, и другой великий математик, Карл-Фридрих Гаусс, сделал следующий шаг в теории, получшей (по причине, в которых мы не вникаем) название «теория модулярных форм». Он обнаружил, что, если функцию Эйлера возвели в куб, получится ряд, быть может еще более замечательный, чем ряд Эйлера:
$$\varphi(x)^3 = (1-x)^3(1-x^2)^3(1-x^3)^3\dots = 1-3x+5x^3-7x^6+9x^{10}-11x^{15}\dots$$
(я советую вам не полениться и вычислить столько коэффициентов ряда $\varphi(x)^3$ или
$$\prod_{n=1}^{\infty} (1-x^n)^3 = 1 + \sum_{n=1}^{\infty} (-1)^n (2n+1)x^{\frac{n(n+1)}{2}}.$$
Это тождество Гаусса тем более удивительно, что квадрат функции Эйлера с виду ничего не применяется:
$$\varphi(x)^2 = 1-2x-x^2+2x^3+x^4+2x^5-2x^6-2x^8-2x^9+x^{10}\dots$$