|
|
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
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
|
|
|
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) = 4*binomial(n+1,2)*binomial(n+1,4)/binomial(n+1,3) = (n-2)*binomial(n+1,2). - Gary Detlefs, Dec 08 2011
|
|
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 + ...
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
|
(n-2)*(n)*(n+1)/2 ;
|
|
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
|
(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
|
|
|
KEYWORD
|
nonn,walk,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|