A005564 Number of n-step walks on square lattice in the first quadrant which finish at distance n-3 from the x-axis.

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

Author

N. J. A. Sloane

Keywords

• nonn
• walk
• easy

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

Examples

			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)
		

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

Crossrefs

Cf. A000217.

First differences of A001701.

Fourth column of A093768.

Programs

GAP

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

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

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

PARI

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

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

Extensions

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