1. Тождество Эйлера
В середине XVIII века – дело было в 1748 году или несколькими годами раньше – Леонард Эйлер заинтересовался коэффициентами многочлена φn(x) = (1 – x)(1 – x2)(1 – x3)...(1 – xn). Он раскрыл скобки в произведении – и получил поразительный результат. Проделаем эту выкладку и мы: φ1(x) = 1 – x ,
φ2(x) = 1 – x – x2+ x3 ,
φ3(x) = 1 – x – x2+ x4 + x5– x6,
φ4(x) = 1 – x – x2+ 2+x5– x8– x9+ x10 ,
φ5(x) = 1 – x – x2+ x5 + x6+ x7– x8– x9– x10... ,
φ6(x) = 1 – x – x2+ x5 + 2x7– x9– x10 ... ,
φ7(x) = 1 – x – x2+ x5 + x7+ x8– x10... ,
φ8(x) = 1 – x – x2+ x5 +x7+ x9 ... ,
φ9(x) = 1 – x – x2+ x5 + x7+ x10... ,
φ10(x) = 1 – x – x2+ x5 + x7... .
Многоточия обозначают части многочленов φn(x), содержащие x в степенях, больших 10 (выписать эти многочлены полностью не позволяет формат журнала: многочлен φ10(x), например, имеет степень 55). Начнём с очевидного, но важного наблюдения: коэффициенты многочлена φn(x) с ростом n «стабилизируются», то есть каждый из них начиная с некоторого n не меняется. Это легко объяснить: переход от φn–1(x) к φn(x), состоящий в умножении на 1 – xn, не оказывает никакого воздействия на коэффициенты при 1, x, ..., xn–1, так что при n > k коэффициент при xk в многочлене φn(x) от n не зависит. (Например, вычисленная часть многочлена φ10(x) не изменится, если вместо φ10 взять φ11, φ12 и т.д.) Ввиду этого мы можем говорить о «бесконечном произведении»φ(x) = (1 – x)(1 – x2 )(1 – x3 )(1 – x4 )...,понимая под этим, конечно, не многочлен, а степенной ряд, то есть выражение вида a0 + a1x + a2x2 + a3x3 + a4x4 + ..., где a0, a1, a2, a3, a4... – числа; в нашем случае a0, a1, a2, a3, a4 – стабилизирующиеся коэффициенты. Наше вычисление показывает, чтоa0 = a5 = a7 = 1,
a1 = a2 = –1,
a3 = a4 = a6 = a8 = a9 = a10 = 0.
φ(x) называется функцией Эйлера. Слово «функция» здесь употреблено не случайно: при –1 < x < 1 значения φ(x) можно вычислить (подобно тому, как вычисляют сумму бесконечной геометрической прогрессии). Теперь – главное. После раскрытия наших скобок очень многое уничтожается, можно сказать – почти всё. Например, результат раскрытия скобок в произведении (1 – x)(1 – x2 )...(1 – x10 ) содержит до приведения подобных 43 слагаемых с x в степенях, меньших или равных 10, в том числе 24 слагаемых с x в степенях 8, 9, 10. После приведения подобных из этих 43 слагаемых остаётся всего 5, в том числе ни одного с x в степенях 8, 9, 10. Более точно, как мы видели, среди коэффициентов a0, a1, a2, ..., a10 три равны 1, два равны –1 и шесть равны 0. Выскажем осторожную гипотезу: коэффициенты ak всегда равны 0, 1 или –1, причём большинство из них равно 0. Дальнейшее вычисление, которое читатель при желании сможет провести сам, не только подтверждает эту гипотезу, но и позволяет её уточнить. Вот, например, часть ряда φ(x), содержащая x в степенях, не превосходящих 100:φ(x) = 1 – x – x2 + x5 + x7 – x12 – x15 + x22 + x26 –– x35 – x40 + x51 + x57 – x70 – x77 + x92 + x100... Надо полагать, что Эйлер, который не боялся длинных выкладок и отменно считал, примерно столько членов ряда φ(x) и вычислил. А потом он просто не мог не заметить, что коэффициенты, отличные от 0, равны 1 или –1, и при этом единицы и минус единицы расположены не как попало, а в строго определённом порядке: две единицы, две минус единицы, две единицы, две минус единицы и т.д. (Мемуар Эйлера на эту тему полностью приведён в книге Д.Пойа «Математика и правдоподобные рассуждения» (М., «Наука», 1975, с.111). Чтение этого мемуара, как и других глав книги Пойа, несомненно, доставит вам большое удовольствие.) В таблице выписаны показатели степеней x, при которых стоят ненулевые коэффициенты.показатели 1, 2 5, 7 12, 15 22, 26 35, 40 51, 57 70, 77 92,10коэффициенты –1 1 –1 1 –1 1 –1 1
Легко угадать, что это за показатели: в n-м столбце нашей таблицы в верхней строке стоят числа ½(3n2 – n), в нижней – число (–1)n. Если это так при всех n, мы приходим к равенству(1 – x)(1 – x2)(1 – x3)... = 1 – x – x2 + x5 + x7 – ... + (–1)n x½(3n² – n) + (–1)n x½(3n² + n) + ...
Это и есть тождество Эйлера. Последующие поколения математиков дали этому тождеству несколько доказательств. Одно из них приводится в п. 3. (Читатель, который больше интересуется фактами, чем доказательствами, без ущерба для понимания дальнейшего может этот параграф пропустить.) А сейчас я расскажу об одном замечательном применении тождества Эйлера, которое украшает все учебники комбинаторики.
2. Тождество Эйлера и число разбиений
Пусть n – натуральное число. Обозначим через p(n) число способов, которыми можно представить n в виде суммы натуральных слагаемых (при этом слагаемые в суммах могут повторяться, и представления, различающиеся лишь порядком слагаемых, считаются одинаковыми). Например:p(1) = 1;
p(2) = 2 (2 = 2; 2 = 1 + 1);
p(3) = 3 (3 = 3; 3 = 2 + 1; 3 = 1 + 1 + 1);
p(4) = 5 (4; 3 + 1; 2 + 2; 2 + 1 + 1; 1 + 1 + 1 + 1);
p(5) = 7 (5; 4 + 1; 3 + 2; 3 + 1 + 1; 2 + 2 + 1; 2 + 1 + 1 + 1; 1 + 1 + 1 + 1 + 1).
Числа p(n) входят во многие математические формулы, и их полезно уметь вычислять. Но как это сделать? Попробуйте, например, найти p(10). Вам придется изрядно повозиться, и, если повезёт, вы найдете правильный ответ: 42. А если нужно знать, скажем, p(50)? На помощь приходит тождество Эйлера. Сначала немного «теории». Положим π(x) = 1 + p(1)x + p(2)x2 + p(3)x3 + ... = 1 + x + 2x2 + 3x3 + 5x4 + 7x5 + ...
Как и φ(x), π(x) – функция, определённая при –1 < x < 1. Но, опять-таки, нас она интересует только как степенной ряд. Теорема. Ряды φ(x) и π(x), взаимно обратны, то есть φ(x) · π(x) = 1.
Вы понимаете, в чем смысл этого равенства? Степенные ряды можно перемножать:(a0 + a1x + a1x2 + ...)(b0 + b1x + b1x2 + ...) = a0b0 + a0b1x + a0b2x2 + ... + a1b0x + a1b1x2 + a1b2x3 + ... + a2b0x2 + a2b1x3 + a2b2x4 + ... +
. . . . . . . . . . . . . . . . . . . . . . .
= a0b0 + (a0b1 + a1b0)x + (a0b2 + 2a1b1 + a2b0)x2 + ...; наше утверждение означает, что если перемножить таким образом ряды φ(x) и π(x), то полученное произведение сведётся к 1: коэффициенты при x, x2, x3 ... будут равны нулю.
Доказательство. 1
φ(x)= (1 + x + x2 + x3 + ...)(1 + x2 + x4 + x6 + ...)×...×(1 + xk + x2k + x3k + ...)... .
Мы видим, что представлений числа n в виде a1 + 2a2 + ... + kak столько же, сколько есть его при xn в нашем произведении равен p(n), то есть 1/φ(x) = π(x). Теорема доказана. Положив для удобства p(0) = 1, напишем (1 – x – x2 + x5 + x7 + ...)(1 + p(1)x + p(2)x2 + ...) = 1 (коэффициенты в первом множителе пишутся согласно тождеству Эйлера!). Раскроем скобки и приравняем нулю коэффициенты при x, x2, x3, ..., xn в левой части. Получим: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) – ... = 0
(в левой части последней формулы нужно писать слагаемые до тех пор, пока аргумент у p остаётся неотрицательным). Итак, p(n) = p(n–1) + p(n–2) – p(n–5) – p(n–7) + ... .
Эта формула позволяет быстро составить довольно длинную таблицу чисел p(n). Вот практический совет, как это сделать. Возьмите лист клетчатой бумаги – лучше всего двойной тетрадный лист. Отрежьте вдоль его длинной стороны полоску шириной 3–4 клетки. Положите эту полоску перед собой вертикально и у левого среза в нижней клетке поставьте какой-нибудь знак, скажем звёздочку. Затем, двигаясь вверх, поставьте в первой клетке +, во второй +, в пятой –, в седьмой –, в двенадцатой +, в пятнадцатой + и т.д., насколько хватит длины полоски (рис. 1). Оставшуюся часть листа также положите перед собой вертикально и, отступя 10–15 клеток от её левого среза, проведите на ней вертикальную черту – сверху донизу. В клетки, прилегающие к черте слева, двигаясь сверху вниз, впишите уже известные вам числа p(n), начиная с p(0): 1, 1, 2, 3, 5, 7. Чтобы найти следующее значение, приложите отрезанную полоску справа к вертикальной черте так, чтобы звёздочка оказалась против первой пустой клетки. Теперь из суммы чисел, стоящих против плюсов, вычтите сумму чисел, стоящих против минусов. Что получится – впишите в клетку против звездочки: это – следующее значение функции p(n). Опустите полоску на одну клетку вниз и повторите то же самое. И так далее. Через несколько минут вы получите колонку чисел p(n) высотой в ваш лист. Пользуясь этим рецептом, я нашел числа p(n) для n ≤ 50. На это потребовалось – честно, по часам – 17 минут. (Несколько первых шагов вычисления я привожу на рисунке 2; красные числа – это новые значения p(n).) В частности, p(50) = 204226.
Представьте себе, сколько потребовалось бы времени для нахождения этого числа кустарным способом!
3. Доказательство тождества Эйлера
Раскроем скобки в нашем произведении (1 – x)(1 – x2)(1 – x3)(1 – x4)... .
Получится сумма (бесконечная), в которой xn встретится столько раз, сколькими способами n представляется в виде суммы возрастающей последовательности натуральных чисел: n = n1 + n2 + ... + nk , n1 < n2 < ... < nk ; при этом знак при xn будет +, если k чётно, и –, если k нечётно. Ниже в этом параграфе наборы (n1 , ..., nk ) с n1 + ... + nk = n и n1 < ... < nk называются просто «разбиениями». Мы будем различать разбиения трёх типов. Обозначим для разбиения (n1 , ..., nk ) через s наибольшее число такое, что nk – nk–s+1 = s – 1, то есть s чисел nk–s+1, ..., nk идут подряд (очевидно, s ≤ k). Например, для разбиения 12=2+4+6 s = 1, для разбиения 12=1+5+6 s = 2, для разбиения 33=4+5+8+9 s = 3. Мы скажем, что разбиение (n1 , ..., nk ) принадлежит
первому типу, если n1 ≤ s, исключая случай n1 = s = k;
второму типу, если n1 > s, исключая случай n1 = s + 1, s = k;
третьему типу в исключённых случаях, то есть если s = k и n1 равно s или s + 1.
Поставим теперь в соответствие разбиению (n1 , ..., nk ) первого типа разбиение ì (n2, ..., nk–n1 , nk–n1+1, ..., nk + 1), если k – n1 ≥ 2,
(n2 + 1, ..., nk + 1), если k – n1 = 1,
которое относится, очевидно, ко второму типу (проверьте!). Более того, таким образом между разбиениями первого и второго типа получается взаимно однозначное соответствие: обратное отображение ставит в соответствие разбиению (n1 , ..., nk ) второго типа разбиение (s, n1, ..., nk–s , nk–s+1 – 1, ..., nk – 1), если k – s ≥ 1, (s, n1 – 1, ..., nk – 1), если k – s = 0 (обозначение s сохраняет прежний смысл), относящееся к первому типу (проверьте!). Поскольку наше соответствие связывает разбиения, в которых числа слагаемых различаются на 1, соответствующие этим разбиениям xn уничтожатся, и в нашей сумме останутся только слагаемые, отвечающие разбиениям третьего типа. А разбиения этого типа, по определению, имеют вид (k, k + 1, ..., 2k – 1),(k + 1, k + 2, ..., 2k), и им соответствуют (–1)k x½(3k² – k), (–1)k x½(3k² + k) (как вам известно, k + (k + 1) + ... + (2k – 1) = ½(3k2 – k) и (k + 1) + (k + 2) + ... + 2k = ½(3k2 + k) ).
Доказательство окончено.