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.
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
9
4
|
|
|||
|
|
19
|
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. |
|||
|
