cp's OEIS Frontend

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

%I A005564 M4134 #132 Apr 28 2025 09:00:36
%S A005564 6,20,45,84,140,216,315,440,594,780,1001,1260,1560,1904,2295,2736,
%T A005564 3230,3780,4389,5060,5796,6600,7475,8424,9450,10556,11745,13020,14384,
%U A005564 15840,17391,19040,20790,22644,24605,26676,28860,31160,33579,36120,38786,41580,44505
%N A005564 Number of n-step walks on square lattice in the first quadrant which finish at distance n-3 from the x-axis.
%C A005564 The steps are N, S, E or W.
%C A005564 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
%C A005564 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
%C A005564 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
%D A005564 L. B. W. Jolley, "Summation of Series", Dover Publications, 1961, p. 38.
%D A005564 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005564 Vincenzo Librandi, <a href="/A005564/b005564.txt">Table of n, a(n) for n = 3..1000</a>
%H A005564 DefElement, <a href="https://defelement.org/elements/nedelec1.html">Nédélec first kind</a>
%H A005564 R. K. Guy, <a href="/A005555/a005555.pdf">Letter to N. J. A. Sloane, May 1990</a>
%H A005564 R. K. Guy, Catwalks, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/GUY/catwalks.html">Sandsteps and Pascal Pyramids</a>, J. Integer Seqs., Vol. 3 (2000), #00.1.6. See figure 4, sum of terms in (n-2)-nd row.
%H A005564 Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H A005564 Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H A005564 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (4,-6,4,-1).
%F A005564 G.f.: x^3 * ( 6 - 4*x + x^2 ) / ( 1 - x )^4. [_Simon Plouffe_ in his 1992 dissertation]
%F A005564 a(n) = (n-2)*n*(n+1)/2 = (n-2)*A000217(n).
%F A005564 a(n) = Sum_{j = 0..n} ((n+j-1)^2-(n-j+1)^2)/4. - _Zerinvary Lajos_, Sep 13 2006
%F A005564 a(n) = Sum_{k = 2..n-1} k*n. - _Zerinvary Lajos_, Jan 29 2008
%F A005564 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
%F A005564 a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4). - _Vincenzo Librandi_, Jun 18 2012
%F A005564 E.g.f.: x - x*(2 - 2*x - x^2)*exp(x)/2. - _Ilya Gutkovskiy_, Jun 29 2016
%F A005564 a(n) = 6*Sum_{i = 1..n-1} A000217(i) - n*A000217(n). - _Bruno Berselli_, Jul 03 2018
%F A005564 Sum_{n>=3} 1/a(n) = 5/18. - _Amiram Eldar_, Oct 07 2020
%e A005564 The n=4 diagram in Fig. 4 of Guy's paper is:
%e A005564 1
%e A005564 0 4
%e A005564 9 0 6
%e A005564 0 16 0 4
%e A005564 10 0 9 0 1
%e A005564 Adding 16+4 we get a(4)=20.
%e A005564 The a(3) = 6 walks are EEN, ENE, ENW, NEW, NSN, NNS. - _Michael Somos_, Jun 09 2014
%e A005564 G.f. = 6*x^3 + 20*x^4 + 45*x^5 + 84*x^6 + 140*x^7 + 216*x^8 + 315*x^9 + ...
%e A005564 From _Gregory L. Simay_ Jun 28 2016: (Start)
%e A005564 P(m,4) = (m^3 + 3*m^2 + ...)/(3!*4!) with 3 = a(3)/2 = 6/2.
%e A005564 P(m,5) = (m^4 + 10*m^3 + ...)/(4!*5!) with 10 = a(4)/2 = 20/2.
%e A005564 P(m,6) = (m^5 + (45/2)*m^4 +...)/(5!*6!) with 45/2 = a(5)/2.
%e A005564 P(m,7) = (m^6 + 42*m^5 +...)/(6!*7!) with 42 = a(6)/2 = 84/2. (End)
%p A005564 A005564 := proc(n)
%p A005564         (n-2)*(n)*(n+1)/2 ;
%p A005564 end proc: seq(A005564(n),n=0..10) ; # _R. J. Mathar_, Dec 09 2011
%t A005564 Table[(n-2)*Binomial[n+1, 2], {n, 3, 40}]
%t A005564 LinearRecurrence[{4,-6,4,-1},{6,20,45,84},50] (* _Vincenzo Librandi_, Jun 18 2012 *)
%o A005564 (PARI) a(n)=(n-2)*(n)*(n+1)/2 \\ _Charles R Greathouse IV_, Dec 12 2011
%o A005564 (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
%o A005564 (GAP) a:=List([0..45],n->(n+1)*Binomial(n+4,2)); # _Muniru A Asiru_, Feb 15 2018
%Y A005564 Cf. A000217.
%Y A005564 First differences of A001701.
%Y A005564 Fourth column of A093768.
%K A005564 nonn,walk,easy
%O A005564 3,1
%A A005564 _N. J. A. Sloane_
%E A005564 Entry revised by _N. J. A. Sloane_, Jul 06 2012