A182905 Number of weighted lattice paths in F[n]. The members of F[n] are paths of weight n that start at (0,0), do not go below the horizontal axis, and whose steps are of the following four kinds: an (1,0)-step with weight 1, an (1,0)-step with weight 2, a (1,1)-step with weight 2, and a (1,-1)-step with weight 1. The weight of a path is the sum of the weights of its steps.

1, 1, 3, 6, 14, 32, 75, 177, 422, 1013, 2447, 5942, 14495, 35501, 87257, 215144, 531970, 1318726, 3276644, 8158736, 20354413, 50870857, 127348839, 319288920, 801657469, 2015431885, 5073224661, 12785062080, 32254748838, 81457050078

Offset

0,3

Comments

The paths in F[n] need not end on the horizontal axis.

If f(z) is the generating function of the paths in F[n] (according to weight), and g(z) is the generating function of the those paths in F[n] that end on the horizontal axis, then f = g +z^2*gf. Also, g = (1 + zg)(1+z^2*g). Eliminating g from the above two equations, one obtains f(z).

Links

Table of n, a(n) for n=0..29.

M. Bona and A. Knopfmacher, On the probability that certain compositions have the same number of parts, Ann. Comb., 14 (2010), 291-306.

Formula

G.f.: f(z)=2/[1-z-3z^2+sqrt((1+z+z^2)(1-3z+z^2))].

a(n) ~ sqrt(4935 + 2207*sqrt(5))* ((3 + sqrt(5))/2)^n / (sqrt(8*Pi)*n^(3/2)). - Vaclav Kotesovec, Mar 06 2016. Equivalently, a(n) ~ 5^(1/4) * phi^(2*n + 8) / (2*sqrt(Pi)*n^(3/2)), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, Dec 06 2021

a(n) = Sum_{k=0..n} (k+1)*Sum_{i=0..n-k+1} C(i+1,n+1-i)*C(i+1,-i+n-k))/(i+1). - Vladimir Kruchinin, Jan 25 2019

D-finite with recurrence (n+2)*a(n) +(-4*n-5)*a(n-1) +(n-1)*a(n-2) +(4*n+5)*a(n-3) +(7*n-16)*a(n-4) +2*(n-1)*a(n-5) +2*(-n+4)*a(n-6)=0. - R. J. Mathar, Jul 24 2022

Example

a(3)=6. Indeed, denoting by h (H) the (1,0)-step of weight 1 (2), and U=(1,1), D=(1,-1), we have hhh, hH, Hh, UD, hU, and Uh.

Maple

f := 2/(1-z-3*z^2+sqrt((1+z+z^2)*(1-3*z+z^2))): fser := series(f, z = 0, 32): seq(coeff(fser, z, n), n = 0 .. 29);

Mathematica

CoefficientList[Series[2/(1-x-3*x^2+Sqrt[(1+x+x^2)*(1-3*x+x^2)]), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 06 2016 *)

Prog

(Maxima)
a(n):=sum((k+1)*sum((binomial(i+1, n+1-i)*binomial(i+1, -i+n-k))/(i+1), i, 0, n-k+1), k, 0, n); /* Vladimir Kruchinin, Jan 25 2019 */

Crossrefs

Sequence in context: A129954 A238768 A272362 * A330053 A192678 A114945

Adjacent sequences: A182902 A182903 A182904 * A182906 A182907 A182908

Keyword

nonn

Author

Emeric Deutsch, Dec 16 2010

Status

approved