login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 5
1, 2, 14, 106, 838, 6802, 56190, 470010, 3968310, 33747490, 288654574, 2480593546, 21400729382, 185239360178, 1607913963614, 13991107041306, 122002082809110, 1065855419418690, 9327252391907790, 81744134786314410, 717367363052796678, 6303080714967178962 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

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->infty} u(n,k) and v(k) := lim_{n->infty} 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

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)

Thread in newsgroup rec.puzzles, Dec 03 1999. [Broken link]

M. Kauers and D. Zeilberger, The Computational Challenge of Enumerating High-Dimensional Rook Walks, arXiv:1011.4671 [math.CO], 2010.

E. Yu Jin, M. E. Nebel, A combinatorial proof of the recurrence for rook paths, El. J. Comb. 19 (2012) #P57

Programming Puzzles & Code Golf Stack Exchange user flawr, Partitioning the grid into triangles

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

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

EXAMPLE

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

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

PROG

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

(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) = 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

(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<x>:=PowerSeriesRing(Rationals(), m); Coefficients(R!( ((x*(1-x))/(Sqrt(1-10*x+9*x^2))+x)/2 )); // G. C. Greubel, Dec 01 2018

CROSSREFS

Main diagonal of the square array given in A035002.

First differences of (A084771-1)/2.

Cf. A144045, A181728.

Row d=2 of A181731.

Sequence in context: A122680 A121122 A026293 * A074618 A108436 A088754

Adjacent sequences:  A051705 A051706 A051707 * A051709 A051710 A051711

KEYWORD

easy,nonn,nice

AUTHOR

Joe Keane (jgk(AT)jgk.org)

EXTENSIONS

More terms from James A. Sellers, Dec 08 1999

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 20 18:39 EST 2019. Contains 320345 sequences. (Running on oeis4.)