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

Треугольник Паскаля (арифметический треугольник) — бесконечная таблица биномиальных коэффициентов, имеющая треугольную форму. В этом треугольнике на вершине и по бокам стоят единицы. Каждое число равно сумме двух расположенных над ним чисел. Строки треугольника симметричны относительно вертикальной оси. В большей части западного мира она названа в честь французского математика Блеза Паскаля, хотя за многие столетия до него её изучали и другие математики в исламском мире, Индии, Китае, Германии и Италии. Числа, составляющие треугольник Паскаля, возникают естественным образом в алгебре, комбинаторике, теории вероятностей, математическом анализе, теории чисел.
Схема чисел, образующих треугольник Паскаля, была известна задолго до времён Паскаля. Персидский математик Аль-Караджи (953–1029) написал ныне утерянную книгу, содержащую первую формулировку биномиальных коэффициентов и первое в истории описание треугольника Паскаля. Позднее треугольник также исследовался Омаром Хайямом около 1100 года, поэтому в Иране эту схему называют треугольником Хайяма (перс. مثلث خیام‎). Упоминание треугольной последовательности биномиальных коэффициентов под названием meru-prastaara встречается также в комментарии индийского математика X века Халаюдхи к трудам другого математика, Пингалы. В 1303 году была выпущена книга «Яшмовое зеркало четырёх элементов» китайского математика Чжу Шицзе, в которой был изображен треугольник Паскаля на одной из иллюстраций; считается, что изобрёл его другой китайский математик, Ян Хуэй, поэтому в Китае его называют треугольником Яна Хуэя (кит. 杨辉三角; 楊輝三角).
В Италии треугольник Паскаля иногда называют треугольником Тартальи, поскольку Никколо Тарталья описал эту таблицу на сто лет раньше Паскаля. На титульном листе учебника арифметики, написанного в 1529 году Петером Апианом, астрономом из Ингольштадтского университета, также изображён треугольник Паскаля. А в 1665 году вышла книга Блеза Паскаля «Трактат об арифметическом треугольнике», которая была специально посвящена данной таблице и по содержательности опережала своих европейских предшественников. Позднее треугольник был назван в честь Паскаля Пьером Раймоном де Монмором (1708), который назвал его «таблицей сочетаний г-на Паскаля» (фр. table de M. Pascal pour les combinaisons), и Абрахамом де Муавром (1730), который назвал его «арифметическим треугольником Паскаля» (лат. Triangulum Arithmeticum PASCALIANUM), что стало основой современного западного названия.
Биномиальные коэффициенты часто обозначаются ( n k ) {\displaystyle {\binom {n}{k}}} или C n k {\displaystyle C_{n}^{k}} и читаются как «число сочетаний из n элементов по k».
Существуют простые алгоритмы для вычисления всех элементов ряда или диагонали без предварительного расчёта всех остальных элементов предыдущих рядов или факториалов.
Чтобы рассчитать ряд n {\displaystyle n} с элементами ( n 0 ) , ( n 1 ) , … , ( n n ) {\displaystyle {\tbinom {n}{0}},{\tbinom {n}{1}},\ldots ,{\tbinom {n}{n}}} , начните с ( n 0 ) = 1 {\displaystyle {\tbinom {n}{0}}=1} . Теперь, для каждого последующего элемента, рассчитайте его значение умножая предыдущий результат на дробь с постепенно меняющимися числителем и знаменателем:
Например, для расчёта значений ряда номер 5, дроби будут иметь следующие значения 5 1 {\displaystyle {\tfrac {5}{1}}} , 4 2 {\displaystyle {\tfrac {4}{2}}} , 3 3 {\displaystyle {\tfrac {3}{3}}} , 2 4 {\displaystyle {\tfrac {2}{4}}} и 1 5 {\displaystyle {\tfrac {1}{5}}} , и следовательно элементы ряда ( 5 0 ) = 1 {\displaystyle {\tbinom {5}{0}}=1} , ( 5 1 ) = 1 × 5 1 = 5 {\displaystyle {\tbinom {5}{1}}=1\times {\tfrac {5}{1}}=5} , ( 5 2 ) = 5 × 4 2 = 10 {\displaystyle {\tbinom {5}{2}}=5\times {\tfrac {4}{2}}=10} , и так далее. (Оставшиеся элементы легко получить с помощью симметрии.)
Для расчёта элементов диагоналей ( n 0 ) , ( n + 1 1 ) , ( n + 2 2 ) , … , {\displaystyle {\tbinom {n}{0}},{\tbinom {n+1}{1}},{\tbinom {n+2}{2}},\ldots ,} начните снова с ( n 0 ) = 1 {\displaystyle {\tbinom {n}{0}}=1} и получите последующие элементы путём умножения на определённые дроби:
Например, для расчёта диагонали начиная с ( 5 0 ) {\displaystyle {\tbinom {5}{0}}} , дроби будут следующими 6 1 , 7 2 , 8 3 , … {\displaystyle {\tfrac {6}{1}},{\tfrac {7}{2}},{\tfrac {8}{3}},\ldots } , и следовательно элементы получатся ( 5 0 ) = 1 , ( 6 1 ) = 1 × 6 1 = 6 , ( 7 2 ) = 6 × 7 2 = 21 {\displaystyle {\tbinom {5}{0}}=1,{\tbinom {6}{1}}=1\times {\tfrac {6}{1}}=6,{\tbinom {7}{2}}=6\times {\tfrac {7}{2}}=21} , и так далее. По симметрии эти элементы равны ( 5 5 ) , ( 6 5 ) , ( 7 5 ) {\displaystyle {\tbinom {5}{5}},{\tbinom {6}{5}},{\tbinom {7}{5}}} , и так далее.