login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005564 Number of n-step walks on square lattice in the first quadrant which finish at distance n-3 from the x-axis.
(Formerly M4134)
11
6, 20, 45, 84, 140, 216, 315, 440, 594, 780, 1001, 1260, 1560, 1904, 2295, 2736, 3230, 3780, 4389, 5060, 5796, 6600, 7475, 8424, 9450, 10556, 11745, 13020, 14384, 15840, 17391, 19040, 20790, 22644, 24605, 26676, 28860, 31160, 33579, 36120, 38786, 41580, 44505 (list; graph; refs; listen; history; text; internal format)
OFFSET

3,1

COMMENTS

The steps are N, S, E or W.

For n>=4, a(n-1)/2 is the coefficient c(n-2) of the m^(n-2) term of P(m,n) = (c(m-1)* m^(n-1) + c(m-2)* m^(n-2) +...+ c(0)* m^0)/((a!)* (a-1)!), the polynomial for the number of partitions of m with exactly n parts. - Gregory L. Simay, Jun 28 2016

2a(n) is the denominator of formula 207 in Jolleys' "Summation of Series." 2/(1*3*4)+3/(2*4*5)+...n terms. Sum_{k = 1..n} (k+1)/(k*(k+2)*(k+3)). This summation has a closed form of 17/36-(6*n^2+21*n+17)/(6*(n+1)*(n+2)*(n+3)). - Gary Detlefs, Mar 15 2018

REFERENCES

L. B. W. Jolley, "Summation of Series", Dover Publications, 1961, p. 38.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 3..1000

R. K. Guy, Letter to N. J. A. Sloane, May 1990

R. K. Guy, Catwalks, Sandsteps and Pascal Pyramids, J. Integer Seqs., Vol. 3 (2000), #00.1.6. See figure 4, sum of terms in (n-2)-nd row.

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.

Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

FORMULA

G.f.: x^3 * ( 6 - 4*x + x^2 ) / ( 1 - x )^4. [Simon Plouffe in his 1992 dissertation]

a(n) = (n-2)*n*(n+1)/2 = (n-2)*A000217(n).

a(n) = Sum_{j = 0..n} ((n+j-1)^2-(n-j+1)^2)/4. - Zerinvary Lajos, Sep 13 2006

a(n) = Sum_{k = 2..n-1} k*n. - Zerinvary Lajos, Jan 29 2008

a(n) = 4*binomial(n+1,2)*binomial(n+1,4)/binomial(n+1,3) = (n-2)*binomial(n+1,2). - Gary Detlefs, Dec 08 2011

a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4). - Vincenzo Librandi, Jun 18 2012

E.g.f.: x - x*(2 - 2*x - x^2)*exp(x)/2. - Ilya Gutkovskiy, Jun 29 2016

a(n) = 6*Sum_{i = 1..n-1} A000217(i) - n*A000217(n). - Bruno Berselli, Jul 03 2018

EXAMPLE

The n=4 diagram in Fig. 4 of Guy's paper is:

1

0 4

9 0 6

0 16 0 4

10 0 9 0 1

Adding 16+4 we get a(4)=20.

The a(3) = 6 walks are EEN, ENE, ENW, NEW, NSN, NNS. - Michael Somos, Jun 09 2014

G.f. = 6*x^3 + 20*x^4 + 45*x^5 + 84*x^6 + 140*x^7 + 216*x^8 + 315*x^9 + ...

From Gregory L. Simay Jun 28 2016: (Start)

P(m,4) = (m^3 + 3*m^2 + ...)/(3!*4!) with 3 = a(3)/2 = 6/2.

P(m,5) = (m^4 + 10*m^3 + ...)/(4!*5!) with 10 = a(4)/2 = 20/2.

P(m,6) = (m^5 + (45/2)*m^4 +...)/(5!*6!) with 45/2 = a(5)/2.

P(m,7) = (m^6 + 42*m^5 +...)/(6!*7!) with 42 = a(6)/2 = 84/2. (End)

MAPLE

A005564 := proc(n)

        (n-2)*(n)*(n+1)/2 ;

end proc: seq(A005564(n), n=0..10) ; # R. J. Mathar, Dec 09 2011

MATHEMATICA

Table[(n-2)*Binomial[n+1, 2], {n, 3, 40}]

LinearRecurrence[{4, -6, 4, -1}, {6, 20, 45, 84}, 50] (* Vincenzo Librandi, Jun 18 2012 *)

PROG

(PARI) a(n)=(n-2)*(n)*(n+1)/2 \\ Charles R Greathouse IV, Dec 12 2011

(MAGMA) I:=[6, 20, 45, 84]; [n le 4 select I[n] else 4*Self(n-1)-6*Self(n-2)+4*Self(n-3)-Self(n-4): n in [1..45]]; // Vincenzo Librandi, Jun 18 2012

(GAP) a:=List([0..45], n->(n+1)*Binomial(n+4, 2)); # Muniru A Asiru, Feb 15 2018

CROSSREFS

Cf. A000217.

First differences of A001701.

Fourth column of A093768.

Sequence in context: A006137 A225269 A048969 * A011928 A055455 A203552

Adjacent sequences:  A005561 A005562 A005563 * A005565 A005566 A005567

KEYWORD

nonn,walk,easy

AUTHOR

N. J. A. Sloane

EXTENSIONS

Entry revised by N. J. A. Sloane, Jul 06 2012

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 November 15 01:25 EST 2019. Contains 329143 sequences. (Running on oeis4.)