160k views
2 votes
Imagine you have N chess pieces and M squares to put them, and M > N. Precisely how many different arrangements are there, if each square can only be occupied by one piece and all the pieces are identical and cannot be distinguished?

User DennisLi
by
3.3k points

1 Answer

2 votes

Let's consider a numerical example.

Let's say we had N = 4 chess pieces that are all pawns and there are M = 9 squares to place them. Label the squares A,B,C,D,E,F,G,H,I

Now because all the pieces are identical, this means that what we can effectively do is select four letters at random from the set {A,B,C,D,E,F,G,H,I} and this basically will instruct where to place the pawns. Whatever letter is selected will have its space filled with a pawn, otherwise, the location remains empty.

For instance, if we select the subset {D,G,A,C} then this means to place pawns at squares D, G, A and C. The order of placement does not matter because again, we can't tell the pawns apart. The letters that are not selected are simply left empty (with no chess piece to occupy the location).

As you can probably guess or see at this point, we will use the nCr combination formula to count how many ways to fill the 9 squares using only 4 pieces.

In this particular example, n = 9 and r = 4. There are...

C(n,r) = C(9,4) = (9!)/(4!*(9-4)!) = (9!)/(4!*5!) = (9*8*7*6*5!)/(4!*5!) = (9*8*7*6)/(4*3*2*1) = 3024/24 = 126 ways to pick four locations for the pawns to be situated. This only applies to a 9 square chessboard (perhaps a 3 by 3).

-----------------------------------

Now onto a more general expression

we have N pieces and M locations, with M > N

Again we turn to a combination formula

Instead of C(n,r), we compute C(M, N), so

C(M, N) = (M!)/(N!*(M-N)!)

The final answer is (M!)/(N!*(M-N)!)

We cannot simplify further because we don't know the values of M or N. Back in the example in the previous section, we had M = 9 and N = 4 which computed to 126.

User Chris Walter
by
3.2k points