|
| |
|
|
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.
|
|
6
|
|
|
|
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->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
|
|
|
REFERENCES
|
Posting to newsgroup rec.puzzles, Dec 03 1999 by Nick Wedd (Nick(AT)maproom.co.uk).
|
|
|
LINKS
|
|
|
|
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
|
|
|
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:
|
|
|
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.
|
|
|
KEYWORD
|
easy,nonn,nice
|
|
|
AUTHOR
|
Joe Keane (jgk(AT)jgk.org)
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
