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

1, 2, 14, 106, 838, 6802, 56190, 470010, 3968310, 33747490, 288654574, 2480593546, 21400729382, 185239360178, 1607913963614, 13991107041306, 122002082809110, 1065855419418690, 9327252391907790, 81744134786314410, 717367363052796678, 6303080714967178962

Offset: 1

Author

Joe Keane (jgk(AT)jgk.org)

Keywords

• easy
• nonn
• nice

Comments

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

Number of ways to partition the 1 X (n-1) grid into triangles, with all vertices on grid points. - Peter Kagey, Nov 30 2018

Examples

			G.f. = x + 2*x^2 + 14*x^3 + 106*x^4 + 838*x^5 + 6802*x^6 + 56190*x^7 + ...
		

References

• Posting to newsgroup rec.puzzles, Dec 03 1999 by Nick Wedd (Nick(AT)maproom.co.uk).

Links

• Muniru A Asiru, Table of n, a(n) for n = 1..1000 (first 325 terms from Alois P. Heinz)
• Alin Bostan, Calcul Formel pour la Combinatoire des Marches [The text is in English], Habilitation à Diriger des Recherches, Laboratoire d'Informatique de Paris Nord, Université Paris 13, December 2017.
• "flawr", (Programming Puzzles & Code Golf Stack Exchange user), Partitioning the grid into triangles
• E. Yu Jin and M. E. Nebel, A combinatorial proof of the recurrence for rook paths, Electronic J. Comb. 19 (2012) #P57.
• M. Kauers and D. Zeilberger, The Computational Challenge of Enumerating High-Dimensional Rook Walks, arXiv:1011.4671 [math.CO], 2010.
• Alexander R. Povolotsky, MathOverflow, Are two formulas related to A051708 equivalent?, 2025.
• Nick Webb, Thread in newsgroup rec.puzzles, Dec 03 1999. [Broken link]

Crossrefs

Main diagonal of the square array given in A035002.

First differences of (A084771-1)/2.

Cf. A144045, A181728.

Row d=2 of A181731.

Programs

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

Magma

m:=30; R:=PowerSeriesRing(Rationals(), m); Coefficients(R!( ((x*(1-x))/(Sqrt(1-10*x+9*x^2))+x)/2 )); // G. C. Greubel, Dec 01 2018

Maple

a:= proc(n) option remember;
      `if`(n<3, n, ((10*n-16)*a(n-1)-(9*n-27)*a(n-2))/(n-1))
    end:
seq(a(n), n=1..30);  # Alois P. Heinz, Jul 21 2012

Mathematica

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

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

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

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

Formula

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

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

a(n) is asymptotic to (sqrt(2)/27)*9^n/(sqrt(Pi*n)). - Martin J. Erickson, Nov 09 2007

G.f.: A(x) satisfies 2 * x^3 = (1 - 9*x) * A(x) * (A(x) - x). - Michael Somos, Jan 08 2011

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

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

a(n) = ((-1)^(n-1) * 4^(n-1)) / (48*(n-1)*n) * ( -(4*(n-1)^2 + 16*(n-1) + 28)*JacobiP(n-2, -2*(n-1)-1, 2, -1/2) + (n+2)*(n-2)*JacobiP(n-3, -2*(n-1), 3, -1/2) ) for n > 1. - Alexander R. Povolotsky, Apr 26 2025

Extensions

More terms from James Sellers, Dec 08 1999