A247298 Number of weighted lattice paths B(n) having no uudd strings.

1, 1, 2, 4, 8, 17, 36, 80, 180, 410, 946, 2203, 5173, 12233, 29108, 69643, 167437, 404311, 980125, 2384441, 5819576, 14245384, 34964611, 86032272, 212172668, 524371704, 1298509438, 3221425567, 8005623916, 19926840746, 49674610998, 124006308008

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) = A247297(n,0).

Links

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

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

Example

a(6)=36 because among the 37 (=A004148(7)) paths in B(6) only uudd contains uudd.

Maple

eq := G = 1+z*G+z^2*G+z^3*G*(G-z^3): G := RootOf(eq, G): Gser := series(G, z = 0, 37): seq(coeff(Gser, z, n), n = 0 .. 35);

Crossrefs

Cf. A004148, A247297.

Sequence in context: A202844 A093951 A137255 * A325928 A076892 A106462

Adjacent sequences: A247295 A247296 A247297 * A247299 A247300 A247301

Keyword

nonn

Author

Emeric Deutsch, Sep 17 2014

Status

approved