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
Keywords
Examples
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.
Links
- M. Bona and A. Knopfmacher, On the probability that certain compositions have the same number of parts, Ann. Comb., 14 (2010), 291-306.
Programs
-
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 *) -
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 */
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
Comments