A144045 -id:A144045 - cp's OEIS frontend

A181731 Table A(d,n) of the number of paths of a chess rook in a d-dimensional hypercube from (0...0) to (n...n) where the rook may move in steps that are multiples of (1,0..0), (0,1,0..0), ..., (0..0,1).

1, 1, 1, 1, 2, 2, 1, 6, 14, 4, 1, 24, 222, 106, 8, 1, 120, 6384, 9918, 838, 16, 1, 720, 291720, 2306904, 486924, 6802, 32, 1, 5040, 19445040, 1085674320, 964948464, 25267236, 56190, 64, 1, 40320, 1781750880, 906140159280, 4927561419120, 439331916888, 1359631776, 470010, 128, 1, 362880, 214899027840, 1224777388630320, 54259623434853360

Offset: 1

Manuel Kauers, Nov 16 2010

The table is enumerated along antidiagonals: A(1,0), A(2,0), A(1,1), A(3,0), A(2,1), A(1,2), A(4,0), A(3,1), A(2,2), A(1,3), ... .

			A(3,1) = 6 because there are 6 rook paths on 3D chessboards from (0,0,0) to (1,1,1).
Square table A(d,n) begins:
  1,   1,      2,          4,             8, ...
  1,   2,     14,        106,           838, ...
  1,   6,    222,       9918,        486924, ...
  1,  24,   6384,    2306904,     964948464, ...
  1, 120, 291720, 1085674320, 4927561419120, ...

Alois P. Heinz, Antidiagonals n = 1..20
M. Kauers and D. Zeilberger, The Computational Challenge of Enumerating High-Dimensional Rook Walks, arXiv:1011.4671 [math.CO], 2010.

Rows d=1-12 give: A011782, A051708 (from [1,1]), A144045 (from [1,1,1]), A181749, A181750, A181751, A181752, A181724, A181725, A181726, A181727, A181728.
Columns n=0-2 give: A000012, A000142, A105749.
Main diagonal gives A246623.

b:= proc(l) option remember; `if`({l[]} minus {0}={}, 1, add(add
       (b(sort(subsop(i=l[i]-j, l))), j=1..l[i]), i=1..nops(l)))
    end:
A:= (d, n)-> b([n$d]):
seq(seq(A(h-n, n), n=0..h-1), h=1..10); # Alois P. Heinz, Jul 21 2012

b[l_List] := b[l] = If[Union[l] ~Complement~ {0} == {}, 1, Sum[ Sum[ b[ Sort[ ReplacePart[l, i -> l[[i]] - j]]], {j, 1, l[[i]]}], {i, 1, Length[l]}]]; A[d_, n_] := b[Array[n&, d]]; Table[Table[A[h-n, n], {n, 0, h-1}], {h, 1, 10}] // Flatten (* Jean-François Alcover, Feb 25 2015, after Alois P. Heinz *)

Edited by Alois P. Heinz, Jul 21 2012

Minor edits by Vaclav Kotesovec, Sep 03 2014

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.

Original entry on oeis.org

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

Offset: 1

Joe Keane (jgk(AT)jgk.org)

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

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

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

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]

Main diagonal of the square array given in A035002.
First differences of (A084771-1)/2.
Cf. A144045, A181728.
Row d=2 of A181731.

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

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

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

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

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

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

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

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

More terms from James Sellers, Dec 08 1999

cp's OEIS Frontend

A181731 Table A(d,n) of the number of paths of a chess rook in a d-dimensional hypercube from (0...0) to (n...n) where the rook may move in steps that are multiples of (1,0..0), (0,1,0..0), ..., (0..0,1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions