login
A134425
Number of paths of length n in the first quadrant, starting at the origin and consisting of 2 kinds of upsteps U=(1,1) (U1 and U2), 3 kinds of flatsteps F=(1,0) (F1, F2 and F3) and 1 kind of downsteps D=(1,-1).
3
1, 5, 27, 151, 861, 4969, 28911, 169187, 994329, 5862925, 34658691, 205305423, 1218183669, 7238062641, 43055682327, 256365292443, 1527728176305, 9110460044821, 54362600841963, 324557242893191, 1938584147698701
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
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
Sequence in context: A100193 A158869 A162557 * A332598 A305573 A184702
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Nov 05 2007
STATUS
approved