Треугольник Паскаля
Треугольник Паскаля (арифметический треугольник) — бесконечная таблица биномиальных коэффициентов, имеющая треугольную форму. В этом треугольнике на вершине и по бокам стоят единицы. Каждое число равно сумме двух расположенных над ним чисел. Строки треугольника симметричны относительно вертикальной оси. В большей части западного мира она названа в честь французского математика Блеза Паскаля, хотя за многие столетия до него её изучали и другие математики в исламском мире<ref>Шаблон:Статья</ref>, Индии<ref>Шаблон:Статья</ref>, Китае, Германии и Италии<ref>Шаблон:Книга</ref>. Числа, составляющие треугольник Паскаля, возникают естественным образом в алгебре, комбинаторике, теории вероятностей, математическом анализе, теории чиселШаблон:Sfn.
История
Схема чисел, образующих арифметический треугольник, была известна задолго до времён Паскаля.
Персидский математик Аль-Караджи (953–1029) написал ныне утерянную книгу, содержащую первую формулировку биномиальных коэффициентов и первое в истории описание треугольника Паскаля<ref>Шаблон:Cite book</ref><ref>The Development of Arabic Mathematics Between Arithmetic and Algebra - R. Rashed "Page 63"</ref><ref>Шаблон:Cite book</ref>. Позднее треугольник также исследовался Омаром Хайямом около 1100 года, поэтому в Иране эту схему называют треугольником Хайяма (перс. Шаблон:Lang-fa2). С X по XVII век можно проследить непрерывное распространение знаний об арифметическом треугольнике в исламском мире<ref>Шаблон:Cite book</ref>.
Упоминание треугольной последовательности биномиальных коэффициентов под названием meru-prastaara встречается также в комментарии индийского математика X века Шаблон:Нп5 к трудам другого математика, ПингалыШаблон:Неавторитетный источник?<ref>Pisipati S. S. The knpwn srcret</ref>. В 1303 году была выпущена книга «Яшмовое зеркало четырёх элементов» китайского математика Чжу Шицзе, в которой был изображен треугольник Паскаля на одной из иллюстраций; считается, что изобрёл его другой китайский математик, Ян Хуэй, поэтому в Китае его называют треугольником Яна Хуэя (кит. 杨辉三角; 楊輝三角).
В Италии треугольник Паскаля иногда называют треугольником Тартальи, поскольку Никколо Тарталья описал эту таблицу на сто лет раньше Паскаля. На титульном листе учебника арифметики, написанного в 1529 году Петером Апианом, астрономом из Шаблон:Iw, также изображён треугольник Паскаля. А в 1665 году<ref name="mem">Шаблон:Статья</ref> вышла книга Блеза Паскаля «Трактат об арифметическом треугольнике»<ref>Шаблон:Статья</ref>, которая была специально посвящена данной таблице и по содержательности опережала своих европейских предшественников. Позднее треугольник был назван в честь Паскаля Пьером Раймоном де Монмором (1708), который назвал его «таблицей сочетаний г-на Паскаля» (фр. table de M. Pascal pour les combinaisons), и Абрахамом де Муавром (1730), который назвал его «арифметическим треугольником Паскаля» (Шаблон:Lang-lat), что стало основой современного западного названия<ref>Шаблон:Cite journal See in particular p. 11.</ref>.
Обозначения и свойства
Биномиальные коэффициенты часто обозначаются <math>\binom{n}{k}</math> или <math>C_n^k</math> и читаются как «число сочетаний из Шаблон:Mvar элементов по Шаблон:Mvar»Шаблон:Sfn.
- Числа треугольника симметричны (равны) относительно вертикальной оси.
- В строке с номером n (нумерация начинается с 0):
- первое и последнее числа равны 1;
- второе и предпоследнее числа равны n;
- третье число равно треугольному числу <math>T_{n-1} = \frac{n(n - 1)}{2}</math>, что также равно сумме номеров предшествующих строк;
- четвёртое число является тетраэдрическим;
- m-е число (при нумерации с 0) равно биномиальному коэффициенту <math>C_n^m = \binom{n}{m} = \frac{n!}{m!(n - m)!}</math>.
- Сумма чисел восходящей диагонали, начинающейся с первого элемента (n − 1)-й строки, есть n-е число Фибоначчи:
- <math>\binom{n - 1}{0} + \binom{n - 2}{1} + \binom{n - 3}{2} + \ldots = F_n.</math>
- Если вычесть из центрального числа в строке с чётным номером соседнее число из той же строки, то получится число Каталана.
- Сумма чисел n-й строки треугольника Паскаля равна <math>2^n</math>.
- Все числа в n-й строке, кроме единиц, делятся на число n тогда и только тогда, когда n является простым числом<ref name="mathworld">Шаблон:MathWorld</ref> (следствие теоремы Люка).
- Если в строке с нечётным номером сложить все числа с порядковыми номерами вида 3n, 3n + 1, 3n + 2, то первые две суммы будут равны, а третья на единицу меньше.
- Каждое число в треугольнике равно количеству способов добраться до него из вершины, перемещаясь либо вправо-вниз, либо влево-вниз.
Выборочное вычисление значений
Существуют простые алгоритмы для вычисления всех элементов ряда или диагонали без предварительного расчёта всех остальных элементов предыдущих рядов или факториалов.
Чтобы рассчитать ряд <math>n</math> с элементами <math>\tbinom{n}{0}, \tbinom{n}{1}, \ldots, \tbinom{n}{n}</math>, начните с <math>\tbinom{n}{0}=1</math>. Теперь, для каждого последующего элемента, рассчитайте его значение умножая предыдущий результат на дробь с постепенно меняющимися числителем и знаменателем:
- <math> {n\choose k}= {n\choose k-1}\times \frac{n+1-k}{k}.</math>
Например, для расчёта значений ряда номер 5, дроби будут иметь следующие значения <math>\tfrac{5}{1}</math>, <math>\tfrac{4}{2}</math>, <math>\tfrac{3}{3}</math>, <math>\tfrac{2}{4}</math> и <math>\tfrac{1}{5}</math>, и следовательно элементы ряда <math>\tbinom{5}{0}=1</math>, <math>\tbinom{5}{1}=1\times\tfrac{5}{1}=5</math>, <math>\tbinom{5}{2}=5\times\tfrac{4}{2}=10</math>, и так далее. (Оставшиеся элементы легко получить с помощью симметрии.)
Для расчёта элементов диагоналей <math>\tbinom{n}{0}, \tbinom{n+1}{1}, \tbinom{n+2}{2},\ldots,</math> начните снова с <math>\tbinom{n}{0} = 1</math> и получите последующие элементы путём умножения на определённые дроби:
- <math> {n+k\choose k}= {n+k-1\choose k-1}\times \frac{n+k}{k}.</math>
Например, для расчёта диагонали начиная с <math>\tbinom{5}{0}</math>, дроби будут следующими <math>\tfrac{6}{1}, \tfrac{7}{2}, \tfrac{8}{3}, \ldots</math>, и следовательно элементы получатся <math>\tbinom{5}{0}=1, \tbinom{6}{1}=1 \times \tfrac{6}{1}=6, \tbinom{7}{2}=6\times\tfrac{7}{2}=21</math>, и так далее. По симметрии эти элементы равны <math>\tbinom{5}{5}, \tbinom{6}{5}, \tbinom{7}{5}</math>, и так далее.