A000903 Number of inequivalent ways of placing n nonattacking rooks on n X n board up to rotations and reflections of the board.
1, 1, 2, 7, 23, 115, 694, 5282, 46066, 456454, 4999004, 59916028, 778525516, 10897964660, 163461964024, 2615361578344, 44460982752488, 800296985768776, 15205638776753680, 304112757426239984, 6386367801916347184
Offset: 1
Examples
For n=4 the 7 solutions may be taken to be 1234,1243,1324,1423,1432,2143,2413.
References
- L. C. Larson, The number of essentially different nonattacking rook arrangements, J. Recreat. Math., 7 (No. 3, 1974), circa pages 180-181.
- R. C. Read, personal communication.
- N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
- Z. Stankova and J. West, A new class of Wilf-equivalent permutations, J. Algeb. Combin., 15 (2002), 271-290.
Links
- N. J. A. Sloane, Table of n, a(n) for n = 1..100
- P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
- L. C. Larson, The number of essentially different nonattacking rook arrangements, J. Recreat. Math., 7 (No. 3, 1974), circa pages 180-181. [Annotated scan of pages 180 and 181 only]
- E. Lucas, Théorie des Nombres, Gauthier-Villars, Paris, 1891, Vol. 1, p. 222.
- E. Lucas, Théorie des nombres (annotated scans of a few selected pages)
- R. C. Read, Letter to N. J. A. Sloane, Oct. 29, 1976
- R. W. Robinson, Counting arrangements of bishops, pp. 198-214 of Combinatorial Mathematics IV (Adelaide 1975), Lect. Notes Math., 560 (1976).
- R. W. Robinson, Counting arrangements of bishops, pp. 198-214 of Combinatorial Mathematics IV (Adelaide 1975), Lect. Notes Math., 560 (1976). (Annotated scanned copy)
- Zvezdelina Stankova-Frenkel and Julian West, A new class of Wilf-equivalent permutations, arXiv:math/0103152 [math.CO], 2001. See Fig. 9.
- Eric Weisstein's World of Mathematics, Rook Number.
- Eric Weisstein's World of Mathematics, Rooks Problem.
Programs
-
Maple
Maple programs for A000142, A037223, A122670, A001813, A000085, A000898, A000407, A000902, A000900, A000901, A000899, A000903 P:=n->n!; # Gives A000142 G:=proc(n) local k; k:=floor(n/2); k!*2^k; end; # Gives A037223, A000165 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 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 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) rho:=n->R(n)/2; # Gives A000407, aerated beta:=n->B(n)/2; # Gives A000902, doubled up delta:=n->(D(n)-B(n))/2; # Gives A000900 unprotect(gamma); gamma:=n-> if n <= 1 then RETURN(0) else (G(n)-B(n)-R(n))/4; fi; # Gives A000901, doubled up alpha:=n->P(n)/8-G(n)/8+B(n)/4-D(n)/4; # Gives A000899 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
-
Mathematica
c[n_] := Floor[n/2]! 2^Floor[n/2]; r[n_] := If[Mod[n, 4] > 1, 0, m = Floor[n/4]; If[m == 0, 1, (2 m)!/m!]]; d[0] = d[1] = 1; d[n_] := d[n] = (n - 1)d[n - 2] + d[n - 1]; a[1] = 1; a[n_] := (n! + c[n] + 2 r[n] + 2 d[n])/8; Array[a, 21] (* Jean-François Alcover, Apr 06 2011, after Matthias Engelhardt, further improved by Robert G. Wilson v *)
Formula
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
For asymptotics see the Robinson paper.
Extensions
More terms from David W. Wilson, Jul 13 2003