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

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

Д. Фукс

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

(a + b)(a – b) = a2 – b2,

(1 – a)(1 + a + ... + an ) = 1 – an+1.

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

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			+ 2x5			– 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, 100
коэффициенты	–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) + ...

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

∞		∞
∏	(1 – xn) = 1 +	∑	(–1)n ( x½(3n² – n) + x½(3n² + n) ).
n=1		n=1

Это и есть тождество Эйлера. Последующие поколения математиков дали этому тождеству несколько доказательств. Одно из них приводится в п. 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 1 – x

·

1 1 – x2

· ... ·

1 1 – xk

· ... =

= (1 + x + x2 + x3 + ...)(1 + x2 + x4 + x6 + ...)×...×(1 + xk + x2k + x3k + ...)... .

При раскрытии скобок в последнем произведении получится сумма всевозможных выражений вида

	a1		2a2		kak
x		x		... x		,

где a1 ..., ak – целые неотрицательные числа. Таким образом, xn войдёт в эту сумму столько раз, сколькими способами n можно представить в виде

a1 + 2a2 + ... + kak.

Но это представление можно переписать так:

1 + ... + 1	+	2 + ... + 2	+ ... +	k + ... + k	.
a1		a2		ak

Мы видим, что представлений числа n в виде a1 + 2a2 + ... + kak столько же, сколько есть его представлений в виде суммы натуральных слагаемых, то есть p(n). Таким образом, коэффициент при xn в нашем произведении равен p(n), то есть 1/φ(x) = π(x). Теорема доказана.

Положив для удобства p(0) = 1, напишем