login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000903 Number of inequivalent ways of placing n nonattacking rooks on n X n board up to rotations and reflections of the board.
(Formerly M1761 N0698)
10
1, 1, 2, 7, 23, 115, 694, 5282, 46066, 456454, 4999004, 59916028, 778525516, 10897964660, 163461964024, 2615361578344, 44460982752488, 800296985768776, 15205638776753680, 304112757426239984, 6386367801916347184 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

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

R. W. Robinson, Counting arrangements of bishops, pp. 198-214 of Combinatorial Mathematics IV (Adelaide 1975), Lect. Notes Math., 560 (1976).

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)

Zvezdelina Stankova-Frenkel and Julian West, A new class of Wilf-equivalent permutations, arXiv:math/0103152. See Fig. 9.

Eric Weisstein's World of Mathematics, Rook Number.

Eric Weisstein's World of Mathematics, Rooks Problem.

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.

EXAMPLE

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

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] + 2r[n] + 2d[n])/8; Array[a, 21] (* Jean-François Alcover, Apr 06 2011, after Matthias Engelhardt, further improved by Robert G. Wilson v *)

CROSSREFS

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

Sequence in context: A073344 A038119 A006986 * A049021 A002494 A032264

Adjacent sequences:  A000900 A000901 A000902 * A000904 A000905 A000906

KEYWORD

nonn,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from David W. Wilson, Jul 13 2003

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified April 25 18:21 EDT 2017. Contains 285416 sequences.