|
| |
|
|
A002465
|
|
Number of ways to place n nonattacking bishops on an n X n board.
(Formerly M3616 N1467)
|
|
14
| |
|
|
1, 4, 26, 260, 3368, 53744, 1022320, 22522960, 565532992, 15915225216, 496911749920, 17029582652416, 636101065346560, 25705530908501760, 1118038500044633088, 52054862490790200576, 2584158975023147147264
(list; graph; refs; listen; history; 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.
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).
S. E. Arshon, Matematicheskoe prosveshchenie 8, 1936, p. 24-29.
N. Vilenkin, Populyarnaja kombinatorika, 1972, p. 166.
J. Perott, Sur le probleme des fous, Bulletin de la société mathématique de France, Tome XI, 1883, p. 173-186.
|
|
|
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, Number of ways of placing non-attacking queens, kings, bishops and knights (in English and Czech)
Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
|
|
|
FORMULA
| Asymptotic: a(n)/(n-1)! ~ 0.63 * 3.08827^n [From V. 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. [From V. Kotesovec, May 27 2011]
|
|
|
EXAMPLE
| a(3) = 26: ways to place 3 nonattacking bishops on a 3 X 3 board:
XXX XXO XXO XOX 0XO
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}] (* V. Kotesovec, Mar 23 2011 *)
|
|
|
CROSSREFS
| Cf. A187235
Sequence in context: A056786 A006056 A098620 * A079473 A145164 A113078
Adjacent sequences: A002462 A002463 A002464 * A002466 A002467 A002468
|
|
|
KEYWORD
| nonn,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
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 (kotesovec(AT)chello.cz), Mar 09 2011
|
| |
|
|
