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

1, 5, 27, 151, 861, 4969, 28911, 169187, 994329, 5862925, 34658691, 205305423, 1218183669, 7238062641, 43055682327, 256365292443, 1527728176305, 9110460044821, 54362600841963, 324557242893191, 1938584147698701

Offset: 0

Author

Emeric Deutsch, Nov 05 2007

Keywords

• nonn

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

Examples

			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.
		

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, Carpathian Math. Publ., Vol. 15 (2023), No. 2, 420-436. See Theorems 1 and 2; Preprint, arXiv:2303.10223 [math.CO], 2023.

Crossrefs

Cf. A001003, A134426.

Programs

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

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 */

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