|
|
A026300
|
|
Motzkin triangle, T, read by rows; T(0,0) = T(1,0) = T(1,1) = 1; for n >= 2, T(n,0) = 1, T(n,k) = T(n-1,k-2) + T(n-1,k-1) + T(n-1,k) for k = 1,2,...,n-1 and T(n,n) = T(n-1,n-2) + T(n-1,n-1).
|
|
47
|
|
|
1, 1, 1, 1, 2, 2, 1, 3, 5, 4, 1, 4, 9, 12, 9, 1, 5, 14, 25, 30, 21, 1, 6, 20, 44, 69, 76, 51, 1, 7, 27, 70, 133, 189, 196, 127, 1, 8, 35, 104, 230, 392, 518, 512, 323, 1, 9, 44, 147, 369, 726, 1140, 1422, 1353, 835, 1, 10, 54, 200, 560, 1242, 2235, 3288, 3915, 3610, 2188
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
Right-hand columns have g.f. M^k, where M is g.f. of Motzkin numbers.
Consider a semi-infinite chessboard with squares labeled (n,k), ranks or rows n >= 0, files or columns k >= 0; number of king-paths of length n from (0,0) to (n,k), 0 <= k <= n, is T(n,n-k). - Harrie Grondijs, May 27 2005. Cf. A114929, A111808, A114972.
|
|
REFERENCES
|
Harrie Grondijs, Neverending Quest of Type C, Volume B - the endgame study-as-struggle.
A. Nkwanta, Lattice paths and RNA secondary structures, in African Americans in Mathematics, ed. N. Dean, Amer. Math. Soc., 1997, pp. 137-147.
|
|
LINKS
|
Mark C. Wilson, Diagonal asymptotics for products of combinatorial classes, PDF.
|
|
FORMULA
|
T(n,k) = Sum_{i=0..floor(k/2)} binomial(n, 2i+n-k)*(binomial(2i+n-k, i) - binomial(2i+n-k, i-1)). - Herbert Kociemba, May 27 2004
T(n,k) = binomial(n, k)*hypergeom([1/2 - k/2, -k/2], [n - k + 2], 4). - Peter Luschny, Mar 21 2018
T(n,k) = [t^(n-k)] [x^n] 2/(1 - (2*t + 1)*x + sqrt((1 + x)*(1 - 3*x))). - Peter Luschny, Oct 24 2018
The n-th row polynomial R(n,x) equals the n-th degree Taylor polynomial of the function (1 - x^2)*(1 + x + x^2)^n expanded about the point x = 0. - Peter Bala, Feb 26 2023
|
|
EXAMPLE
|
Triangle starts:
[0] 1;
[1] 1, 1;
[2] 1, 2, 2;
[3] 1, 3, 5, 4;
[4] 1, 4, 9, 12, 9;
[5] 1, 5, 14, 25, 30, 21;
[6] 1, 6, 20, 44, 69, 76, 51;
[7] 1, 7, 27, 70, 133, 189, 196, 127;
[8] 1, 8, 35, 104, 230, 392, 518, 512, 323;
[9] 1, 9, 44, 147, 369, 726, 1140, 1422, 1353, 835.
|
|
MAPLE
|
add(binomial(n, 2*i+n-k)*(binomial(2*i+n-k, i) -binomial(2*i+n-k, i-1)), i=0..floor(k/2));
|
|
MATHEMATICA
|
t[n_, k_] := Sum[ Binomial[n, 2i + n - k] (Binomial[2i + n - k, i] - Binomial[2i + n - k, i - 1]), {i, 0, Floor[k/2]}]; Table[ t[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Robert G. Wilson v, Jan 03 2011 *)
t[_, 0] = 1; t[n_, 1] := n; t[n_, k_] /; k>n || k<0 = 0; t[n_, n_] := t[n, n] = t[n-1, n-2]+t[n-1, n-1]; t[n_, k_] := t[n, k] = t[n-1, k-2]+t[n-1, k-1]+t[n-1, k]; Table[t[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Apr 18 2014 *)
T[n_, k_] := Binomial[n, k] Hypergeometric2F1[1/2 - k/2, -k/2, n - k + 2, 4];
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Peter Luschny, Mar 21 2018 *)
|
|
PROG
|
(Haskell)
a026300 n k = a026300_tabl !! n !! k
a026300_row n = a026300_tabl !! n
a026300_tabl = iterate (\row -> zipWith (+) ([0, 0] ++ row) $
zipWith (+) ([0] ++ row) (row ++ [0])) [1]
(PARI) tabl(nn) = {for (n=0, nn, for (k=0, n, print1(sum(i=0, k\2, binomial(n, 2*i+n-k)*(binomial(2*i+n-k, i)-binomial(2*i+n-k, i-1))), ", "); ); print(); ); } \\ Michel Marcus, Jul 25 2015
|
|
CROSSREFS
|
T(n,n) are Motzkin numbers A001006.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|