OFFSET
0,2
COMMENTS
See A134426 for the enumeration of these paths according to the ordinates of their endpoints.
a(n) is the number of Schroder paths of semilength n in which the (2,0)-steps that are on the horizontal axis come in 4 colors. Example: a(2)=27 because we have 4^2=16 paths of shape HHHH, 4 paths of shape HUD, 4 paths of shape UDH, 1 paths of each of the shapes UDUD, UUDD, and UHD. - Emeric Deutsch, May 02 2011
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..200
Taras Goy and Mark Shattuck, Hessenberg-Toeplitz Matrix Determinants with Schröder and Fine Number Entries, arXiv:2303.10223 [math.CO], 2023.
FORMULA
G.f.: 2/(1-7z+sqrt(1-6z+z^2)). G.f.: g/(1-2zg), where g is the g.f. of the little Schroeder numbers 1,3,11,45,197,... (A001003).
Recurrence: (n+1)*a(n) = 3*(4*n+1)*a(n-1) - (37*n-20)*a(n-2) + 6*(n-2)*a(n-3). - Vaclav Kotesovec, Oct 20 2012
a(n) ~ 6^n/2. - Vaclav Kotesovec, Oct 20 2012
a(n) = Sum_{k=0..n}((k+1)*Sum_{j=0..n+1}(binomial(j,n-k-j)*3^(-n+k+2*j)*2^(n-j)*binomial(n+1,j)))/(n+1). - Vladimir Kruchinin, Mar 13 2016
EXAMPLE
a(2)=5 because we have F1, F2, F3, U1 and U2. a(3)=27 because we have 9 paths of shape FF, 2 paths of shape UD, 6 paths of shape FU, 6 paths of shape UF and 4 paths of shape UU.
MAPLE
G:=2/(1-7*z+sqrt(1-6*z+z^2)): Gser:=series(G, z=0, 30): seq(coeff(Gser, z, n), n= 0..20);
MATHEMATICA
CoefficientList[Series[2/(1-7*x+Sqrt[1-6*x+x^2]), {x, 0, 20}], x] (* Vaclav Kotesovec, Oct 20 2012 *)
PROG
(Maxima)
a(n):=sum((k+1)*sum(binomial(j, n-k-j)*3^(-n+k+2*j)*2^(n-j)*binomial(n+1, j), j, 0, n+1), k, 0, n)/(n+1); /* Vladimir Kruchinin, Mar 13 2016 */
CROSSREFS
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Nov 05 2007
STATUS
approved