A247300 Number of h- and H-steps at level 0 in all lattice paths in B(n).

0, 1, 3, 7, 17, 40, 94, 222, 526, 1252, 2994, 7191, 17343, 41989, 102023, 248712, 608168, 1491349, 3666685, 9037003, 22323243, 55259206, 137058248, 340567477, 847711177, 2113455657, 5277115687, 13195311961, 33038994039, 82829585094, 207905352180

Offset: 0

Author

Emeric Deutsch, Sep 17 2014

Keywords

• nonn

Comments

B(n) is the set of lattice paths of weight n that start in (0,0), end on the horizontal axis and never go below this axis, whose steps are of the following four kinds: h = (1,0) of weight 1, H = (1,0) of weight 2, u = (1,1) of weight 2, and d = (1,-1) of weight 1. The weight of a path is the sum of the weights of its steps.

a(n) = Sum(k*A247299(n,k), 0<=k<=n).

Examples

			a(3)=7 because in B(3) = {ud, hH, Hh, hhh} all h- and H-steps are at level 0.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• M. Bona and A. Knopfmacher, On the probability that certain compositions have the same number of parts, Ann. Comb., 14 (2010), 291-306.

Crossrefs

Cf. A247299.

Programs

Maple

G := 4*z*(1+z)/(1-z-z^2+sqrt((1+z+z^2)*(1-3*z+z^2)))^2: Gser := series(G, z = 0, 33): seq(coeff(Gser, z, n), n = 0 .. 30);
# second Maple program:
b:= proc(n, y) option remember; `if`(y<0 or y>n or n<0, 0,
      `if`(n=0, [1, 0], (p-> p+`if`(y=0, [0, p[1]], 0))
      (b(n-1, y) +b(n-2, y)) +b(n-2, y+1) +b(n-1, y-1)))
    end:
a:= n-> b(n, 0)[2]:
seq(a(n), n=0..50);  # Alois P. Heinz, Sep 17 2014

Mathematica

b[n_, y_] := b[n, y] = If[y<0 || y>n || n<0, 0, If[n == 0, {1, 0}, Function[{p}, p + If[y == 0, {0, p[[1]]}, 0]][b[n-1, y] + b[n-2, y]] + b[n-2, y+1] + b[n-1, y-1]]] ; a[n_] := b[n, 0][[2]]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, May 27 2015, after Alois P. Heinz *)

Formula

G.f.: 4*z*(1 + z)/(1 - z - z^2 +sqrt((1 + z + z^2)*(1 - 3*z + z^2)))^2.

a(n) ~ sqrt(525 + 235*sqrt(5)) * ((3 + sqrt(5))/2)^n / (sqrt(2*Pi)*n^(3/2)). - Vaclav Kotesovec, Mar 06 2016

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

D-finite with recurrence -(n+5)*(74*n-105)*a(n) +(90*n^2+287*n+109)*a(n-1) +(190*n^2-89*n+43)*a(n-2) +(206*n^2-289*n+23)*a(n-3) +(42*n^2-301*n+337)*a(n-4) -(58*n-37)*(n-5)*a(n-5)=0. - R. J. Mathar, Jul 24 2022