OFFSET
1,1
COMMENTS
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