Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If I have a checkers board (8x8) and 16 black pieces , 16 white ones (this isn't the usual checkers).

Assume that these pieces can be placed anywhere on the board.

How can I calculate the number of ways the board can be laid out?

(it's trivial to say that each position may be a white piece , black piece or empty, but I have an upper bound on the number of checker pieces).

edit:

Considering the upper bound (ie 16 or less black/white piece) how does the number of ways change?

Now, assume that pieces can upgrade to kings. Needless to say, when you gain a king, you lose a normal piece, which preserves the the max 16 pieces rule.

How can I calculate the number of ways the board can be laid out considering the kings?

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

$${64\choose16}{48\choose16}$$ Multiply by $2^{32}$ to get the answer when there can be kings.

If you have at most 16 black and at most 16 white, you get $$\sum_{m,n=0}^{16}{64\choose m}{48\choose n}$$ which is $$\left(\sum_0^{16}{64\choose m}\right)\left(\sum_0^{16}{48\choose n}\right)$$

share|improve this answer
    
Thanks. I get the first part. But I don't see how * 2^32 solves the kings problem? What about the upper bound problem? –  Mazyod Sep 17 '12 at 5:32
1  
Given the first part, on each of the 32 occupied squares, you can choose to replace the piece with a king, or not. I'll edit in something about the "upper bound" problem, unless someone beats me to it. –  Gerry Myerson Sep 17 '12 at 5:35
add comment

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.