login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A182883 Number of weighted lattice paths of weight n having no (1,0)-steps of weight 1. 4
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

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.

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.

LINKS

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

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

EXAMPLE

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.

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 *)

CROSSREFS

Cf. A182882. A105868.

Sequence in context: A047708 A256277 A252746 * A172285 A192232 A243320

Adjacent sequences:  A182880 A182881 A182882 * A182884 A182885 A182886

KEYWORD

nonn,easy

AUTHOR

Emeric Deutsch, Dec 11 2010

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 21 20:07 EST 2020. Contains 332110 sequences. (Running on oeis4.)