A182890 Number of (1,0)-steps of weight 1 at level 0 in all weighted lattice paths in L_n.

0, 1, 2, 5, 14, 36, 94, 247, 646, 1691, 4428, 11592, 30348, 79453, 208010, 544577, 1425722, 3732588, 9772042, 25583539, 66978574, 175352183, 459077976, 1201881744, 3146567256, 8237820025, 21566892818, 56462858429, 147821682470, 387002188980, 1013184884470

Offset: 0

Author

Emeric Deutsch, Dec 12 2010

Keywords

• nonn
• easy

Comments

The members of L_n are paths of weight n that start at (0,0) and end on the horizontal axis and whose steps are of the following four kinds: a (1,0)-step with weight 1, a (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.

Examples

			a(3)=5. Indeed, denoting by h (resp. H) the (1,0)-step of weight 1 (resp. 2), and u=(1,1), d=(1,-1), the five paths of weight 3 are ud, du, hH, Hh, and hhh; they contain 0+0+1+1+3=5 h-steps at level 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.
• E. Munarini and N. Zagaglia Salvi, On the Rank Polynomial of the Lattice of Order Ideals of Fences and Crowns, Discrete Mathematics 259 (2002), 163-177.
• Index entries for linear recurrences with constant coefficients, signature (2,1,2,-1).

Crossrefs

Cf. A182888.

Programs

Maple

G:=z/(1+z+z^2)/(1-3*z+z^2): Gser:=series(G,z=0,33): seq(coeff(Gser,z,n),n=0..30);

Mathematica

Table[Sum[Binomial[2n+2-2k,2k-1]/2, {k,0,n+1}], {n,0,30}]; (* Rigoberto Florez, Apr 10 2023 *)

Maxima

a(n):=1/2*sum(binomial(2*n-2*m, 2*m+1), m, 0, (2*n-1)/4); /* Vladimir Kruchinin, Jan 24 2022 */

Formula

G.f: x/((1+x+x^2)*(1-3*x+x^2)).

a(n) = Sum_{k>=0} k*A182888(n,k).

a(n) = (A000045(2n+2) - ((-1)^n)*A010892(n))/4. - John M. Campbell, Dec 30 2016

a(n) = Sum_{m=0..n} C(2*n-2*m,2*m+1)/2. - Vladimir Kruchinin, Jan 24 2022