A182883 Number of weighted lattice paths of weight n having no (1,0)-steps of weight 1.

1, 0, 1, 2, 1, 6, 7, 12, 31, 40, 91, 170, 281, 602, 1051, 1988, 3907, 7044, 13735, 25962, 48643, 94094, 177145, 338184, 647791, 1228812, 2356927, 4500678, 8595913, 16486966, 31521543, 60419872, 115870879, 222045160, 426275647, 818054654

Offset: 0

Author

Emeric Deutsch, Dec 11 2010

Keywords

• nonn
• easy

Comments

L_n is the set of lattice paths of weight n that start at (0,0) end on the horizontal axis and whose steps are of the following four kinds: an (1,0)-step with weight 1; an (1,0)-step with weight 2; a (1,1)-step with weight 2; a (1,-1)-step with weight 1. The weight of a path is the sum of the weights of its steps.

Diagonal of the rational function 1 / (1 - x^3 - y^3 - (x*y)^2). - Ilya Gutkovskiy, Apr 23 2025

Examples

			a(3)=2. Indeed, denoting by h (H) the (1,0)-step of weight 1 (2), and u=(1,1), d=(1,-1), the five paths of weight 3 are ud, du, hH, Hh, and hhh; two of them, namely ud and du, contain no h steps.
		

References

• 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, N. Zagaglia Salvi, On the rank polynomial of the lattice of order ideals of fences and crowns, Discrete Mathematics 259 (2002), 163-177.

Crossrefs

Cf. A182882. A105868.

Programs

Maple

G:=1/sqrt(1-2*z^2+z^4-4*z^3): Gser:=series(G,z=0,40): seq(coeff(Gser,z,n), n=0..35);
# Alternatively (after Bala):
seq(add(binomial(n-k,k)*binomial(k,n-2*k), k=ceil(n/3)...floor(n/2)),n=0..35); # Peter Luschny, Feb 07 2017
# With natural summation bound:
a := n -> add((-1)^k*binomial(n,k)*hypergeom([-k,k-n,k-n], [1,-n], -1), k=0..n): seq(simplify(a(n)), n=0..35); # Peter Luschny, Feb 13 2018

Mathematica

CoefficientList[Series[1/Sqrt[1-2x^2+x^4-4x^3],{x,0,40}],x] (* Harvey P. Dale, Oct 16 2011 *)

Formula

a(n) = A182882(n,0).

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

It appears that a(n) = Sum_{k = 0..floor(n/2)} binomial(n-k,k)*binomial(k,n-2*k): this gives correct values for a(0) through a(35). If true, then sequence equals antidiagonal sums of triangle A105868. - Peter Bala, Mar 06 2013

D-finite n*a(n) = (2*n - 2)*a(n-2) + (4*n - 6)*a(n-3) - (n - 2)*a(n-4), follows easily by differentiating the o.g.f. Maple's sumrecursion command verifies that Sum_{k = 0..floor(n/2)} binomial(n-k,k)*binomial(k,n-2*k) satisfies the same recurrence with the same initial conditions thus proving the above conjecture. - Peter Bala, Feb 07 2017

a(n) = Sum_{k=0..n} (-1)^k*binomial(n, k)*hypergeom([-k, k-n, k-n], [1, -n], -1). - Peter Luschny, Feb 13 2018