Биномиальные коэффициенты. Треугольник Паскаля

Как мы говорили в предыдущем уроке, для вычисления корней использовались так называемые биномиальные коэффициенты – коэффициенты при одночленах anan – 1ban – 2b2, ..., a2bn – 2abn – 1bn в разложении бинома (a + b)n.

Известно, что при n = 2 разложение бинома выглядит так:

(a + b)2 = a2 + 2ab + b2,

при n = 3 – так:

(a + b)3 = a3 + 3a2b +  3ab2 + b3.

Разложение для (a + b)2 издавна доказывали и иллюстрировали с помощью деления квадрата со стороной (a + b) на четыре части: два квадрата (их площади a2 и b2) и два прямоугольника (площадью ab каждый). Для разложения (a + b)3 применялось деление куба на два куба a3 и b3 и на шесть параллелепипедов a2b и ab2.

Рис. 1. Геометрическое расположение квадрата и куба суммы

Формула разложения выражения (a + b)n нередко называется биномом Ньютона, но это название исторически неудачно, так как она была известна задолго до Ньютона; Ньютон же обобщил эту формулу на случай дробных показателей степени n.

Коэффициент в разложении при обозначается Это обозначение в 1778 г. ввел Л. Эйлер. Таким образом, можно записать разложение бинома так:

Cоответственно,

Разумеется, можно вычислить все биномиальные коэффициенты для любого n путем непосредственного перемножения n множителей (a + b), раскрытия скобок и приведения подобных членов. Правда, математикам древности и средневековья сделать это мешало отсутствие алгебраической символики. например, в одном средневековом математическом тексте, имевшем хождение в Западной Европе в XV в. и, по-видимому, восходящем к арабам, биномиальные коэффициенты вычисляются очень наглядно путем возведения в степени числа 10001 и приводятся в виде таблицы.

1000900360084012601260084003600090001
100080028005600700056002800080001
10007002100350035002100070001
1000600150020001500060001
100050010001000050001
10004000600040001
1000300030001
100020001
10001
Таблица 1. Степень числа 1001 воспроизводит биномиальные коэффициенты

Ат-Туси (XIII в.) располагал таблицей биномиальных коэффициентов до n = 12 и, что еще важнее, привел общее правило для их получения, которое в современных обозначениях может быть выражено так:

Можете ли вы доказать это правило?

Доказательство

Благодаря данному правилу можно вычислять биномиальные коэффициенты последовательно для все больших степеней n: а именно, k-й коэффициент бинома степени n равен сумме k-го и (k – 1)-го коэффициентов степени (n – 1). К этому следует добавить, что в биноме степени n первый (точнее, нулевой, k = 0) и последний (k = n) коэффициенты – т. е. коэффициенты при an и при bn – оба равны 1 (при перемножении n множителей (a + b) член an получается единожды, а именно, при перемножении n раз чисел a; то же верно и для члена bn).

Если записать биномиальные коэффициенты в виде таблицы со строками и столбцами то каждая строка будет начинаться и заканчиваться единицей, а каждое промежуточное число строки будет равняться сумме двух чисел предыдущей строки – того, что стоит непосредственно над ним, и то, что стоит левее:

k 0 1 2 3 4 5 6 7 8 9
n
0         1
1 1   1
2 1 2    1
3 1 3 3    1
4 1 4 6 4    1
5 1 5 10 10 5    1
6 1 6 15 20 15 6    1
7 1 7 21 35 35 21 7    1
8 1 8 28 56 70 56 28 8    1
9 1 9 36 84 136 136 84 36 9    1
Таблица 2. Биномиальные коэффициенты

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

Полученный числовой треугольник называется треугольником Паскаля. Таблицы биномиальных коэффициентов были известны и предшествующим математикам – китайским, арабским и европейским (П. Аппиан, 1527 г.; М. Штифель, 1544 г.; Н. Тарталья, 1556 г.). Однако именно благодаря работе Паскаля «Трактат об арифметическом треугольнике», опубликованной уже после смерти автора (в 1665 г.), свойства биномиальных коэффициентов получили широкую известность. Правда, сам Паскаль (и многие его предшественники) рисовали этот треугольник несколько иначе, с «повышенными» столбцами и прямым углом при вершине:

k 0 1 2 3 4 5 6 7 8 9
n – k
0         1    1    1    1    1    1    1    1    1    1
1 1 2 3 4 5 6 7 8 9
2 1 3 6 10 15 21 28 36
3 1 4 10 20 35 56 84
4 1 5 15 35 70 136
5 1 6 21 56 136
6 1 7 28 84
7 1 8 36
8 1 9
9 1
Таблица 3. Треугольник Паскаля

В такой таблице числа, соответствующие разложению бинома степени n, стоят не вдоль одной и той же строки, а вдоль одной и той же восходящей диагонали. Все восходящие диагонали, а значит, и вся таблица симметрична относительно главной нисходящей диагонали – «биссектрисы прямого угла». Каждое число в таблице (кроме единиц, находящихся на верхнем и левом краях), равняется сумме двух чисел, стоящих от него сверху и слева.

Вот еще несколько свойств таблицы 3, доказанных Паскалем.

Модель 1. 

Интересно и свойство делимости чисел, составляющих треугольник Паскаля. Если обозначить одним цветом числа, делящиеся нацело на какое-нибудь натуральное число, а другим – делящиеся с остатком, получатся неожиданные узоры. Некоторые из них составлены из равных разноцветных треугольников – это результат деления на простые числа. Другие же похожи на фракталы. Попробуйте объяснить – почему?

Числа, стоящие вдоль одной и той же строки (столбца) на таблице, также интересны. То, что в нулевой строке и нулевом столбце стоят единицы, очевидно. Очевидно и то, что на первой строке и первом столбце стоят подряд все натуральные числа: 1, 2, 3, 4 и т. д.

А вот что за числа стоят на второй строке (столбце)? Оказывается, эти числа имеют свое название, причем носят его с глубокой древности – это треугольные числа (см. «Фигурные числа пифагорейцев»). А числа на третьей строке (столбце) – пирамидальные числа, равные сумме треугольных.

Рис. 2. 

Если обратиться к форме треугольника Паскаля, представленной в таблице 2, и рассмотреть ее столбцы и нисходящие диагонали, то это рассмотрение ничего нового не даст: фактически, столбцы у таблиц 2 и 3 одни и те же, а нисходящие диагонали таблицы 2 совпадают со строками таблицы 3. Строки же таблицы 2 совпадают с восодящими диагоналями таблицы 3. Но вот замечательным свойством обладают восходящие диагонали таблицы 2. Если записать суммы чисел, стоящих на восходящих диагоналях, то мы получим: 1; 1; 1 + 1 = 2; 1 + 2 = 3; 1 + 3 + 1 = 5; 1 + 4 + 3 = 8 и т. д. Последовательность этих чисел (1, 1, 2, 3, 5, 8, ...) обладает тем свойством, что каждое число в ней равно сумме двух предыдущих. Эти числа носят название чисел Фибоначчи и обладают многими интересными математическими свойствами, возникая в самых неожиданных задачах.

Гораздо проще вопрос о том, чему равны суммы чисел, стоящих на каждой из строк таблицы 2 (или на каждой из восходящих диагоналей таблицы 3). Попробуйте на него ответить.

Ответ

Еще один сходный вопрос – чему равна сумма:

в которой все биномиальные коэффициенты степени n > 0 с нечетными номерами взяты со знаком плюс, а с четными – со знаком минус?

Ответ

Чрезвычайно важное свойство биномиального разложения связано с тем, что его коэффициенты оказывается, представляют собой не что иное, как числа сочетаний по элементов из множества с элементами (см. «Комбинаторика»; там же доказывается общая формула для этих чисел: ).

Приведем одно из свойств, связанных с делимостью биномиальных коэффициентов. Рассмотрим таблицу 2. Легко видеть, что все числа ее 5-й строки, кроме крайних единиц, делятся на 5; все числа 7-й строки, кроме крайних единиц, делятся на 7. У каких еще строк есть такое же свойство? Очевидно – у 2-й и 3-й. А у остальных, легко видеть, такого свойства нет. Что объединяет числа 2, 3, 5 и 7 и отличает их от других чисел первого десятка? Правильно, все они простые. Можно доказать, что, действительно, все числа n-ой строки треугольника Паскаля (в форме таблицы 2), кроме крайних единиц, делятся на n тогда и только тогда, когда n простое.

Еще одно красивое свойство треугольника Паскаля (в форме таблицы 2) связано с вопросом, сколько нечетных чисел содержит n-я строка. Оказывается, число этих нечетных чисел всегда равно 2k, где k – число единиц в двоичной записи числа n. Проверьте этот неочевидное свойство самостоятельно.

И наконец приведем сравнительно недавно и, в общем, то, случайно обнаруженное свойство треугольника Паскаля, связывающее его с простыми числами (Г. В. Манн, Д. Шенкс, 1972 г.). Запишем строки треугольника Паскаля (в форме таблицы 2), каждый раз сдвигая строки вправо на две позиции.

0    1
1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
5 1 5 10 10 5 1
6 1 6 15 20 15 6 1
7 1 7 21 35 35 21
8 1 8 28 56
9 1 9
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Таблица 4. Связь ряда простых чисел и треугольника Паскаля

Числа, стоящие в таблице, выделены, если они делятся на номер строки. Числа в нижней строке, нумерующие столбцы, выделены, если в этом столбце все числа выделены. Выходит, что выделенные номера столбцов в точности соответствуют простым числам.