login
A108425
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 peaks (i.e., ud and Ud's).
4
2, 4, 6, 8, 36, 22, 16, 144, 248, 90, 32, 480, 1600, 1560, 394, 64, 1440, 7840, 14400, 9420, 1806, 128, 4032, 32480, 95760, 115416, 55692, 8558, 256, 10752, 120064, 517440, 986272, 860832, 325360, 41586, 512, 27648, 408576, 2419200, 6668928
OFFSET
1,1
COMMENTS
Row sums yield A027307. T(n,n) = A006318(n) (the large Schroeder numbers; asks for a bijective proof). T(n,1) = 2^n.
LINKS
Michael De Vlieger, Table of n, a(n) for n = 1..11325 (rows 1 <= n <= 150).
Andrei Asinowski, Axel Bacher, Cyril Banderier, Bernhard Gittenberger, Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata, Laboratoire d'Informatique de Paris Nord (LIPN 2019).
Emeric Deutsch, Problem 10658, American Math. Monthly, 107, 2000, 368-370.
FORMULA
T(n, k) = (1/n)binomial(n, k)*Sum_{j=0..k-1} 2^(n-j)*binomial(n, j)*binomial(n, k-1-j).
G.f.: G = G(t, z) satisfies zG^3 + tzG^2 - (1 + z - tz)G + 1 = 0.
EXAMPLE
Example T(2,1)=4 because we have uudd, uUddd, Uuddd and UUdddd.
Triangle begins:
2;
4, 6;
8, 36, 22;
16, 144, 248, 90;
MAPLE
T:=(n, k)->(1/n)*binomial(n, k)*sum(2^(n-j)*binomial(n, j)*binomial(n, k-1-j), j=0..k-1): for n from 1 to 10 do seq(T(n, k), k=1..n) od; # yields sequence in triangular form
MATHEMATICA
Table[(1/n) Binomial[n, k] Sum[2^(n - j) Binomial[n, j] Binomial[n, k - 1 - j], {j, 0, k - 1}], {n, 9}, {k, n}] // Flatten (* Michael De Vlieger, Oct 06 2015 *)
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Jun 03 2005
STATUS
approved