A108443 Triangle read by rows: T(n,k) is number of paths from (0,0) to (3n,0) that stay in the first quadrant (but may touch the horizontal axis), consisting of steps u=(2,1), U=(1,2), or d=(1,-1) and have k triple descents (i.e., ddd's).
1, 2, 6, 3, 1, 21, 24, 15, 5, 1, 80, 150, 145, 84, 31, 7, 1, 322, 857, 1145, 949, 528, 202, 53, 9, 1, 1347, 4692, 8096, 8801, 6598, 3551, 1394, 398, 81, 11, 1, 5798, 25102, 53457, 72338, 68594, 47805, 25092, 10019, 3040, 692, 115, 13, 1, 25512, 132484, 337132
Offset: 0
Examples
T(2,1) = 3 because we have uUddd, Uuddd and UdUddd.
Triangle begins:
1;
2;
6, 3, 1;
21, 24, 15, 5, 1;
80, 150, 145, 84, 31, 7, 1;
322, 857, 1145, 949, 528, 202, 53, 9, 1;
Links
- Alois P. Heinz, Rows n = 0..100, flattened
- Emeric Deutsch, Problem 10658: Another Type of Lattice Path, American Math. Monthly, 107, 2000, 368-370.
Programs
-
Maple
b:= proc(x, y, t) option remember; expand(`if`(y<0 or y>x, 0, `if`(x=0, 1, b(x-1, y-1, min(2, t+1))*`if`(t=2, z, 1)+ b(x-1, y+2, 0)+b(x-2, y+1, 0)))) end: T:= n->(p->seq(coeff(p, z, i), i=0..degree(p)))(b(3*n, 0$2)): seq(T(n), n=0..8); # Alois P. Heinz, Oct 06 2015 -
Mathematica
b[x_, y_, t_] := b[x, y, t] = Expand[If[y < 0 || y > x, 0, If[x == 0, 1, b[x - 1, y - 1, Min[2, t + 1]]*If[t == 2, z, 1] + b[x - 1, y + 2, 0] + b[x - 2, y + 1, 0]]]]; T[n_] := Function[p, Table[Coefficient[p, z, i], {i, 0, Exponent[p, z]}]][b[3*n, 0, 0]]; Table[T[n], {n, 0, 8}] // Flatten (* Jean-François Alcover, Dec 21 2016, after Alois P. Heinz *) -
PARI
{T(n,k)=local(G=1+z*O(z^n)+t*O(t^k));for(k=1,n, G=1+z*(t+z-t*z)^2*G^3+z*(2-t)*(t+z-t*z)*G^2+2*z*(1-t)*G); polcoeff(polcoeff(G,n,z),k,t)}
Formula
G.f. G = G(t,z) satisfies G = 1 + z(t + z - tz)^2*G^3 + z(2-t)(t + z - tz)G^2 + 2z(1-t)G.
Comments