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

Треугольный массив биномиальных коэффициентов в математике

${\displaystyle {\begin{array}{c}1\\1\quad 1\\1\quad 2\quad 1\\1\quad 3\quad 3\quad 1\\1\quad 4\quad 6\quad 4\quad 1\\1\quad 5\quad 10\quad 10\quad 5\quad 1\\1\quad 6\quad 15\quad 20\quad 15\quad 6\quad 1\\1\quad 7\quad 21\quad 35\quad 35\quad 21\quad 7\quad 1\end{array}}}$

Диаграмма, показывающая первые восемь строк треугольника Паскаля.

В математике треугольник Паскаля — это бесконечный треугольный массив биномиальных коэффициентов , которые играют важную роль в теории вероятностей, комбинаторике и алгебре. В большей части западного мира он назван в честь французского математика Блеза Паскаля , хотя другие математики изучали его за столетия до него в Персии, ^[1] Индии, ^[2] Китае, Германии и Италии. ^[3]

Строки треугольника Паскаля традиционно нумеруются, начиная со строки сверху (0-я строка). Элементы в каждой строке нумеруются слева, начиная с и обычно располагаются в шахматном порядке относительно чисел в соседних строках. Треугольник может быть построен следующим образом: в строке 0 (самой верхней строке) есть уникальная ненулевая запись 1. Каждая запись каждой последующей строки строится путем сложения числа выше и слева с числом выше и справа, при этом пустые записи рассматриваются как 0. Например, начальный номер строки 1 (или любой другой строки) равен 1 (сумма 0 и 1), тогда как числа 1 и 3 в строке 3 складываются, чтобы получить число 4 в строке 4. ${\displaystyle n=0}$ ${\displaystyle k=0}$

Формула

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

В th строке треугольника Паскаля th запись обозначается , произносится как " n choose k ". Например, самая верхняя запись - . С этой нотацией конструкция предыдущего абзаца может быть записана как ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle {\tbinom {0}{0}}=1}$

$${\displaystyle {n \choose k}={n-1 \choose k-1}+{n-1 \choose k}}$$для любого положительного целого числа и любого целого числа . ^[4] Эта повторяемость для биномиальных коэффициентов известна как правило Паскаля . ${\displaystyle n}$ ${\displaystyle 0\leq k\leq n}$

История

Треугольник Ян Хуэя , изображенный китайцами с помощью стержневых цифр , появляется в «Нефритовом зеркале четырех неизвестных» , математическом труде Чжу Шицзе , датированном 1303 годом.

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

Схема чисел, образующих треугольник Паскаля, была известна задолго до времен Паскаля. Персидский математик Аль-Караджи (953–1029) написал ныне утерянную книгу, которая содержала первую формулировку биномиальных коэффициентов и первое описание треугольника Паскаля. ^{[5] [6] [7]} Позднее ее повторил Омар Хайям (1048–1131), другой персидский математик; поэтому треугольник также называют треугольником Хайяма ( مثلث خیام ) в Иране. ^[8] Было известно несколько теорем, связанных с треугольником, включая биномиальную теорему . Хайям использовал метод нахождения n-ных корней , основанный на биномиальном разложении, и, следовательно, на биномиальных коэффициентах. ^[1]

Треугольник Паскаля был известен в Китае в начале 11 века благодаря работам китайского математика Цзя Сяня (1010–1070). В 13 веке Ян Хуэй (1238–1298) определил треугольник, и он известен как треугольник Ян Хуэя (杨辉三角;楊輝三角) в Китае. ^[9]

В Европе треугольник Паскаля впервые появился в « Арифметике » Иордана де Немора (XIII век). ^[10] Биномиальные коэффициенты были вычислены Герсонидом в начале XIV века с использованием для них мультипликативной формулы. ^[11] Петрус Апианус (1495–1552) опубликовал полный треугольник на фронтисписе своей книги о деловых вычислениях в 1527 году. ^[12] Михаэль Штифель опубликовал часть треугольника (со второго по средний столбец в каждой строке) в 1544 году, описав его как таблицу фигурных чисел . ^[11] В Италии треугольник Паскаля называют треугольником Тартальи , названным в честь итальянского алгебраиста Тартальи (1500–1577), который опубликовал шесть строк треугольника в 1556 году. ^[11] Джероламо Кардано также опубликовал треугольник, а также аддитивные и мультипликативные правила его построения в 1570 году. ^[11]

« Traité du triangle arithmétique » Паскаля был опубликован посмертно в 1665 году. ^[13] В этом труде Паскаль собрал несколько известных на тот момент результатов о треугольнике и применил их для решения задач по теории вероятностей . Треугольник позже был назван в честь Паскаля Пьером Раймоном де Монмором (1708), который назвал его table de M. Pascal pour les combinaisons (по-французски: таблица сочетаний г-на Паскаля), и Авраамом де Муавром (1730), который назвал его Triangulum Arithmeticum PASCALIANUM (по-латыни: арифметический треугольник Паскаля), что стало основой для современного западного названия. ^[14]

Биномиальные разложения

Визуализация биномиального разложения до 4-й степени

Треугольник Паскаля определяет коэффициенты, которые возникают в биномиальных разложениях . Например, в разложении коэффициентами являются записи во второй строке треугольника Паскаля: , , . $${\displaystyle (x+y)^{2}=x^{2}+2xy+y^{2}=\mathbf {1} x^{2}y^{0}+\mathbf {2} x^{1}y^{1}+\mathbf {1} x^{0}y^{2},}$$ ${\displaystyle {\tbinom {2}{0}}=1}$ ${\displaystyle {\tbinom {2}{1}}=2}$ ${\displaystyle {\tbinom {2}{2}}=1}$

В общем случае теорема о биноме гласит, что при возведении двучлена в положительную целую степень выражение приобретает вид, где коэффициенты — это в точности числа в строке треугольника Паскаля: ${\displaystyle x+y}$ ${\displaystyle n}$ $${\displaystyle (x+y)^{n}=\sum _{k=0}^{n}a_{k}x^{n-k}y^{k}=a_{0}x^{n}+a_{1}x^{n-1}y+a_{2}x^{n-2}y^{2}+\ldots +a_{n-1}xy^{n-1}+a_{n}y^{n},}$$ ${\displaystyle a_{k}}$ ${\displaystyle n}$ $${\displaystyle a_{k}={n \choose k}.}$$

Вся левая диагональ треугольника Паскаля соответствует коэффициенту при в этих биномиальных разложениях, тогда как следующая левая диагональ соответствует коэффициенту при и т.д. ${\displaystyle x^{n}}$ ${\displaystyle x^{n-1}y}$

Чтобы увидеть, как биномиальная теорема связана с простой конструкцией треугольника Паскаля, рассмотрим задачу вычисления коэффициентов разложения через соответствующие коэффициенты , где для простоты мы положили . Предположим тогда, что Теперь ${\displaystyle (x+y)^{n+1}}$ ${\displaystyle (x+1)^{n}}$ ${\displaystyle y=1}$ $${\displaystyle (x+1)^{n}=\sum _{k=0}^{n}a_{k}x^{k}.}$$ $${\displaystyle (x+1)^{n+1}=(x+1)(x+1)^{n}=x(x+1)^{n}+(x+1)^{n}=\sum _{i=0}^{n}a_{i}x^{i+1}+\sum _{k=0}^{n}a_{k}x^{k}.}$$

${\displaystyle {\begin{array}{c}{\dbinom {0}{0}}\\{\dbinom {1}{0}}\quad {\dbinom {1}{1}}\\{\dbinom {2}{0}}\quad {\dbinom {2}{1}}\quad {\dbinom {2}{2}}\\{\dbinom {3}{0}}\quad {\dbinom {3}{1}}\quad {\dbinom {3}{2}}\quad {\dbinom {3}{3}}\\{\dbinom {4}{0}}\quad {\dbinom {4}{1}}\quad {\dbinom {4}{2}}\quad {\dbinom {4}{3}}\quad {\dbinom {4}{4}}\\{\dbinom {5}{0}}\quad {\dbinom {5}{1}}\quad {\dbinom {5}{2}}\quad {\dbinom {5}{3}}\quad {\dbinom {5}{4}}\quad {\dbinom {5}{5}}\end{array}}}$

Первые шесть строк треугольника Паскаля как биномиальные коэффициенты

Два суммирования можно переиндексировать и объединить, чтобы получить ${\displaystyle k=i+1}$ $${\displaystyle {\begin{aligned}\sum _{i=0}^{n}a_{i}x^{i+1}+\sum _{k=0}^{n}a_{k}x^{k}&=\sum _{k=1}^{n+1}a_{k-1}x^{k}+\sum _{k=0}^{n}a_{k}x^{k}\\[4pt]&=\sum _{k=1}^{n}a_{k-1}x^{k}+a_{n}x^{n+1}+a_{0}x^{0}+\sum _{k=1}^{n}a_{k}x^{k}\\[4pt]&=a_{0}x^{0}+\sum _{k=1}^{n}(a_{k-1}+a_{k})x^{k}+a_{n}x^{n+1}\\[4pt]&=x^{0}+\sum _{k=1}^{n}(a_{k-1}+a_{k})x^{k}+x^{n+1}.\end{aligned}}}$$

Таким образом, крайние левые и правые коэффициенты остаются равными 1, и для любого заданного коэффициент члена в многочлене равен , сумме коэффициентов и в предыдущей степени . Это действительно правило нисходящего сложения для построения треугольника Паскаля. ${\displaystyle 0<k<n+1}$ ${\displaystyle x^{k}}$ ${\displaystyle (x+1)^{n+1}}$ ${\displaystyle a_{k-1}+a_{k}}$ ${\displaystyle x^{k-1}}$ ${\displaystyle x^{k}}$ ${\displaystyle (x+1)^{n}}$

Нетрудно превратить этот аргумент в доказательство (методом математической индукции ) биномиальной теоремы.

Так как , то в разложении общего случая коэффициенты одинаковы. ${\displaystyle (a+b)^{n}=b^{n}({\tfrac {a}{b}}+1)^{n}}$

Интересное следствие биномиальной теоремы получается , если задать обе переменные так, что ${\displaystyle x=y=1}$ $${\displaystyle \sum _{k=0}^{n}{n \choose k}={n \choose 0}+{n \choose 1}+\cdots +{n \choose n-1}+{n \choose n}=(1+1)^{n}=2^{n}.}$$

Другими словами, сумма элементов в -й строке треугольника Паскаля равна -й степени числа 2. Это эквивалентно утверждению, что число подмножеств -элементного множества равно , как можно увидеть, заметив, что каждый из элементов может быть независимо включен или исключен из данного подмножества. ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle 2^{n}}$ ${\displaystyle n}$

Комбинации

Второе полезное применение треугольника Паскаля — это расчет комбинаций . Количество комбинаций элементов, взятых за один раз, т.е. количество подмножеств элементов из числа элементов, можно найти с помощью уравнения ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle n}$

${\displaystyle \mathbf {C} (n,k)=\mathbf {C} _{k}^{n}={_{n}C_{k}}={n \choose k}={\frac {n!}{k!(n-k)!}}}$.

Это равно записи в строке треугольника Паскаля. Вместо того, чтобы выполнять мультипликативный расчет, можно просто найти соответствующую запись в треугольнике (построенную путем сложения). Например, предположим, что нужно нанять 3 работников из 7 кандидатов; тогда число возможных вариантов найма равно 7, выбираем 3, запись 3 в строке 7 приведенной выше таблицы, которая равна . ^[15] ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle {\tbinom {7}{3}}=35}$

Связь с биномиальным распределением и свертками

При делении на , th строка треугольника Паскаля становится биномиальным распределением в симметричном случае, когда . По центральной предельной теореме это распределение приближается к нормальному распределению с увеличением. Это также можно увидеть, применив формулу Стирлинга к факториалам, участвующим в формуле для комбинаций. ${\displaystyle 2^{n}}$ ${\displaystyle n}$ ${\displaystyle p={\tfrac {1}{2}}}$ ${\displaystyle n}$

Это связано с операцией дискретной свертки двумя способами. Во-первых, умножение полиномов точно соответствует дискретной свертке, так что многократное свертывание последовательности с собой соответствует взятию степеней , и, следовательно, генерации строк треугольника. Во-вторых, многократное свертывание функции распределения для случайной величины с собой соответствует вычислению функции распределения для суммы n независимых копий этой переменной; это именно та ситуация, к которой применима центральная предельная теорема, и, следовательно, приводит к нормальному распределению в пределе. (Операция многократного взятия свертки чего-либо с собой называется степенью свертки .) ${\displaystyle \{\ldots ,0,0,1,1,0,0,\ldots \}}$ ${\displaystyle x+1}$

Модели и свойства

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

Каждый кадр представляет строку в треугольнике Паскаля. Каждый столбец пикселей — это число в двоичном коде с младшим битом внизу. Светлые пиксели представляют 1, а темные пиксели — 0.

Числа композиций n  +1 в k +1 упорядоченных разбиений образуют  треугольник Паскаля.

Ряды

• Сумма элементов одной строки в два раза больше суммы предыдущей строки. Например, строка 0 (самая верхняя строка) имеет значение 1, строка 1 имеет значение 2, строка 2 имеет значение 4 и т. д. Это происходит потому, что каждый элемент в строке производит два элемента в следующей строке: один слева и один справа. Сумма элементов строки  равна . ${\displaystyle n}$ ${\displaystyle 2^{n}}$
• Взяв произведение элементов в каждой строке, последовательность произведений (последовательность A001142 в OEIS ) связана с основанием натурального логарифма, e . ^{[16] [17]} В частности, определим последовательность для всех следующим образом: ${\displaystyle s_{n}}$ ${\displaystyle n\geq 0}$ ${\displaystyle s_{n}=\prod _{k=0}^{n}{n \choose k}=\prod _{k=0}^{n}{\frac {n!}{k!(n-k)!}}}$
  Тогда отношение последовательных строковых произведений равно , а отношение этих отношений равно Правая часть приведенного выше уравнения принимает форму предельного определения . $${\displaystyle {\frac {s_{n+1}}{s_{n}}}={\frac {\displaystyle (n+1)!^{n+2}\prod _{k=0}^{n+1}{\frac {1}{k!^{2}}}}{\displaystyle n!^{n+1}\prod _{k=0}^{n}{\frac {1}{k!^{2}}}}}={\frac {(n+1)^{n}}{n!}}}$$ $${\displaystyle {\frac {s_{n+1}\cdot s_{n-1}}{s_{n}^{2}}}=\left({\frac {n+1}{n}}\right)^{n},~n\geq 1.}$$ ${\displaystyle e}$ $${\displaystyle e=\lim _{n\to \infty }\left(1+{\frac {1}{n}}\right)^{n}}$$
• ${\displaystyle \pi }$можно найти в треугольнике Паскаля с помощью бесконечного ряда Нилаканта . ^[18] $${\displaystyle \pi =3+\sum _{n=1}^{\infty }(-1)^{n+1}{\frac {2n+1 \choose 1}{{2n+1 \choose 2}{2n+2 \choose 2}}}}$$
• Некоторые числа в треугольнике Паскаля соответствуют числам в треугольнике Лозанича .
• Сумма квадратов элементов строки  n равна среднему элементу строки  2 n . Например, 1 ² + 4 ² + 6 ² + 4 ² + 1 ² = 70 . В общем виде, $${\displaystyle \sum _{k=0}^{n}{n \choose k}^{2}={2n \choose n}.}$$
• В любой четной строке средний член минус член на две позиции левее равняется каталонскому числу , а именно . Например, в строке 4, которая есть 1, 4, 6, 4, 1, мы получаем 3-е каталонское число . ${\displaystyle n=2m}$ ${\displaystyle C_{m-1}={\tbinom {2m}{m}}-{\tbinom {2m}{m-2}}}$ ${\displaystyle C_{3}=6-1=5}$
• В строке  p , где p — простое число , все члены в этой строке, за исключением единиц, делятся на p . Это можно легко доказать с помощью формулы умножения . Поскольку знаменатель не может иметь простых множителей, равных p , то p остается в числителе после целочисленного деления, делая всю запись кратной p . ${\displaystyle {\tbinom {p}{k}}={\tfrac {p!}{k!(p-k)!}}}$ ${\displaystyle k!(p-k)!}$
• Четность : Чтобы подсчитать нечетные члены в строке  n , преобразуйте n в двоичную систему счисления . Пусть x будет числом единиц в двоичном представлении. Тогда число нечетных членов будет 2 ^x . Эти числа являются значениями в последовательности Гулда . ^[19]
• Каждая запись в строке 2 ⁿ  − 1, n  ≥ 0, является нечетной. ^[20]
• Полярность : когда элементы строки треугольника Паскаля попеременно складываются и вычитаются, результат равен 0. Например, строка 6 — это 1, 6, 15, 20, 15, 6, 1, поэтому формула имеет вид 1 − 6 + 15 − 20 + 15 − 6 + 1 = 0.

Диагонали

Вывод симплексных чисел из треугольника Паскаля, выровненного слева

Диагонали треугольника Паскаля содержат фигурные числа симплексов:

• Диагонали, проходящие вдоль левого и правого краев, содержат только единицы.
• Диагонали рядом с диагоналями края содержат натуральные числа по порядку. Числа одномерного симплекса увеличиваются на 1 по мере того, как отрезки линии расширяются до следующего целого числа вдоль числовой оси.
• Двигаясь внутрь, следующая пара диагоналей содержит треугольные числа по порядку.
• Следующая пара диагоналей содержит тетраэдрические числа по порядку, а следующая пара дает пентатопные числа .

${\displaystyle {\begin{aligned}P_{0}(n)&=P_{d}(0)=1,\\P_{d}(n)&=P_{d}(n-1)+P_{d-1}(n)\\&=\sum _{i=0}^{n}P_{d-1}(i)=\sum _{i=0}^{d}P_{i}(n-1).\end{aligned}}}$

Симметрия треугольника подразумевает, что n- ^е d-мерное число равно d - ^му n -мерному числу.

Альтернативная формула, не включающая рекурсию, — это где n ^{( d )} — возрастающий факториал . $${\displaystyle P_{d}(n)={\frac {1}{d!}}\prod _{k=0}^{d-1}(n+k)={n^{(d)} \over d!}={\binom {n+d-1}{d}},}$$

Геометрический смысл функции P _d таков: P _d (1) = 1 для всех d . Постройте d - мерный треугольник (трехмерный треугольник - это тетраэдр ), разместив дополнительные точки под начальной точкой, что соответствует P _d (1) = 1. Разместите эти точки аналогично размещению чисел в треугольнике Паскаля. Чтобы найти P _d ( x ), имейте в общей сложности x точек, составляющих целевую фигуру. Тогда P _d ( x ) равно общему количеству точек в фигуре. 0-мерный треугольник - это точка, а 1-мерный треугольник - это просто линия, и поэтому P ₀ ( x ) = 1 и P ₁ ( x ) = x , что является последовательностью натуральных чисел. Количество точек в каждом слое соответствует P _{d  − 1} ( x ).

Вычисление строки или диагонали отдельно

Существуют простые алгоритмы для вычисления всех элементов в строке или диагонали без вычисления других элементов или факториалов.

Для вычисления строки с элементами начните с . Для каждого последующего элемента значение определяется путем умножения предыдущего значения на дробь с медленно меняющимися числителем и знаменателем: ${\displaystyle n}$ ${\displaystyle {\tbinom {n}{0}},{\tbinom {n}{1}},\ldots ,{\tbinom {n}{n}}}$ ${\displaystyle {\tbinom {n}{0}}=1}$

${\displaystyle {n \choose k}={n \choose k-1}\times {\frac {n+1-k}{k}}.}$

Например, для вычисления строки 5 дроби равны  ,  ,  ,  и , а следовательно, элементы равны  ,   ,   , и т. д. (Остальные элементы проще всего получить с помощью симметрии.) ${\displaystyle {\tfrac {5}{1}}}$ ${\displaystyle {\tfrac {4}{2}}}$ ${\displaystyle {\tfrac {3}{3}}}$ ${\displaystyle {\tfrac {2}{4}}}$ ${\displaystyle {\tfrac {1}{5}}}$ ${\displaystyle {\tbinom {5}{0}}=1}$ ${\displaystyle {\tbinom {5}{1}}=1\times {\tfrac {5}{1}}=5}$ ${\displaystyle {\tbinom {5}{2}}=5\times {\tfrac {4}{2}}=10}$

Чтобы вычислить диагональ, содержащую элементы, снова начните с и получите последующие элементы путем умножения на определенные дроби: ${\displaystyle {\tbinom {n}{0}},{\tbinom {n+1}{1}},{\tbinom {n+2}{2}},\ldots ,}$ ${\displaystyle {\tbinom {n}{0}}=1}$

${\displaystyle {n+k \choose k}={n+k-1 \choose k-1}\times {\frac {n+k}{k}}.}$

Например, для вычисления диагонали, начинающейся в , дроби равны  , а элементы равны , и т.д. По симметрии эти элементы равны , и т.д. ${\displaystyle {\tbinom {5}{0}}}$ ${\displaystyle {\tfrac {6}{1}},{\tfrac {7}{2}},{\tfrac {8}{3}},\ldots }$ ${\displaystyle {\tbinom {5}{0}}=1,{\tbinom {6}{1}}=1\times {\tfrac {6}{1}}=6,{\tbinom {7}{2}}=6\times {\tfrac {7}{2}}=21}$ ${\displaystyle {\tbinom {5}{5}},{\tbinom {6}{5}},{\tbinom {7}{5}}}$

Последовательность Фибоначчи в треугольнике Паскаля

Общие закономерности и свойства

Приближение уровня 4 к треугольнику Серпинского, полученное путем закрашивания первых 32 строк треугольника Паскаля белым цветом, если биномиальный коэффициент четный, и черным цветом, если он нечетный.

• Рисунок, полученный путем раскрашивания только нечетных чисел в треугольнике Паскаля, очень похож на фрактал, известный как треугольник Серпинского . Это сходство становится все более точным по мере рассмотрения большего количества строк; в пределе, когда число строк приближается к бесконечности, результирующий рисунок представляет собой треугольник Серпинского, предполагая фиксированный периметр. В более общем смысле, числа могут быть окрашены по-разному в зависимости от того, являются ли они кратными 3, 4 и т. д.; это приводит к другим похожим рисункам.

Поскольку доля черных чисел стремится к нулю с ростом n , следствием этого является то, что доля нечетных биномиальных коэффициентов стремится к нулю, когда n стремится к бесконечности. ^[21]

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

• В треугольной части сетки (как на изображениях ниже) число кратчайших путей сетки от заданного узла до верхнего узла треугольника является соответствующей записью в треугольнике Паскаля. На игровом поле Plinko, имеющем форму треугольника, это распределение должно давать вероятности выигрыша различных призов.

• Если строки треугольника Паскаля выровнены по левому краю, то диагональные полосы (отмечены цветом ниже) в сумме дают числа Фибоначчи .

Построение как матричной экспоненты

${\displaystyle {\begin{aligned}\exp {\begin{pmatrix}.&.&.&.&.\\1&.&.&.&.\\.&2&.&.&.\\.&.&3&.&.\\.&.&.&4&.\end{pmatrix}}&={\begin{pmatrix}1&.&.&.&.\\1&1&.&.&.\\1&2&1&.&.\\1&3&3&1&.\\1&4&6&4&1\end{pmatrix}}\\e^{\text{counting}}&={\text{binomial}}\end{aligned}}}$

Биномиальная матрица как экспоненциальная матрица. Все точки представляют 0.

Благодаря простоте построения с помощью факториалов можно дать очень простое представление треугольника Паскаля в терминах матричной экспоненты : Треугольник Паскаля — это экспонента матрицы, которая имеет последовательность 1, 2, 3, 4, ... на своей поддиагонали и ноль во всех остальных местах.

Построение алгебры Клиффорда с использованием симплексов

Маркировка элементов каждого n-симплекса соответствует базисным элементам алгебры Клиффорда, используемым в качестве форм в геометрической алгебре, а не матрицам. Распознавание геометрических операций, таких как вращения, позволяет обнаружить алгебраические операции. Так же, как каждая строка, n , начиная с 0, треугольника Паскаля соответствует (n-1) -симплексу, как описано ниже, она также определяет количество именованных базисных форм в n- мерной геометрической алгебре . Биномиальная теорема может быть использована для доказательства геометрической связи, предоставляемой треугольником Паскаля. ^[22] Это же доказательство можно применить к симплексам, за исключением того, что первый столбец всех единиц должен игнорироваться, тогда как в алгебре они соответствуют действительным числам, , с базисом 1. ${\displaystyle \mathbb {R} }$

Связь с геометрией многогранников

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

Число элементов симплексов

Давайте начнем с рассмотрения 3-й строки треугольника Паскаля со значениями 1, 3, 3, 1. Двумерный треугольник имеет один двумерный элемент (сам), три одномерных элемента (линии или ребра) и три нульмерных элемента ( вершины или углы). Значение последнего числа (1) объяснить сложнее (но см. ниже). Продолжая наш пример, тетраэдр имеет один трехмерный элемент (сам), четыре двумерных элемента (грани), шесть одномерных элементов (ребра) и четыре нульмерных элемента (вершины). Добавляя последнюю 1 снова, эти значения соответствуют 4-й строке треугольника (1, 4, 6, 4, 1). Линия 1 соответствует точке, а линия 2 соответствует отрезку линии (диаде). Этот шаблон продолжается до произвольно высокоразмерных гипертетраэдров (известных как симплексы ).

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

Число заданного размерного элемента в тетраэдре теперь является суммой двух чисел: во-первых, числа этого элемента, найденного в исходном треугольнике, плюс число новых элементов, каждый из которых построен на элементах на одну размерность меньше из исходного треугольника . Таким образом, в тетраэдре число ячеек (многогранных элементов) равно 0 + 1 = 1 ; число граней равно 1 + 3 = 4 ; число ребер равно 3 + 3 = 6 ; число новых вершин равно 3 + 1 = 4. Этот процесс суммирования числа элементов заданной размерности с числами на одну размерность меньше для получения числа первых, найденных в следующем более высоком симплексе, эквивалентен процессу суммирования двух соседних чисел в строке треугольника Паскаля для получения числа ниже. Таким образом, значение последнего числа (1) в строке треугольника Паскаля становится понятным как представляющее новую вершину, которая должна быть добавлена ​​к симплексу, представленному этой строкой, чтобы получить следующий более высокий симплекс, представленный следующей строкой. Эта новая вершина присоединяется к каждому элементу в исходном симплексе, чтобы получить новый элемент на одно более высокое измерение в новом симплексе, и это является источником паттерна, который, как обнаружено, идентичен тому, который виден в треугольнике Паскаля.

Количество элементов гиперкуба

Похожая закономерность наблюдается в отношении квадратов , в отличие от треугольников. Чтобы найти закономерность, нужно построить аналог треугольника Паскаля, элементы которого являются коэффициентами ( x + 2) ^{номера строки} , вместо ( x + 1) ^{номера строки} . Есть несколько способов сделать это. Самый простой — начать со строки 0 = 1 и строки 1 = 1, 2. Продолжайте строить аналоговые треугольники в соответствии со следующим правилом:

${\displaystyle {n \choose k}=2\times {n-1 \choose k-1}+{n-1 \choose k}.}$

То есть, выбираем пару чисел в соответствии с правилами треугольника Паскаля, но удваиваем то, что слева, перед сложением. Это дает:

${\displaystyle {\begin{matrix}{\text{ 1}}\\{\text{ 1}}\quad {\text{ 2}}\\{\text{ 1}}\quad {\text{ 4}}\quad {\text{ 4}}\\{\text{ 1}}\quad {\text{ 6}}\quad {\text{ 12}}\quad {\text{ 8}}\\{\text{ 1}}\quad {\text{ 8}}\quad {\text{ 24}}\quad {\text{ 32}}\quad {\text{ 16}}\\{\text{ 1}}\quad {\text{ 10}}\quad {\text{ 40}}\quad {\text{ 80}}\quad {\text{ 80}}\quad {\text{ 32}}\\{\text{ 1}}\quad {\text{ 12}}\quad {\text{ 60}}\quad 160\quad 240\quad 192\quad {\text{ 64}}\\{\text{ 1}}\quad {\text{ 14}}\quad {\text{ 84}}\quad 280\quad 560\quad 672\quad 448\quad 128\end{matrix}}}$

Другой способ создания этого треугольника — начать с треугольника Паскаля и умножить каждую запись на 2k ^, где k — это позиция в строке данного числа. Например, 2-е значение в строке 4 треугольника Паскаля равно 6 (наклон 1s соответствует нулевой записи в каждой строке). Чтобы получить значение, которое находится в соответствующей позиции в аналоговом треугольнике, умножьте 6 на 2 ^{номер позиции} = 6 × 2 ² = 6 × 4 = 24. Теперь, когда аналоговый треугольник построен, количество элементов любого измерения, которые составляют куб произвольного размера (называемый гиперкубом ), можно прочитать из таблицы способом, аналогичным треугольнику Паскаля. Например, количество 2-мерных элементов в 2-мерном кубе (квадрате) равно одному, количество 1-мерных элементов (сторон или линий) равно 4, а количество 0-мерных элементов (точек или вершин) равно 4. Это соответствует 2-й строке таблицы (1, 4, 4). Куб имеет 1 куб, 6 граней, 12 ребер и 8 вершин, что соответствует следующей строке аналогового треугольника (1, 6, 12, 8). Этот шаблон продолжается бесконечно.

Чтобы понять, почему существует эта закономерность, сначала осознайте, что построение n -куба из ( n − 1) -куба выполняется путем простого дублирования исходной фигуры и смещения ее на некоторое расстояние (для обычного n -куба длина ребра) ортогонально пространству исходной фигуры, а затем соединения каждой вершины новой фигуры с соответствующей ей вершиной оригинала. Этот начальный процесс дублирования является причиной того, почему для перечисления размерных элементов n -куба необходимо удвоить первое из пары чисел в строке этого аналога треугольника Паскаля перед суммированием для получения числа ниже. Таким образом, начальное удвоение дает количество «исходных» элементов, которые должны быть найдены в следующем более высоком n -кубе, и, как и прежде, новые элементы строятся на элементах с меньшим измерением (ребра на вершинах, грани на ребрах и т. д.). Опять же, последнее число строки представляет собой количество новых вершин, которые должны быть добавлены для создания следующего более высокого n -куба.

В этом треугольнике сумма элементов строки m равна 3 ^m . Опять же, если использовать элементы строки 4 в качестве примера: 1 + 8 + 24 + 32 + 16 = 81 , что равно . ${\displaystyle 3^{4}=81}$

Подсчет вершин в кубе по расстоянию

Каждая строка треугольника Паскаля дает количество вершин на каждом расстоянии от фиксированной вершины в n -мерном кубе. Например, в трех измерениях третья строка (1 3 3 1) соответствует обычному трехмерному кубу : фиксируя вершину V , есть одна вершина на расстоянии 0 от V (то есть сама V ), три вершины на расстоянии 1, три вершины на расстоянии √ 2 и одна вершина на расстоянии √ 3 (вершина напротив V ). Вторая строка соответствует квадрату, в то время как строки с большими номерами соответствуют гиперкубам в каждом измерении.

Преобразование Фурье sin(х)н +1/х

Как было сказано ранее, коэффициенты ( x  + 1) ⁿ являются n-й строкой треугольника. Теперь коэффициенты ( x  − 1) ⁿ те же самые, за исключением того, что знак меняется с +1 на −1 и обратно. После соответствующей нормализации та же самая последовательность чисел возникает в преобразовании Фурье sin( x ) ^{n +1} / x . Точнее: если n четное, берем действительную часть преобразования, а если n нечетное, берем мнимую часть . Тогда результатом является ступенчатая функция , значения которой (соответствующим образом нормализованные) задаются n- й строкой треугольника с чередующимися знаками. ^[23] Например, значения ступенчатой ​​функции, которая получается из:

${\displaystyle {\mathfrak {Re}}\left({\text{Fourier}}\left[{\frac {\sin(x)^{5}}{x}}\right]\right)}$

составляют 4-ю строку треугольника, с чередующимися знаками. Это обобщение следующего основного результата (часто используемого в электротехнике ):

${\displaystyle {\mathfrak {Re}}\left({\text{Fourier}}\left[{\frac {\sin(x)^{1}}{x}}\right]\right)}$

является функцией boxcar . ^[24] Соответствующая строка треугольника — это строка 0, которая состоит только из числа 1.

Если n сравнимо с 2 или 3 mod 4, то знаки начинаются с −1. Фактически, последовательность (нормализованных) первых членов соответствует степеням i , которые циклически повторяют точку пересечения осей с единичной окружностью в комплексной плоскости: $${\displaystyle +i,-1,-i,+1,+i,\ldots }$$

Расширения

Треугольник Паскаля можно расширить вверх, выше 1 в вершине, сохранив аддитивное свойство, но сделать это можно разными способами. ^[25]

К высшим измерениям

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

К комплексным числам

Когда функция факториала определена как , треугольник Паскаля может быть расширен за пределы целых чисел до , поскольку является мероморфным всей комплексной плоскости . ^[26] ${\displaystyle z!=\Gamma (z+1)}$ ${\displaystyle \mathbb {C} }$ ${\displaystyle \Gamma (z+1)}$

К произвольным основаниям

Исаак Ньютон однажды заметил, что первые пять строк треугольника Паскаля, если их читать как цифры целого числа, являются соответствующими степенями одиннадцати. Он утверждал без доказательств, что последующие строки также генерируют степени одиннадцати. ^[27] В 1964 году Роберт Л. Мортон представил более обобщенный аргумент о том, что каждая строка может быть прочитана как система счисления с основанием, где — гипотетическая конечная строка, или предел , треугольника, а строки — ее частичные произведения. ^[28] Он доказал, что записи строки , если их интерпретировать непосредственно как разрядное число, соответствуют биномиальному разложению . С тех пор были разработаны более строгие доказательства. ^{[29] [30]} Чтобы лучше понять принцип, лежащий в основе этой интерпретации, вот некоторые вещи, которые следует вспомнить о биномах: ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle \lim _{n\to \infty }11_{a}^{n}}$ ${\displaystyle n}$ ${\displaystyle (a+1)^{n}=11_{a}^{n}}$

• Основание системы счисления в позиционной записи (например, ) — это одномерный многочлен от переменной , где степень переменной -го члена ( начиная с ) равна . Например, . ${\displaystyle a}$ ${\displaystyle 14641_{a}}$ ${\displaystyle a}$ ${\displaystyle i}$ ${\displaystyle i=0}$ ${\displaystyle i}$ ${\displaystyle 14641_{a}=1\cdot a^{4}+4\cdot a^{3}+6\cdot a^{2}+4\cdot a^{1}+1\cdot a^{0}}$
• Строка соответствует биномиальному разложению . Переменная может быть исключена из разложения, установив . Теперь разложение представляет собой развернутую форму системы счисления с основанием , ^{[31] [32],} как показано выше. Таким образом, когда записи строки объединяются и считываются в системе с основанием, они образуют числовой эквивалент . Если для , то теорема верна для с нечетными значениями, дающими отрицательные произведения строк. ^{[33] [34] [35]} ${\displaystyle (a+b)^{n}}$ ${\displaystyle b}$ ${\displaystyle b=1}$ ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle (a+1)^{n}=11_{a}^{n}}$ ${\displaystyle c=a+1}$ ${\displaystyle c<0}$ ${\displaystyle a=\{c-1,-(c+1)\}\;\mathrm {mod} \;2c}$ ${\displaystyle n}$

При установке основания строки (переменной ) равным единице и десяти, строка становится произведением и , соответственно. Для иллюстрации рассмотрим , что дает произведение строк . Числовое представление формируется путем конкатенации записей строки . Двенадцатая строка обозначает произведение: ${\displaystyle a}$ ${\displaystyle n}$ ${\displaystyle 11_{1}^{n}=2^{n}}$ ${\displaystyle 11_{10}^{n}=11^{n}}$ ${\displaystyle a=n}$ ${\displaystyle \textstyle n^{n}\left(1+{\frac {1}{n}}\right)^{n}=11_{n}^{n}}$ ${\displaystyle 11_{n}^{n}}$ ${\displaystyle n}$

${\displaystyle 11_{12}^{12}=1:10:56:164:353:560:650:560:353:164:56:10:1_{12}=27433a9699701_{12}}$

с составными цифрами (разделенными знаком ":") в системе счисления с основанием двенадцать. Цифры от до являются составными, поскольку эти записи строк вычисляются до значений, больших или равных двенадцати. Чтобы нормализовать ^[36] число, просто перенесите префикс первой составной записи, то есть удалите префикс коэффициента от ее самой левой цифры до, но исключая ее самую правую цифру, и используйте арифметику с основанием двенадцать для суммирования удаленного префикса с записью, расположенной непосредственно слева от нее, затем повторите этот процесс, двигаясь влево, пока не будет достигнута самая левая запись. В этом конкретном примере нормализованная строка заканчивается на for all . Самая левая цифра — это for , которая получается путем переноса of в запись . Из этого следует, что длина нормализованного значения равна длине строки, . Целая часть содержит ровно одну цифру, поскольку (количество знаков слева, на которые переместилась десятичная дробь) на единицу меньше длины строки. Ниже приведено нормализованное значение . Составные цифры остаются в значении, поскольку они представляют собой остатки системы счисления, представленные в системе счисления с основанием десять: ${\displaystyle k=n-1}$ ${\displaystyle k=1}$ ${\displaystyle \textstyle {n \choose n-1}}$ ${\displaystyle 01}$ ${\displaystyle n}$ ${\displaystyle 2}$ ${\displaystyle n>2}$ ${\displaystyle 1}$ ${\displaystyle 10_{n}}$ ${\displaystyle k=1}$ ${\displaystyle 11_{n}^{n}}$ ${\displaystyle n+1}$ ${\displaystyle 1.1_{n}^{n}}$ ${\displaystyle n}$ ${\displaystyle 1.1_{1234}^{1234}}$ ${\displaystyle 1234}$

${\displaystyle 1.1_{1234}^{1234}=2.885:2:35:977:696:\overbrace {\ldots } ^{\text{1227 digits}}:0:1_{1234}=2.717181235\ldots _{10}}$

Смотрите также

• Машина для производства бобов , «квинконс» Фрэнсиса Гальтона
• Треугольник Белла
• Треугольник Бернулли
• Биномиальное разложение
• Клеточные автоматы
• треугольник Эйлера
• Треугольник Флойда
• Гауссовский биномиальный коэффициент
• Идентичность хоккейной клюшки
• Гармонический треугольник Лейбница
• Кратности элементов в треугольнике Паскаля (гипотеза Зингмастера)
• Матрица Паскаля
• Пирамида Паскаля
• симплекс Паскаля
• Протонный ЯМР , одно из применений треугольника Паскаля
• Теорема о звезде Давида
• Трехчленное разложение
• Треугольник с тремя членами
• Многочлены, вычисляющие суммы степеней арифметических прогрессий

Ссылки

1. Кулидж, Дж. Л. (1949), «История биномиальной теоремы», The American Mathematical Monthly , 56 (3): 147–157, doi : 10.2307/2305028, JSTOR  2305028, MR  0028222.
2. Морис Винтерниц, История индийской литературы , т. III
3. Питер Фокс (1998). Библиотека Кембриджского университета: великие коллекции. Cambridge University Press. стр. 13. ISBN 978-0-521-62647-7.
4. Биномиальный коэффициент обычно принимается равным нулю, если k меньше нуля или больше n . ${\displaystyle \scriptstyle {n \choose k}}$
5. Селин, Хелайн (2008-03-12). Энциклопедия истории науки, технологий и медицины в не-западных культурах. Springer Science & Business Media. стр. 132. Bibcode :2008ehst.book.....S. ISBN 9781402045592.
6. Развитие арабской математики между арифметикой и алгеброй - Р. Рашед "Страница 63"
7. Сидоли, Натан; Бруммелен, Глен Ван (2013-10-30). Из Александрии через Багдад: обзоры и исследования древнегреческих и средневековых исламских математических наук в честь Дж. Л. Берггрена. Springer Science & Business Media. стр. 54. ISBN 9783642367366.
8. Кеннеди, Э. (1966). Омар Хайям. Учитель математики 1958. Национальный совет учителей математики. С. 140–142. JSTOR  i27957284.
9. Вайсштейн, Эрик В. (2003). Краткая энциклопедия математики CRC , стр. 2169. ISBN 978-1-58488-347-0 . 
10. Хьюз, Варнава (1 августа 1989 г.). «Арифметический треугольник Иордана де Немора». История математики . 16 (3): 213–223. дои : 10.1016/0315-0860(89)90018-9 .
11. Эдвардс, AWF (2013), «Арифметический треугольник», в Уилсон, Робин; Уоткинс, Джон Дж. (ред.), Комбинаторика: Древняя и современная , Oxford University Press, стр. 166–180.
12. Смит, Карл Дж. (2010), Природа математики, Cengage Learning, стр. 10, ISBN 9780538737586.
13. Traité du треугольник арифметика, avec quelques autres petits Traitez sur la mesme matière и Gallica
14. Фаулер, Дэвид (январь 1996 г.). «Функция биномиального коэффициента». The American Mathematical Monthly . 103 (1): 1–17. doi :10.2307/2975209. JSTOR  2975209.См. в частности стр. 11.
15. "Треугольник Паскаля в теории вероятностей". 5010.mathed.usu.edu . Получено 01.06.2023 .
16. Brothers, HJ (2012), «Нахождение e в треугольнике Паскаля», Mathematics Magazine , 85 : 51, doi : 10.4169/math.mag.85.1.51, S2CID  218541210.
17. Братья, HJ (2012), «Треугольник Паскаля: скрытое хранилище » , The Mathematical Gazette , 96 : 145–148, doi :10.1017/S0025557200004204, S2CID  233356674.
18. Фостер, Т. (2014), «Следы Нилаканты в треугольнике Паскаля», Учитель математики , 108 : 247, doi : 10.5951/mathteacher.108.4.0246
19. Файн, Нью-Джерси (1947), «Биномиальные коэффициенты по модулю простого числа», American Mathematical Monthly , 54 (10): 589–592, doi :10.2307/2304500, JSTOR  2304500, MR  0023257. См. в частности теорему 2, которая дает обобщение этого факта для всех простых модулей.
20. Хинц, Андреас М. (1992), «Треугольник Паскаля и Ханойская башня», The American Mathematical Monthly , 99 (6): 538–544, doi :10.2307/2324061, JSTOR  2324061, MR  1166003. Хинц приписывает это наблюдение книге Эдуарда Люка 1891 года « Теория чисел» (стр. 420).
21. Ян Стюарт, «Как разрезать торт», Oxford University Press, стр. 180
22. Уилмот, ГП (2023), Алгебра геометрии
23. Похожий пример см., например, в Hore, PJ (1983), «Подавление растворителя в ядерном магнитном резонансе с преобразованием Фурье», Journal of Magnetic Resonance , 55 (2): 283–300, Bibcode : 1983JMagR..55..283H, doi : 10.1016/0022-2364(83)90240-8.
24. Карл, Джон Х. (2012), Введение в цифровую обработку сигналов, Elsevier, стр. 110, ISBN 9780323139595.
25. Хилтон, П.; и др. (1989). «Расширение биномиальных коэффициентов для сохранения симметрии и шаблона». Симметрия 2. В Международной серии по современной прикладной математике и информатике. Пергам. С. 89–102. doi :10.1016/B978-0-08-037237-2.50013-1. ISBN 9780080372372..
26. Хилтон, П.; и др. (1989). «Расширение биномиальных коэффициентов для сохранения симметрии и шаблона». Симметрия 2. В Международной серии по современной прикладной математике и информатике. Pergamon. стр. 100–102. doi :10.1016/B978-0-08-037237-2.50013-1. ISBN 9780080372372..
27. Ньютон, Исаак (1736), «Трактат о методе флюксий и бесконечных рядов», Математические труды Исаака Ньютона : 1:31–33, Но эти в альтернативных областях, которые даны, я заметил, были теми же самыми с фигурами, из которых состоят различные восходящие степени числа 11, а именно , , , , , и т. д. то есть, первая 1; вторая 1, 1; третья 1, 2, 1; четвертая 1, 3, 3, 1; пятая 1, 4, 6, 4, 1 и т. д. ${\displaystyle 11^{0}}$ ${\displaystyle 11^{1}}$ ${\displaystyle 11^{2}}$ ${\displaystyle 11^{3}}$ ${\displaystyle 11^{4}}$.
28. Мортон, Роберт Л. (1964), «Треугольник Паскаля и степени 11», Учитель математики , 57 (6): 392–394, doi :10.5951/MT.57.6.0392, JSTOR  27957091.
29. Арнольд, Роберт и др. (2004), «Незаконченное дело Ньютона: раскрытие скрытых степеней одиннадцати в треугольнике Паскаля», Труды Дня математики для студентов.
30. Ислам, Робиул и др. (2020), Нахождение любой строки треугольника Паскаля, расширяющей концепцию степени 11.
31. Winteridge, David J. (1984), «Треугольник Паскаля и степени числа 11», Математика в школе , 13 (1): 12–13, JSTOR  30213884.
32. Каллос, Габор (2006), «Обобщение треугольника Паскаля с использованием степеней базовых чисел» (PDF) , Annales Mathématiques , 13 (1): 1–15, doi :10.5802/ambp.211.
33. Хилтон, П.; и др. (1989). «Расширение биномиальных коэффициентов для сохранения симметрии и шаблона». Симметрия 2. В Международной серии по современной прикладной математике и информатике. Пергам. С. 89–91. doi :10.1016/B978-0-08-037237-2.50013-1. ISBN 9780080372372..
34. Мюллер, Фрэнсис Дж. (1965), «Еще о треугольнике Паскаля и степенях числа 11», Учитель математики , 58 (5): 425–428, doi :10.5951/MT.58.5.0425, JSTOR  27957164.
35. Лоу, Леоне (1966), «Еще больше о треугольнике Паскаля и степенях числа 11», Учитель математики , 59 (5): 461–463, doi :10.5951/MT.59.5.0461, JSTOR  27957385.
36. Фьелстад, П. (1991), «Расширение треугольника Паскаля», Компьютеры и математика с приложениями , 21 (9): 3, doi : 10.1016/0898-1221(91)90119-O.

Внешние ссылки

• «Треугольник Паскаля», Энциклопедия математики , EMS Press , 2001 [1994]
• Вайсштейн, Эрик В. «Треугольник Паскаля». MathWorld .
• Старая схема метода семи умножающих квадратов (из «Су Юань Юй Цзянь» Чу Ши-Цзе, 1303 г., изображающая первые девять строк треугольника Паскаля)
• Трактат Паскаля об арифметическом треугольнике (изображения страниц трактата Паскаля, 1654; резюме)