Трехчленный треугольник

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

${\begin{matrix}&&&&1\\&&&1&1&1\\&&1&2&3&2&1\\&1&3&6&7&6&3&1\\1&4&10&16&19&16&10&4&1\end{matrix}}$

The $k$-я запись $n$-я строка обозначается

${n \choose k}_{2}$.

Строки отсчитываются, начиная с 0. Записи $n$-я строка индексируется, начиная с $-n$ слева, а средняя запись имеет индекс 0. Симметрия записей строки относительно средней записи выражается соотношением

${n \choose k}_{2}={n \choose -k}_{2}$

Характеристики

The $n$ соответствует коэффициентам в полиномиальном разложении трехчлена -я строка $(1+x+x^{2})$ поднят до $n$-я мощность:

$\left(1+x+x^{2}\right)^{n}=\sum _{j=0}^{2n}{n \choose j-n}_{2}x^{j}=\sum _{k=-n}^{n}{n \choose k}_{2}x^{n+k}$

или, симметрично,

$\left(1+x+1/x\right)^{n}=\sum _{k=-n}^{n}{n \choose k}_{2}x^{k}$,

следовательно, альтернативные названия триномиальные коэффициенты из-за их связи с полиномиальными коэффициентами :

${n \choose k}_{2}=\sum _{\textstyle {0\leq \mu ,\nu \leq n \atop \mu +2\nu =n+k}}{\frac {n!}{\mu !\,\nu !\,(n-\mu -\nu )!}}$

Кроме того, диагонали обладают интересными свойствами, например, их отношением к треугольным числам .

Сумма элементов $n$-я строка $3^{n}$.

Формула повторения

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

${0 \choose 0}_{2}=1$,

${n+1 \choose k}_{2}={n \choose k-1}_{2}+{n \choose k}_{2}+{n \choose k+1}_{2}$ для $n\geq 0$,

где ${n \choose k}_{2}=0$ для $\ k<-n$ и $\ k>n$.

Центральные трехчленные коэффициенты

Средние элементы трехчленного треугольника

1, 1, 3, 7, 19, 51, 141, 393, 1107, 3139, … (последовательность A002426 в OEIS )

были изучены Эйлером и известны как центральные трёхчленные коэффициенты .

The $n$-й центральный трехчленный коэффициент определяется выражением

${n \choose 0}_{2}=\sum _{k=0}^{n}{\frac {n(n-1)\cdots (n-2k+1)}{(k!)^{2}}}=\sum _{k=0}^{n}{n \choose 2k}{2k \choose k}.$

Их производящая функция

$1+x+3x^{2}+7x^{3}+19x^{4}+\ldots ={\frac {1}{\sqrt {(1+x)(1-3x)}}}.$

Эйлер отметил следующий примечательный пример ошибочной индукции:

$3{n+1 \choose 0}_{2}-{n+2 \choose 0}_{2}=F_{n}(F_{n}+1)$ для $0\leq n\leq 7$,

где $F_{n}$ — n- е число Фибоначчи . Для большего $n$, однако это соотношение неверно. Джордж Эндрюс объяснил это заблуждение, используя общее тождество

$2\sum _{k\in \mathbb {Z} }\left[{n+1 \choose 10k}_{2}-{n+1 \choose 10k+1}_{2}\right]=F_{n}(F_{n}+1).$

Приложения

В шахматах

Количество способов добраться до клетки за минимальное количество ходов

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

В комбинаторике

Коэффициент $x^{k}$ в расширении $\left(1+x+x^{2}\right)^{n}$ дает количество различных способов рисования $k$ карточки из двух одинаковых наборов $n$ игральные карты каждый. Например, из двух наборов по три карты A, B, C разные рисунки:

Количество выбранных карт	Количество опций	Параметры
0	1
1	3	А, Б, С
2	6	АА, АВ, АС, ВВ, ВС, СС
3	7	ААБ, ААС, АББ, АБВ, АСС, BBC, BCC
4	6	ААВВ, ААВС, ААКК, ABBC, ABCC, BBCC
5	3	ААБВС, ААБСС, АВВCC
6	1	ААВВСС

Например,

$6={3 \choose 2-3}_{2}={3 \choose 0}{3 \choose 2}+{3 \choose 1}{2 \choose 0}=1\cdot 3+3\cdot 1$.

В частности, это дает формулу ${24 \choose 12-24}_{2}={24 \choose -12}_{2}={24 \choose 12}_{2}$ за количество разных комбинаций в карточной игре Доппелькопф .

Альтернативно, к этому выражению также можно прийти, рассмотрев количество способов выбора. $p$ пары одинаковых карточек из двух наборов, что является биномиальным коэффициентом ${n \choose p}$. Остальные $k-2p$ карты затем можно выбрать в ${n-p \choose k-2p}$ пути, которое можно записать через биномиальные коэффициенты как

${n \choose k-n}_{2}=\sum _{p=\max(0,k-n)}^{\min(n,[k/2])}{n \choose p}{n-p \choose k-2p}$.

Приведенный выше пример соответствует трем способам выбора двух карт без пар одинаковых карт (AB, AC, BC) и трем способам выбора пары одинаковых карт (AA, BB, CC).

Дальнейшее чтение

• Леонард Эйлер (1767). «Аналитические наблюдения » Новые комментарии Петрополитической академии наук . 11 : 124–143.