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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002465 Number of ways to place n nonattacking bishops on an n X n board.
(Formerly M3616 N1467)
23
1, 4, 26, 260, 3368, 53744, 1022320, 22522960, 565532992, 15915225216, 496911749920, 17029582652416, 636101065346560, 25705530908501760, 1118038500044633088, 52054862490790200576, 2584158975023147147264 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

The old name of this sequence was wrong. It was corrected by Vaclav Kotesovec, Feb 19 2011. Kotesovec remarks that the maximal number of nonattacking bishops on an n X n board is 2n-2, and there are 2^n ways to place them. See the Kotesovec link.

REFERENCES

W. Ahrens, Mathematische Unterhaltungen und Spiele. Teubner, Leipzig, Vol. 1, 3rd ed., 1921; Vol. 2, 2nd ed., 1918. See Vol. 1, p. 271.

S. E. Arshon, Matematicheskoe prosveshchenie, 8, 1936, pp. 24-29.

J. Perott, Sur le probleme des fous, Bulletin de la société mathématique de France, Tome XI, 1883, p. 173-186.

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

N. Vilenkin, Populyarnaja kombinatorika, 1972, p. 166.

LINKS

Vaclav Kotesovec, Table of n, a(n) for n = 1..375

W. Ahrens, Mathematische Unterhaltungen und Spiele, Leipzig: B. G. Teubner, 1901.

D. Atkinson, Solution to the n-Bishops problem of trying to place n identical bishops on an n x n chessboard. [Broken link?]

V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, pp. 242-252

Eric Weisstein's World of Mathematics, Bishops Problem.

FORMULA

Asymptotic: a(n)/(n-1)! ~ 0.631266 * 3.08827^n. - Vaclav Kotesovec, Mar 23 2011

The second constant is 2/(z*(2-z)) = 3.0882773047417401791158400820254..., where z is the root z=1.593624260040... of the equation exp(z)*(2-z)=2. - Vaclav Kotesovec, May 27 2011

For constants see A238258 and A238260. - Vaclav Kotesovec, Feb 21 2014

EXAMPLE

a(3) = 26: ways to place 3 nonattacking bishops on a 3 X 3 board:

XXX XXO XXO XOX OXO

OOO OOO OOO OOO OXO

OOO XOO OXO OXO OXO

(4) (8) (8) (4) (2)

MATHEMATICA

peven[i_]:=(Sum[(-1)^j*Binomial[n-i-1, j]/(n-i-1)!*(n-i+1-j)^(n/2)*(n-i-j)^(n/2-1), {j, 0, n-i-1}]);

poddblack[i_]:=(Sum[(-1)^j*Binomial[n-i-1, j]/(n-i-1)!*(n-i+1-j)^((n+1)/2)*(n-i-j)^((n-3)/2), {j, 0, n-i-1}]);

poddwhite[i_]:=(Sum[(-1)^j*Binomial[n-i-1, j]/(n-i-1)!*(n-i+1-j)^((n-1)/2)*(n-i-j)^((n-1)/2), {j, 0, n-i-1}]);

Table[If[n==1, 1, Sum[If[EvenQ[n], peven[i]*peven[n-i], poddblack[i]*poddwhite[n-i]], {i, 1, n-1}]], {n, 1, 50}]

(* Alternative formula with Stirling numbers of the second kind: *)

Table[If[n==1, 1, Sum[Sum[Binomial[Floor[(n+1)/2], j] * StirlingS2[j+Floor[n/2], n-i], {j, 0, Floor[(n+1)/2]}] * Sum[Binomial[Floor[n/2], j] * StirlingS2[j+Floor[(n+1)/2], i], {j, 0, Floor[n/2]}], {i, 1, n-1}]], {n, 1, 50}] (* Vaclav Kotesovec, Mar 23 2011 *)

CROSSREFS

Cf. A238258, A238260, A187235.

Sequence in context: A215242 A098620 A215266 * A248668 A079473 A145164

Adjacent sequences:  A002462 A002463 A002464 * A002466 A002467 A002468

KEYWORD

nonn,nice

AUTHOR

N. J. A. Sloane.

EXTENSIONS

More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Nov 20 2006

Definition corrected by V. Kotesovec, Feb 19 2011

Terms a(11)-a(17) from Vaclav Kotesovec, Mar 09 2011

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 January 17 07:18 EST 2018. Contains 297787 sequences.