|
%I #97 Oct 21 2023 11:24:55
%S 1,2,14,106,838,6802,56190,470010,3968310,33747490,288654574,
%T 2480593546,21400729382,185239360178,1607913963614,13991107041306,
%U 122002082809110,1065855419418690,9327252391907790,81744134786314410,717367363052796678,6303080714967178962
%N Number of ways to move a chess rook from the lower left corner to square (n,n), with the rook moving only up or right.
%C This sequence arises in connection with mean lengths of ascents and descents in Dyck paths as follows. Let u(n,k) denote the mean length of the k-th ascent taken over all Dyck n-paths (A000108) where it is understood that if a Dyck path has fewer than k ascents, then the length of the k-th ascent is 0. For example, the second ascent in UUDUUUDDDDUD has length 3 and its fourth has length 0. Similarly, let v(n,k) denote the mean length of the k-th descent. Then u(k) := lim_{n->infinity} u(n,k) and v(k) := lim_{n->infinity} v(n,k) both exist. The sequence (u(k))_{k>=1} begins 3, 8/3, ... and decreases steadily toward a limit of 2. Analogously, v(k) increases steadily from 4/3 toward the same limit of 2. For all k >= 1, u(k+1) exceeds 2 by the same amount that v(k) falls below 2. The common difference u(k+1) - 2 = 2 - v(k) is a(k+1)/3^(2k-1). Thus the common difference sequence begins 2/3, 14/27, 106/243, ..., for k=1,2,3,... . - _David Callan_, Jul 14 2006
%C Number of ways to partition the 1 X (n-1) grid into triangles, with all vertices on grid points. - _Peter Kagey_, Nov 30 2018
%D Posting to newsgroup rec.puzzles, Dec 03 1999 by Nick Wedd (Nick(AT)maproom.co.uk).
%H Muniru A Asiru, <a href="/A051708/b051708.txt">Table of n, a(n) for n = 1..1000</a> (first 325 terms from Alois P. Heinz)
%H Alin Bostan, <a href="https://specfun.inria.fr/bostan/HDR.pdf">Calcul Formel pour la Combinatoire des Marches</a> [The text is in English], Habilitation à Diriger des Recherches, Laboratoire d'Informatique de Paris Nord, Université Paris 13, December 2017.
%H "flawr", (Programming Puzzles & Code Golf Stack Exchange user), <a href="https://codegolf.stackexchange.com/a/176651/53884">Partitioning the grid into triangles</a>
%H E. Yu Jin and M. E. Nebel, <a href="https://doi.org/10.37236/2105">A combinatorial proof of the recurrence for rook paths</a>, Electronic J. Comb. 19 (2012) #P57.
%H M. Kauers and D. Zeilberger, <a href="http://arxiv.org/abs/1011.4671">The Computational Challenge of Enumerating High-Dimensional Rook Walks</a>, arXiv:1011.4671 [math.CO], 2010.
%H Nick Webb, <a href="http://www.google.com/groups?hl=en&lr=&ie=UTF-8&th=ccb382dcef6785d3&seekm=8279b9%24hs6%241%40autumn.news.rcn.net#link1">Thread in newsgroup rec.puzzles</a>, Dec 03 1999. [Broken link]
%F G.f.: ((x*(1-x))/(sqrt(1-10*x+9*x^2)) + x)/2. - _Ralf Stephan_, Mar 23 2004; confirmed by Martin J. Erickson, Oct 05 2007
%F D-finite with recurrence a(1)=1; a(2)=2; a(n) = ((10*n-16)*a(n-1) - (9*n-27)*a(n-2)) / (n-1), for n >= 3. - Martin J. Erickson (erickson(AT)truman.edu), Nov 12 2007
%F a(n) is asymptotic to (sqrt(2)/27)*9^n/(sqrt(Pi*n)). - Martin J. Erickson, Nov 09 2007
%F G.f.: A(x) satisfies 2 * x^3 = (1 - 9*x) * A(x) * (A(x) - x). - _Michael Somos_, Jan 08 2011
%F a(n+1) = Sum_{i=0..n} (C(n-1,n-i)*Sum_{k=0..n} (C(k+i,i)*C(n-1,n-k))). - _Vladimir Kruchinin_, Apr 20 2015
%F a(n) = Sum_{k=0..n} (k+1)*C(n-2,k-1)*hypergeom([2+k,2-n],[2],-1) for n >= 2. - _Peter Luschny_, Apr 20 2015
%e G.f. = x + 2*x^2 + 14*x^3 + 106*x^4 + 838*x^5 + 6802*x^6 + 56190*x^7 + ...
%p a:= proc(n) option remember;
%p `if`(n<3, n, ((10*n-16)*a(n-1)-(9*n-27)*a(n-2))/(n-1))
%p end:
%p seq(a(n), n=1..30); # _Alois P. Heinz_, Jul 21 2012
%t CoefficientList[Series[(9*x^2 - Sqrt[9*x^2-10*x+1]*x-x) / (2*(9*x-1)), {x,0,20}],x] // Rest (* _Jean-François Alcover_, Mar 30 2011, after g.f. given by _Ralf Stephan_ *)
%t RecurrenceTable[{a[1]==1,a[2]==2,a[n]==((10n-16)a[n-1]-(9n-27)a[n-2])/ (n-1)},a,{n,30}] (* _Harvey P. Dale_, Sep 28 2013 *)
%o (PARI) {a(n) = if( n<1, 0, n--; polcoeff( 1/2 + (1 - x) / (2 * sqrt( 1 - 10*x + 9*x^2 + x * O(x^n) ) ), n ) )} /* _Michael Somos_, Jan 08 2011 */
%o (Maxima) a(n):=sum(binomial(n-1,n-i)*sum(binomial(k+i,i)*binomial(n-1,n-k),k,0,n),i,0,n); /* _Vladimir Kruchinin_, Apr 20 2015 */
%o (PARI) a(n) = n--; sum(i=0,n, binomial(n-1, n-i)*sum(k=0, n, binomial(k+i, i)*binomial(n-1, n-k))); \\ _Michel Marcus_, Apr 20 2015
%o (GAP) a:=[1,2];; for n in [3..25] do a[n]:=((10*n-16)*a[n-1]-(9*n-27)*a[n-2])/(n-1); od; a; # _Muniru A Asiru_, Nov 30 2018
%o (Magma) m:=30; R<x>:=PowerSeriesRing(Rationals(), m); Coefficients(R!( ((x*(1-x))/(Sqrt(1-10*x+9*x^2))+x)/2 )); // _G. C. Greubel_, Dec 01 2018
%Y Main diagonal of the square array given in A035002.
%Y First differences of (A084771-1)/2.
%Y Cf. A144045, A181728.
%Y Row d=2 of A181731.
%K easy,nonn,nice
%O 1,2
%A Joe Keane (jgk(AT)jgk.org)
%E More terms from _James A. Sellers_, Dec 08 1999.
|
