login
The OEIS is supported by the many generous donors 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

%I M4134 #128 Sep 08 2022 08:44:33

%S 6,20,45,84,140,216,315,440,594,780,1001,1260,1560,1904,2295,2736,

%T 3230,3780,4389,5060,5796,6600,7475,8424,9450,10556,11745,13020,14384,

%U 15840,17391,19040,20790,22644,24605,26676,28860,31160,33579,36120,38786,41580,44505

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

%C The steps are N, S, E or W.

%C 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 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 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 L. B. W. Jolley, "Summation of Series", Dover Publications, 1961, p. 38.

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

%H Vincenzo Librandi, <a href="/A005564/b005564.txt">Table of n, a(n) for n = 3..1000</a>

%H DefElement, <a href="https://defelement.com/elements/nedelec1.html">Nédélec first kind</a>

%H R. K. Guy, <a href="/A005555/a005555.pdf">Letter to N. J. A. Sloane, May 1990</a>

%H 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 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 Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (4,-6,4,-1).

%F G.f.: x^3 * ( 6 - 4*x + x^2 ) / ( 1 - x )^4. [_Simon Plouffe_ in his 1992 dissertation]

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

%F a(n) = Sum_{j = 0..n} ((n+j-1)^2-(n-j+1)^2)/4. - _Zerinvary Lajos_, Sep 13 2006

%F a(n) = Sum_{k = 2..n-1} k*n. - _Zerinvary Lajos_, Jan 29 2008

%F 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 a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4). - _Vincenzo Librandi_, Jun 18 2012

%F E.g.f.: x - x*(2 - 2*x - x^2)*exp(x)/2. - _Ilya Gutkovskiy_, Jun 29 2016

%F a(n) = 6*Sum_{i = 1..n-1} A000217(i) - n*A000217(n). - _Bruno Berselli_, Jul 03 2018

%F Sum_{n>=3} 1/a(n) = 5/18. - _Amiram Eldar_, Oct 07 2020

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

%e 1

%e 0 4

%e 9 0 6

%e 0 16 0 4

%e 10 0 9 0 1

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

%e The a(3) = 6 walks are EEN, ENE, ENW, NEW, NSN, NNS. - _Michael Somos_, Jun 09 2014

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

%e From _Gregory L. Simay_ Jun 28 2016: (Start)

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

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

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

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

%p A005564 := proc(n)

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

%p end proc: seq(A005564(n),n=0..10) ; # _R. J. Mathar_, Dec 09 2011

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

%t LinearRecurrence[{4,-6,4,-1},{6,20,45,84},50] (* _Vincenzo Librandi_, Jun 18 2012 *)

%o (PARI) a(n)=(n-2)*(n)*(n+1)/2 \\ _Charles R Greathouse IV_, Dec 12 2011

%o (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 (GAP) a:=List([0..45],n->(n+1)*Binomial(n+4,2)); # _Muniru A Asiru_, Feb 15 2018

%Y Cf. A000217.

%Y First differences of A001701.

%Y Fourth column of A093768.

%K nonn,walk,easy

%O 3,1

%A _N. J. A. Sloane_

%E Entry revised by _N. J. A. Sloane_, Jul 06 2012

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 10:55 EDT 2024. Contains 371241 sequences. (Running on oeis4.)