login
Triangle read by rows: T(n,k) is the number of Motzkin paths of length n with k peaks (n>=0, 0<=k<=floor(n/2)).
2

%I #33 Oct 23 2019 09:28:06

%S 1,1,1,1,2,2,4,4,1,8,10,3,17,24,9,1,37,58,28,4,82,143,81,16,1,185,354,

%T 231,60,5,423,881,653,205,25,1,978,2204,1824,676,110,6,2283,5534,5058,

%U 2164,435,36,1,5373,13940,13946,6756,1631,182,7,12735,35213,38262,20710

%N Triangle read by rows: T(n,k) is the number of Motzkin paths of length n with k peaks (n>=0, 0<=k<=floor(n/2)).

%C Row sums are the Motzkin numbers (A001006). Column 0 gives A004148.

%C This triangle is the Motzkin path equivalent to the Narayana numbers (A001263). - _Dan Drake_, Feb 17 2011

%H Alois P. Heinz, <a href="/A097860/b097860.txt">Rows n = 0..200, flattened</a>

%H Marilena Barnabei, Flavio Bonetti, and Niccolò Castronuovo, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Barnabei/barnabei5.html">Motzkin and Catalan Tunnel Polynomials</a>, J. Int. Seq., Vol. 21 (2018), Article 18.8.8.

%H Dan Drake and Ryan Gantner, <a href="http://arxiv.org/abs/1109.3273">Generating functions for plateaus in Motzkin paths</a>, J. of the Chungcheong Math. Soc., Vol 25, No. 3, p. 475, August 2012.

%H Zhuang, Yan. <a href="https://arxiv.org/abs/1508.02793">A generalized Goulden-Jackson cluster method and lattice path enumeration</a>, Discrete Mathematics 341.2 (2018): 358-379. Also arXiv: 1508.02793v2.

%F G.f. G = G(t, z) satisfies G = 1+z*G+z^2*G*(G-1+t).

%F G.f. has explicit form G(x,t) = (w-sqrt(w^2-4*x^2))/(2*x^2) with w = 1-x+x^2-x^2*t. (Drake and Ganter, Th. 6) - _Peter Luschny_, Nov 14 2014

%e Triangle starts:

%e 1;

%e 1;

%e 1, 1;

%e 2, 2;

%e 4, 4, 1;

%e 8, 10, 3;

%e 17, 24, 9, 1;

%e ...

%e Row n has 1+floor(n/2) terms.

%e T(4,1)=4 because (UD)HH, H(UD)H, HH(UD) and U(UD)D are the only Motzkin paths of length 4 with 1 peak (here U=(1,1), H=(1,0) and D=(1,-1)); peaks are shown between parentheses.

%p eq:=G=1+z*G+z^2*G*(G-1+t):sol:=solve(eq,G): G:=sol[2]: Gser:=simplify(series(G,z=0,16)): P[0]:=1: for n from 1 to 13 do P[n]:=sort(coeff(Gser,z^n)) od: seq(seq(coeff(t*P[n],t^k),k=1..1+floor(n/2)),n=0..13);

%p # Alternatively

%p A097860_row := proc(n) local w,f,p,i;

%p w := 1-x+x^2-x^2*t; f := (w-sqrt(w^2-4*x^2))/(2*x^2);

%p p := simplify(coeff(series(f,x,3+2*n),x,n));

%p seq(coeff(p,t,i), i=0..iquo(n,2)) end:

%p seq(print(A097860_row(n)), n=0..7); # _Peter Luschny_, Nov 14 2014

%p # third Maple program:

%p b:= proc(x, y, t) option remember; expand(`if`(y<0 or y>x, 0,

%p `if`(x=0, 1, b(x-1, y, 1)+b(x-1, y-1, 1)*t+b(x-1, y+1, z))))

%p end:

%p T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(n, 0, 1)):

%p seq(T(n), n=0..15); # _Alois P. Heinz_, Feb 01 2019

%t gf = With[{w = 1 - x + x^2 - x^2*t}, (w - Sqrt[w^2 - 4*x^2])/(2*x^2)];

%t cx[n_] := cx[n] = SeriesCoefficient[gf, {x, 0, n}];

%t T[n_, k_] := SeriesCoefficient[cx[n], {t, 0, k}];

%t Table[T[n, k], {n, 0, 14}, {k, 0, n/2}] // Flatten (* _Jean-François Alcover_, Dec 04 2017, after _Peter Luschny_ *)

%Y Cf. A001006, A004148, A001263, A097885.

%K nonn,tabf

%O 0,5

%A _Emeric Deutsch_, Sep 01 2004