A000903 - OEIS

%I M1761 N0698 #69 Apr 22 2024 09:25:08

%S 1,1,2,7,23,115,694,5282,46066,456454,4999004,59916028,778525516,

%T 10897964660,163461964024,2615361578344,44460982752488,

%U 800296985768776,15205638776753680,304112757426239984,6386367801916347184

%N Number of inequivalent ways of placing n nonattacking rooks on n X n board up to rotations and reflections of the board.

%D L. C. Larson, The number of essentially different nonattacking rook arrangements, J. Recreat. Math., 7 (No. 3, 1974), circa pages 180-181.

%D R. C. Read, personal communication.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D Z. Stankova and J. West, A new class of Wilf-equivalent permutations, J. Algeb. Combin., 15 (2002), 271-290.

%H N. J. A. Sloane, <a href="/A000903/b000903.txt">Table of n, a(n) for n = 1..100</a>

%H P. J. Cameron, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

%H L. C. Larson, <a href="/A000900/a000900_1.pdf">The number of essentially different nonattacking rook arrangements</a>, J. Recreat. Math., 7 (No. 3, 1974), circa pages 180-181. [Annotated scan of pages 180 and 181 only]

%H E. Lucas, <a href="http://gallica.bnf.fr/ark:/12148/bpt6k29021h">Théorie des Nombres</a>, Gauthier-Villars, Paris, 1891, Vol. 1, p. 222.

%H E. Lucas, <a href="/A000899/a000899.pdf">Théorie des nombres</a> (annotated scans of a few selected pages)

%H R. C. Read, <a href="/A000684/a000684_1.pdf">Letter to N. J. A. Sloane, Oct. 29, 1976</a>

%H R. W. Robinson, <a href="http://dx.doi.org/10.1007/BFb0097382">Counting arrangements of bishops</a>, pp. 198-214 of Combinatorial Mathematics IV (Adelaide 1975), Lect. Notes Math., 560 (1976).

%H R. W. Robinson, <a href="/A000899/a000899_1.pdf">Counting arrangements of bishops</a>, pp. 198-214 of Combinatorial Mathematics IV (Adelaide 1975), Lect. Notes Math., 560 (1976). (Annotated scanned copy)

%H Zvezdelina Stankova-Frenkel and Julian West, <a href="http://arxiv.org/abs/math/0103152">A new class of Wilf-equivalent permutations</a>, arXiv:math/0103152 [math.CO], 2001. See Fig. 9.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/RookNumber.html">Rook Number.</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/RooksProblem.html">Rooks Problem.</a>

%F If n>1 then a(n) = 1/8 * (F(n) + C(n) + 2 * R(n) + 2 * D(n)), where F(n) = A000142(n) [all solutions, i.e., factorials], C(n) = A037223(n) [central symmetric solutions], R(n) = A037224(n) [rotationally symmetric solutions] and D(n) = A000085(n) [symmetric solutions by reflection at a diagonal]. - _Matthias Engelhardt_, Apr 05 2000

%F For asymptotics see the Robinson paper.

%e For n=4 the 7 solutions may be taken to be 1234,1243,1324,1423,1432,2143,2413.

%p Maple programs for A000142, A037223, A122670, A001813, A000085, A000898, A000407, A000902, A000900, A000901, A000899, A000903

%p P:=n->n!; # Gives A000142

%p G:=proc(n) local k; k:=floor(n/2); k!*2^k; end; # Gives A037223, A000165

%p R:=proc(n) local m; if n mod 4 = 2 or n mod 4 = 3 then RETURN(0); fi; m:=floor(n/4); (2*m)!/m!; end; # Gives A122670, A001813

%p unprotect(D); D:=proc(n) option remember; if n <= 1 then 1 else D(n-1)+(n-1)*D(n-2); fi; end; # Gives A000085

%p B:=proc(n) option remember; if n <= 1 then RETURN(1); fi; if n mod 2 = 1 then RETURN(B(n-1)); fi; 2*B(n-2) + (n-2)*B(n-4); end; # Gives A000898 (doubled up)

%p rho:=n->R(n)/2; # Gives A000407, aerated

%p beta:=n->B(n)/2; # Gives A000902, doubled up

%p delta:=n->(D(n)-B(n))/2; # Gives A000900

%p unprotect(gamma); gamma:=n-> if n <= 1 then RETURN(0) else (G(n)-B(n)-R(n))/4; fi; # Gives A000901, doubled up

%p alpha:=n->P(n)/8-G(n)/8+B(n)/4-D(n)/4; # Gives A000899

%p unprotect(sigma); sigma:=n-> if n <= 1 then RETURN(1); else P(n)/8+G(n)/8+R(n)/4+D(n)/4; fi; #Gives A000903

%t c[n_] := Floor[n/2]! 2^Floor[n/2];

%t r[n_] := If[Mod[n, 4] > 1, 0, m = Floor[n/4]; If[m == 0, 1, (2 m)!/m!]];

%t d[0] = d[1] = 1; d[n_] := d[n] = (n - 1)d[n - 2] + d[n - 1];

%t a[1] = 1; a[n_] := (n! + c[n] + 2 r[n] + 2 d[n])/8;

%t Array[a, 21] (* _Jean-François Alcover_, Apr 06 2011, after _Matthias Engelhardt_, further improved by _Robert G. Wilson v_ *)

%Y Cf. A000142, A037223, A037224, A000085, A005635, A099952, A263685.

%K nonn,nice

%O 1,3

%A _N. J. A. Sloane_

%E More terms from _David W. Wilson_, Jul 13 2003