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

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

${\displaystyle {\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}}}$

В ${\displaystyle k}$-я запись ${\displaystyle n}$-я строка обозначается

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

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

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

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

В ${\displaystyle n}$-я строка соответствует коэффициентам в полиномиальное разложение расширения трехчленный ${\displaystyle (1+x+x^{2})}$ поднял до ${\displaystyle n}$-я степень:^[1]

${\displaystyle \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}}$

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

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

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

${\displaystyle {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 )!}}}$

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

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

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

Коэффициенты трехчлена могут быть сгенерированы с использованием следующих формула повторения:^[1]

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

${\displaystyle {n+1 \choose k}_{2}={n \choose k-1}_{2}+{n \choose k}_{2}+{n \choose k+1}_{2}}$ за ${\displaystyle n\geq 0}$,

куда ${\displaystyle {n \choose k}_{2}=0}$ за ${\displaystyle \ k<-n}$ и ${\displaystyle \ k>n}$.

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

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

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

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

В ${\displaystyle n}$-й центральный коэффициент трехчлена определяется как

${\displaystyle {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}.}$

Их производящая функция является^[2]

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

Эйлер отметил следующее Образец меморабельной индукцииis fallacis («яркий пример ложной индукции»):

${\displaystyle 3{n+1 \choose 0}_{2}-{n+2 \choose 0}_{2}=F_{n}(F_{n}+1)}$ за ${\displaystyle 0\leq n\leq 7}$,

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

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

Приложения

В шахматы

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

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

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

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

Количество выбранных карт	Кол-во вариантов	Опции
0	1
1	3	А, Б, В
2	6	AA, AB, AC, BB, BC, CC
3	7	AAB, AAC, ABB, ABC, ACC, BBC, BCC
4	6	AABB, AABC, AACC, ABBC, ABCC, BBCC
5	3	AABBC, AABCC, ABBCC
6	1	AABBCC

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

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

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

Например,

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

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

Рекомендации

1. Вайсштейн, Эрик В. «Трехоминальный коэффициент». MathWorld.
2. Вайсштейн, Эрик В. «Центральный трехчленовый коэффициент». MathWorld.
3. Джордж Эндрюс, Три аспекта разделов. Séminaire Lotharingien de Combinatoire, B25f (1990) Интернет-копия
4. Андреас Стиллер: Pärchenmathematik. Trinomiale und Doppelkopf. («Парная математика. Трехчлены и игра Доппелькопф"). c't Выпуск 10/2005, стр. 181ff

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

• Леонард Эйлер (1767). "Observationes analyticae (" Аналитические наблюдения ")". Новые комментарии academiae scientiarum Petropolitanae. 11: 124–143.