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).
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
Examples
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;
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.
Programs
-
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 *)
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.
Comments