login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A247293
Number of weighted lattice paths B(n) having no uHd strings.
4
1, 1, 2, 4, 8, 16, 35, 77, 172, 391, 899, 2085, 4877, 11490, 27236, 64916, 155483, 374027, 903286, 2189219, 5322965, 12980660, 31740404, 77804885, 191160040, 470662449, 1161123461, 2869754099, 7104856781, 17618234456, 43754467510, 108816781175
OFFSET
0,3
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) = A247292(n,0).
LINKS
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. G = G(z) satisfies G = 1 + z*G + z^2*G + z^3*G*(G - z^2).
D-finite with recurrence +(n+3)*a(n) +(-2*n-3)*a(n-1) -n*a(n-2) +(-2*n+3)*a(n-3) +(n-3)*a(n-4) +(2*n-9)*a(n-5) +2*(-n+6)*a(n-6) +(-2*n+15)*a(n-7) +(n-12)*a(n-10)=0. - R. J. Mathar, Jul 26 2022
EXAMPLE
a(6)=35 because among the 37 (=A004148(7)) members of B(6) only huHd and uHdh contain uHd.
MAPLE
eq := G = 1+z*G+z^2*G+z^3*(G-z^2)*G: G := RootOf(eq, G): Gser := series(G, z = 0, 37): seq(coeff(Gser, z, n), n = 0 .. 35);
# second Maple program:
b:= proc(n, y, t) option remember; `if`(y<0 or y>n or t=3, 0,
`if`(n=0, 1, b(n-1, y, 0)+`if`(n>1, b(n-2, y, `if`(t=1,
2, 0))+b(n-2, y+1, 1), 0)+b(n-1, y-1, `if`(t=2, 3, 0))))
end:
a:= n-> b(n, 0$2):
seq(T(n), n=0..40); # Alois P. Heinz, Sep 16 2014
MATHEMATICA
b[n_, y_, t_] := b[n, y, t] = If[y<0 || y>n || t == 3, 0, If[n == 0, 1, b[n-1, y, 0] + If[n>1, b[n-2, y, If[t == 1, 2, 0]] + b[n-2, y+1, 1], 0] + b[n-1, y-1, If[t == 2, 3, 0]]]]; a[n_] := b[n, 0, 0]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, May 27 2015, after Alois P. Heinz *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Sep 16 2014
STATUS
approved