A247296 Number of uhd and uHd in all weighted lattice paths B(n).

0, 0, 0, 0, 1, 3, 7, 18, 45, 112, 281, 706, 1778, 4490, 11363, 28814, 73199, 186257, 474635, 1211122, 3094171, 7913765, 20261142, 51921920, 133171656, 341836748, 878104607, 2257208148, 5805964495, 14942942127, 38480449261, 99145105834, 255573465001, 659114680270

Offset: 0

Author

Emeric Deutsch, Sep 16 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) = A110320(n-3) + A110320(n-4) (n>=5).

Examples

			a(6)=7 because among the 37 (=A004148(7)) members of B(6) only (uhd)hh, h(uhd)h, hh(uhd), H(uhd), (uhd)H, (uHd)h, and h(uHd) contain uhd or uHd (shown between parentheses).
G.f. = x^4 + 3*x^5 + 7*x^6 + 18*x^7 + 45*x^8 + 112*x^9 + 281*x^10 + ...
		

Links

• G. C. Greubel, 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. A004148, A110320, A247294.

Programs

Magma

m:=30; R:=PowerSeriesRing(Integers(), m); [0,0,0,0] cat Coefficients(R!(x*(x+1)*(-1 +(1-x-x^2 )/sqrt((1-3*x+x^2)*(1+x+x^2)) )/2)); // G. C. Greubel, Aug 05 2018

Maple

eqg := g = 1+z*g+z^2*g+z^3*g^2: g := RootOf(eqg, g): H := z^4*(1+z)*g/(1-z-z^2-2*z^3*g): Hser := series(H, z = 0, 40): seq(coeff(Hser, z, n), n = 0 .. 35);

Mathematica

a[ n_] := With[{t = (1 - 3 x + x^2) (1 + x + x^2)}, SeriesCoefficient[ x (x + 1) (-1 + (1 - x - x^2) / Sqrt[t]) / 2, {x, 0, n}]]; (* Michael Somos, Sep 16 2014 *)

PARI

x='x+O('x^30); concat(vector(4), Vec(x*(x+1)*(-1 +(1-x-x^2 )/sqrt((1-3*x+x^2)*(1+x+x^2)))/2)) \\ G. C. Greubel, Aug 05 2018

Formula

G.f.: G = z^4*(1 + z)*g/(1 - z - z^2 - 2*z^3*g), where g = 1 + z*g + z^2*g + z^3*g^2.

D-finite with recurrence +(n-1)*(202*n-903)*a(n) +(-250*n^2+1095*n-691)*a(n-1) +(-510*n^2+4095*n-8039)*a(n-2) +(-558*n^2+4287*n-7831)*a(n-3) +(-106*n^2+1587*n-4575)*a(n-4) +(154*n-547)*(n-7)*a(n-5)=0. - R. J. Mathar, Jul 24 2022