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. 3
1, 2, 14, 106, 838, 6802, 56190, 470010, 3968310, 33747490, 288654574, 2480593546, 21400729382, 185239360178, 1607913963614, 13991107041306, 122002082809110, 1065855419418690, 9327252391907790, 81744134786314410 (list; graph; refs; listen; history; 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 (callan(AT)stat.wisc.edu), Jul 14 2006

REFERENCES

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

LINKS

Thread in newsgroup rec.puzzles, Dec 03 1999.

M. Kauers and D. Zeilberger, The Computational Challenge of Enumerating High-Dimensional Rook Walks

FORMULA

G.f.: ((x*(1-x))/(sqrt(1-10*x+9*x^2)) + x)/2. - Ralf Stephan (ralf(AT)ark.in-berlin.de), 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

EXAMPLE

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

MATHEMATICA

CoefficientList[Series[(9*x^2 - Sqrt[9*x^2-10*x+1]*x-x) / (2*(9*x-1)), {x, 0, 20}], x] // Rest (* From Jean-François Alcover, Mar 30 2011, after g.f. given by Ralf Stephan *)

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

CROSSREFS

Main diagonal of the square array given in A035002.

First differences of (A084771-1)/2.

Cf. A144045, A181728

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 (sellersj(AT)math.psu.edu), Dec 08 1999

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Puzzles | Hot | Classics
Recent Additions | More pages | Superseeker | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified February 13 17:43 EST 2012. Contains 205523 sequences.