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

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). Вам придется изрядно повозиться, и, если пов

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать