|
| |
|
|
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
|
|
|
REFERENCES
|
Posting to newsgroup rec.puzzles, Dec 03 1999 by Nick Wedd (Nick(AT)maproom.co.uk).
|
|
|
LINKS
|
Alois P. Heinz, Table of n, a(n) for n = 1..325
Thread in newsgroup rec.puzzles, Dec 03 1999.
M. Kauers and D. Zeilberger, The Computational Challenge of Enumerating High-Dimensional Rook Walks
E. Yu Jin, M. E. Nebel, A combinatorial proof of the recurrence for rook paths, El. J. Comb. 19 (2012) #P57
|
|
|
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
|
|
|
EXAMPLE
|
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 (* 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.
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
|
| |
|
|
