Треугольник Паскаля¶

Треугольник Паскаля — это бесконечная таблица чисел, имеющая треугольную форму, в которой каждое число равно сумме двух чисел, расположенных непосредственно над ним слева и справа. Треугольник Паскаля является фундаментальным объектом комбинаторики, теории вероятностей и алгебры, поскольку его строки содержат биномиальные коэффициенты — числа, возникающие при разложении степени бинома \((a+b)^n\).

¶История

Свойства треугольной таблицы чисел были известны задолго до Блеза Паскаля. В X веке персидский математик и поэт Омар Хайям описал связь между треугольными числами и биномиальными коэффициентами. В Китае треугольник был известен под названием «треугольник Ян Хуэя» (XIII век), а в Индии — «треугольник Пингалы» (II век до н. э.). В Европе треугольник впервые опубликовал в 1527 году Петер Апиан в своей книге «Космография», но систематическое изучение его свойств провёл французский математик Блез Паскаль в трактате «Трактат об арифметическом треугольнике» (1654 год). Паскаль использовал эту таблицу для решения задач теории вероятностей, в частности для вычисления числа исходов при подбрасывании монеты.

¶Устройство и построение

Треугольник Паскаля строится следующим образом. В вершине (нулевая строка) записывается число 1. Каждая последующая строка начинается и заканчивается единицей. Внутренние числа строки вычисляются как сумма двух чисел, расположенных над ними в предыдущей строке. Формально:

\[ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \]

где \(\binom{n}{k}\) — биномиальный коэффициент, \(n\) — номер строки (начиная с 0), \(k\) — позиция в строке (начиная с 0). Первые строки треугольника выглядят так:

`` Строка 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 ``

¶Свойства

¶Биномиальные коэффициенты

Каждое число в треугольнике Паскаля является биномиальным коэффициентом \(\binom{n}{k}\), который равен количеству способов выбрать \(k\) элементов из \(n\) без учёта порядка. Например, в строке 4 число 6 соответствует \(\binom{4}{2} = 6\).

¶Симметрия

Треугольник симметричен относительно вертикальной оси: \(\binom{n}{k} = \binom{n}{n-k}\). Это означает, что числа в каждой строке читаются одинаково слева направо и справа налево.

¶Сумма строк

Сумма чисел в \(n\)-й строке равна \(2^n\). Например, в строке 3 сумма \(1+3+3+1 = 8 = 2^3\). Это свойство отражает количество всех подмножеств множества из \(n\) элементов.

¶Степени двойки

Если сложить числа в каждой строке, получаются степени двойки: 1, 2, 4, 8, 16, 32 и т. д.

¶Числа Фибоначчи

Суммы чисел на диагоналях треугольника Паскаля дают последовательность Фибоначчи. Например, если сложить числа на «восходящих» диагоналях:

• 1-я диагональ: 1
• 2-я диагональ: 1
• 3-я диагональ: 1+1=2
• 4-я диагональ: 1+2=3
• 5-я диагональ: 1+3+1=5
• 6-я диагональ: 1+4+3=8

и так далее.

¶Треугольные и тетраэдральные числа

Вдоль боковых сторон треугольника расположены единицы. Вторые числа от края (1, 2, 3, 4, 5, ...) — это натуральные числа. Третьи числа от края (1, 3, 6, 10, 15, ...) — треугольные числа. Четвёртые числа (1, 4, 10, 20, 35, ...) — тетраэдральные числа.

¶Чётность и фракталы

Если раскрасить нечётные числа треугольника Паскаля в один цвет, а чётные — в другой, получается узор, напоминающий треугольник Серпинского — фрактальную структуру. Это связано с тем, что чётность биномиальных коэффициентов определяется правилом: \(\binom{n}{k}\) нечётно тогда и только тогда, когда в двоичной записи числа \(k\) каждый бит не превышает соответствующий бит числа \(n\).

¶Применение

¶Комбинаторика

Треугольник Паскаля — основной инструмент для вычисления числа сочетаний. Он используется в задачах о выборе, перестановках и распределениях.

¶Теория вероятностей

Биномиальные коэффициенты, взятые из треугольника, применяются для вычисления вероятностей в биномиальном распределении. Например, вероятность выпадения ровно \(k\) орлов при \(n\) подбрасываниях монеты равна \(\binom{n}{k} / 2^n\).

¶Алгебра

Треугольник Паскаля напрямую связан с формулой бинома Ньютона:

\[ (a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k \]

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

¶Дискретная математика

Треугольник используется для построения кодов Хэмминга, в теории графов (например, для подсчёта числа путей в решётке) и в криптографии.

¶Вычислительная математика

Биномиальные коэффициенты применяются в алгоритмах численного интегрирования, в интерполяции (например, в схеме Горнера) и при аппроксимации функций.

¶Примеры использования

¶Разложение бинома

Для \((a+b)^4\) строка 4 треугольника даёт коэффициенты: 1, 4, 6, 4, 1. Следовательно:

\[ (a+b)^4 = a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4 \]

¶Подсчёт числа путей

Количество кратчайших путей из левого верхнего угла в правый нижний угол прямоугольной решётки размером \(m \times n\) равно \(\binom{m+n}{m}\). Например, для решётки 3×3 число путей — \(\binom{6}{3} = 20\), что соответствует числу в строке 6 треугольника.

¶Интересные факты

• В строках треугольника Паскаля, номер которых является простым числом, все внутренние числа (кроме крайних единиц) делятся на это простое число. Например, в строке 5 числа 5 и 10 делятся на 5.
• Треугольник Паскаля можно обобщить на многомерные случаи — например, пирамида Паскаля для трёхмерного пространства.
• В 1970-х годах математик Дональд Кнут предложил использовать треугольник Паскаля для обучения программированию, так как его рекурсивная структура легко реализуется в коде.
• В некоторых культурах треугольник Паскаля использовался для гадания и предсказаний, хотя научного обоснования этому нет.

¶Критика и ограничения

Треугольник Паскаля не является вычислительно эффективным для больших \(n\) при прямом построении, так как числа быстро растут и требуют работы с большими целыми числами. Для практических вычислений биномиальных коэффициентов при больших \(n\) (например, \(n > 1000\)) используются логарифмические методы или приближения, такие как формула Стирлинга. Кроме того, треугольник не даёт информации о знаках коэффициентов в разложении \((a-b)^n\), хотя это легко исправить чередованием знаков.