Треугольник Фибоначчи

[Andrey A]

$$\[ \setcounter{MaxMatrixCols}{25} \begin{matrix} & & & & & & & & & & 1 & & & & & & & & & & \\ & & & & & & & & & & & & & & & & & & & & \\ & & & & & & & & & 1 & & 1 & & & & & & & & & \\ & & & & & & & & & & & & & & & & & & & & \\ & & & & & & & & 1 & & 1 & & 1 & & & & & & & & \\ & & & & & & & & & & & & & & & & & & & & \\ & & & & & & & 1 & & 2 & & 2 & & 1 & & & & & & & \\ & & & & & & & & & & & & & & & & & & & & \\ & & & & & & 1 & & 3 & & 6 & & 3 & & 1 & & & & & & \\ & & & & & & & & & & & & & & & & & & & & \\ & & & & & 1 & & 5 & & 15 & & 15 & & 5 & & 1 & & & & & \\ & & & & & & & & & & & & & & & & & & & & \\ & & & & 1 & & 8 & & 40 & & 60 & & 40 & & 8 & & 1 & & & & \\ & & & & & & & & & & & & & & & & & & & & \\ & & & 1 & & 13 & & 104 & & 260 & & 260 & & 104 & & 13 & & 1 & & & \\ & & & & & & & & & & & & & & & & & & & & \\ & & 1 & & 21 & & 273 & & 1092 & & 1820 & & 1092 & & 273 & & 21 & & 1 & & \\ & & & & & & & & & & & & & & & & & & & & \\ & 1 & & 34 & & 714 & & 4641 & & 12376 & & 12376 & & 4641 & & 714 & & 34 & & 1 \end{matrix} \]$$

Элементы треугольника вычисляются по формуле $C^k_n=\frac{n!}{k!(n-k)!}$, в которой факториалы заменены на произведения соответствующего количества начальных членов ряда Фибоначчи (нулевое произведение считаем $=1$). Элементы $(n+2)$-ой строки $(\pm )$ задают рекуррентное правило последовательности $n$-ых степеней Фибоначчи:
$F^2_{n+1}=2F^2_n+2F^2_{n-1}-F^2_{n-2}$ (4-я строка)
$F^3_{n+1}=3F^3_n+6F^3_{n-1}-3F^3_{n-2}-F^3_{n-3}$ (5-я строка)
$F^4_{n+1}=5F^4_n+15F^4_{n-1}-15F^4_{n-2}-5F^4_{n-3}+F^4_{n-4}$ (6-я строка) и т.д.
Это связано с темой http://dxdy.ru/topic103297.html (в конце), но вроде бы подобный целочисленный треугольник можно смастерить из любой функции, в которой из $a\mid b$ следует $f_a\mid f_b$. Например, из последовательности сумм степенного ряда. Интересно, какие тут возможны интерпретации, и нет ли иных способов построения (как в Паскале)? Последовательности, образованные диагоналями имеются в OEIS. Может это где-то описано?

[Andrey A]

Upd
$n$ в примерах со степенями Фибоначчи не связано, конечно, с номером строки. Надо бы так:
$F^4_{i+1}=5F^4_i+15F^4_{i-1}-15F^4_{i-2}-5F^4_{i-3}+F^4_{i-4}$ (6-я строка) и т.д.

[Andrey A]

Upd 25.11
Можно доказать целочисленность подобного треугольника для последовательности сумм натурального ряда $t_i$. Обозначим $C^k_n\left( t_i\right)$ элемент на пересечении $n$-ой строки и $k$-го столбца.

$$\prod_{i=1}^{n}t_i=\frac{1\cdot 2}{2}\cdot \frac{2\cdot 3}{2}\cdot \frac{3\cdot 4}{2}\cdot ...\cdot \frac{n(n+1)}{2}=\frac{n!(n+1)!}{2^n}$$

$$C^k_n\left( t_i\right)=\frac{\prod_{i=1}^{n}t_i}{\prod_{i=1}^{k}t_i\prod_{i=1}^{n-k}t_i}=\frac{n!(n+1)!/2^n}{k!(k+1)!/2^k(n-k)!(n-k+1)!/2^{n-k}}=\frac{n!(n+1)!}{k!(k+1)!(n-k)!(n-k+1)!}$$

Группируя множители различными способами, получаем

$$C^k_n\left( t_i\right)=\frac{C^k_nC^{k+1}_{n+1}}{n-k+1}=\frac{C^k_{n+1}C^{k+1}_n}{n-k}$$

Дробь в левой части выражения $\dfrac{n-k+1}{n-k}=\dfrac{C^k_nC^{k+1}_{n+1}}{C^k_{n+1}C^{k+1}_n}$ несократима, следовательно $n-k+1\mid C^k_nC^{k+1}_{n+1};\ n-k\mid C^k_{n+1}C^{k+1}_n$, и $C^k_n\left( t_i\right)$ - всегда целое число. Для многоугольных чисел в общем случае это не верно. Последовательности диагоналей также имеются в OEIS, но "физический" смысл строк для меня загадка. Такой "треугольный треугольник".

[Andrey A]

Upd 25.11
Это, оказывается, разновидность "каталонского треугольника" A001263. Первый тоже есть в OEIS: A010048 Triangle of Fibonomial coefficients.
Буду признателен за русские ссылки по теме.

[grizzly]

Andrey A в сообщении #1171692 писал(а):

Буду признателен за русские ссылки по теме.

По Вашей ссылке на первый треугольник в литературе указан Кнут:

Цитата:

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 1, p. 84 and 492.

Логично предположить, что что-то полезное можно найти в переводе этого тома на русский.

-- 25.11.2016, 20:41 --

В литературе по другой последовательности есть Риордан. Он легко гуглится на русском.

[Andrey A]

Ага. Спасибо, поищу.

[dimkadimon]

Вот может поможет:

https://en.wikipedia.org/wiki/Fibonomial_coefficient
http://mathworld.wolfram.com/FibonomialCoefficient.html

[Andrey A]

В английской вики есть-таки построение "фибонома" без факториалов, а я туда не заглядывал. Спасибо.
Еще кое-что по горячим следам нашлось: http://www.mccme.ru/~smirnoff/papers/qbinom3.pdf