|
| |
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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) = 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
|
|
|
|
STATUS
|
approved
|
| |
|
|
