login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons 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

%I M3616 N1467

%S 1,4,26,260,3368,53744,1022320,22522960,565532992,15915225216,

%T 496911749920,17029582652416,636101065346560,25705530908501760,

%U 1118038500044633088,52054862490790200576,2584158975023147147264

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

%C 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.

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

%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 N. Vilenkin, Populyarnaja kombinatorika, 1972, p. 166.

%H Vaclav Kotesovec, <a href="/A002465/b002465.txt">Table of n, a(n) for n = 1..375</a>

%H W. Ahrens, <a href="https://archive.org/stream/mathunterhaltung00ahrerich#page/n287/mode/2up">Mathematische Unterhaltungen und Spiele</a>, Leipzig: B. G. Teubner, 1901.

%H S. E. Arshon, <a href="http://mi.mathnet.ru/eng/mp694">Solution of one combinatorial problem</a> [in Russian], Matematicheskoe prosveshchenie, Ser. 1, 8, 1936, pp. 24-29.

%H D. Atkinson, <a href="http://www.cse.scu.edu/~atkinson/teaching/sp02/171/projects/2/solutions/Queens.cpp">Solution to the n-Bishops problem of trying to place n identical bishops on an n x n chessboard.</a> [Broken link?]

%H Vaclav Kotesovec, <a href="https://oeis.org/wiki/User:Vaclav_Kotesovec">Non-attacking chess pieces</a>, 6ed, 2013, pp. 242-252.

%H J. Perott, <a href="https://doi.org/10.24033/bsmf.267">Sur le problème des fous</a>, Bulletin de la société mathématique de France, Tome XI, 1883, p. 173-186.

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

%F Asymptotic: a(n)/(n-1)! ~ 0.631266 * 3.08827^n. - _Vaclav Kotesovec_, Mar 23 2011

%F 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

%F For constants see A238258 and A238260. - _Vaclav Kotesovec_, Feb 21 2014

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

%e XXX XXO XXO XOX OXO

%e OOO OOO OOO OOO OXO

%e OOO XOO OXO OXO OXO

%e (4) (8) (8) (4) (2)

%t 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}]);

%t 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}]);

%t 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}]);

%t 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}]

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

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

%Y Cf. A238258, A238260, A187235.

%K nonn,nice

%O 1,2

%A _N. J. A. Sloane_

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

%E Definition corrected by _Vaclav Kotesovec_, Feb 19 2011

%E Terms a(11)-a(17) from _Vaclav Kotesovec_, Mar 09 2011

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 12 19:50 EDT 2021. Contains 342932 sequences. (Running on oeis4.)