cp's OEIS Frontend

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).

%I A108425 #19 Feb 24 2020 04:28:23
%S A108425 2,4,6,8,36,22,16,144,248,90,32,480,1600,1560,394,64,1440,7840,14400,
%T A108425 9420,1806,128,4032,32480,95760,115416,55692,8558,256,10752,120064,
%U A108425 517440,986272,860832,325360,41586,512,27648,408576,2419200,6668928
%N 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).
%C A108425 Row sums yield A027307. T(n,n) = A006318(n) (the large Schroeder numbers; asks for a bijective proof). T(n,1) = 2^n.
%H A108425 Michael De Vlieger, <a href="/A108425/b108425.txt">Table of n, a(n) for n = 1..11325</a> (rows 1 <= n <= 150).
%H A108425 Andrei Asinowski, Axel Bacher, Cyril Banderier, Bernhard Gittenberger, <a href="https://lipn.univ-paris13.fr/~banderier/Papers/patterns2019.pdf">Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata</a>, Laboratoire d'Informatique de Paris Nord (LIPN 2019).
%H A108425 Emeric Deutsch, <a href="http://www.jstor.org/stable/2589192">Problem 10658</a>, American Math. Monthly, 107, 2000, 368-370.
%F A108425 T(n, k) = (1/n)binomial(n, k)*Sum_{j=0..k-1} 2^(n-j)*binomial(n, j)*binomial(n, k-1-j).
%F A108425 G.f.: G = G(t, z) satisfies zG^3 + tzG^2 - (1 + z - tz)G + 1 = 0.
%e A108425 Example T(2,1)=4 because we have uudd, uUddd, Uuddd and UUdddd.
%e A108425 Triangle begins:
%e A108425    2;
%e A108425    4,   6;
%e A108425    8,  36,  22;
%e A108425   16, 144, 248,  90;
%p A108425 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
%t A108425 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 *)
%Y A108425 Cf. A006318, A027307, A108426.
%K A108425 nonn,tabl
%O A108425 1,1
%A A108425 _Emeric Deutsch_, Jun 03 2005