In how many different ways can k bishops be placed on an nxn chessboard such that no two bishops attack each other? Please try to respond with a formula and explanation.
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ A quick pointer in the right direction: you want "rook polynomials" (en.wikipedia.org/wiki/Rook_polynomial), calculated separately for black squares and white squares, and then recombined somehow. Also, this is not "combinatorial game theory" as that term is usually understood; I'll remove the tag. $\endgroup$– Michael LugoCommented Feb 7, 2011 at 18:27
-
$\begingroup$ There are many partial enumerations of this function at oeis, e.g., oeis.org/A002465 and oeis.org/A172123 and oeis.org/A172124 and oeis.org/A172127 and oeis.org/A172129 and oeis.org/A176886 but so far as I can see no one enumeration encompassing all of these. $\endgroup$– Gerry MyersonCommented Nov 25 at 3:04
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
0
Call this number $B_k(n)$. For fixed $k$ it is known that $B_k(n)$ has the form $P_k(n)+(-1)^nQ_k(n)$, where $P_k$ and $Q_k$ are polynomials. These polynomials have been computed for (at least) $k\leq 6$. We also have (unsurprisingly) the asymptotic formula $B_k(n)\sim n^{2k}/k!$. For further information see http://www.math.binghamton.edu/zaslav/Tpapers/bishops.slides.20100729.pdf.
Update. I learned from Tom Zaslavsky that an explicit formula for $B_k(n)$ as a triple sum was given by C. E. Arshon in 1936.
answered Feb 7, 2011 at 18:44
$\begingroup$
$\endgroup$
See my book http://problem64.beda.cz/silo/kotesovec_non_attacking_chess_pieces_2013_6ed.pdf , page 234-236. Number of ways to place k non-attacking bishops on an n x n board, (n>1)
$\begingroup$
$\endgroup$
Complementing the answer from V. Kotesovec, the triple sum formula has a simpler expression, given below ($k$ non-attacking bishops placed on a $m$ x $m$ square board):
$\displaystyle B_S(m,k)=\sum_{j=0}^k\sum_{i=0}^j\binom{\lfloor\frac{m}{2}\rfloor}{i}\genfrac\{\}{0pt}{}{m-i}{m-j}\sum_{l=0}^{k-j}\binom{\lceil\frac{m}{2}\rceil}{l}\genfrac\{\}{0pt}{}{m-l}{m-k+j}$
where $\genfrac\{\}{0pt}{}{m}{k}$ are the stirling numbers of the second kind. The manuscript in my blog provides a proof of this result.
Update. Also on arxiv.
