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)

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

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

a(n) is the number of degrees of freedom in a tetrahedral cell for a Nédélec first kind finite element space of order n-2. - Matthew Scroggs, Jan 02 2021

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

DefElement, Nédélec first kind

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; arXiv:0911.4975 [math.NT], 2009.

Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 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

Sum_{n>=3} 1/a(n) = 5/18. - Amiram Eldar, Oct 07 2020

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: A225269 A048969 A353692 * 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