Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Michael Lugo Feb 7 '11 at 18:27

1 Answer 1

up vote 19 down vote accepted

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.

share|improve this answer
    
Special thanks for the link. –  fnasim Feb 7 '11 at 19:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.