A002465 Number of ways to place n nonattacking bishops on an n X n board.

1, 1, 4, 26, 260, 3368, 53744, 1022320, 22522960, 565532992, 15915225216, 496911749920, 17029582652416, 636101065346560, 25705530908501760, 1118038500044633088, 52054862490790200576, 2584158975023147147264

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• nice

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.

Examples

			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)
		

References

• W. Ahrens, Mathematische Unterhaltungen und Spiele. Teubner, Leipzig, Vol. 1, 3rd ed., 1921; Vol. 2, 2nd ed., 1918. See Vol. 1, p. 271.
• 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 = 0..375
• W. Ahrens, Mathematische Unterhaltungen und Spiele, Leipzig: B. G. Teubner, 1901.
• S. E. Arshon, Solution of one combinatorial problem [in Russian], Matematicheskoe prosveshchenie, Ser. 1, 8, 1936, pp. 24-29.
• D. Atkinson, Solution to the n-Bishops problem of trying to place n identical bishops on an n x n chessboard. [Broken link?]
• Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, pp. 242-252.
• J. Perott, Sur le problème des fous, Bulletin de la société mathématique de France, Tome XI, 1883, p. 173-186.
• Eric Weisstein's World of Mathematics, Bishops Problem.

Crossrefs

Cf. A238258, A238260, A187235.

Main diagonal of A378590.

Programs

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

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

Extensions

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

Definition corrected by Vaclav Kotesovec, Feb 19 2011

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

a(0)=1 prepended by Alois P. Heinz, Dec 01 2024