Chess PERMUTATION with 8 squares?

Question

If you like FUN MATH problems then please tough it out and read my long question.  It is a challenge

If you can't solve this then AT LEAST give me an upper bound.  this isn't only for fun.  I kinda need this for a program I'm writing for fun.  lol

In short " How Many Ways Can You Fill EIGHT Squares With Pieces From A Chess Board?  Squares can also be empty."  This isn't strictly a permutation or combination problem.  It's a little of both. 
I know math questions like this need to be worded VERY carefully.  I remember college math classes and how the math question could be interpreted as a permutation or combination problem so I'll be as explicit as I can!!

Imagine 8 squares of a chess board. The order of the pieces will often matter but sometimes not.  Pretend it is impossible to tell pawns of the same color apart.  It is impossible to tell knights of the same color apart.  Impossible to tell rooks of the same color apart, etc. hopefully you get where I'm going with this.  However if you had 8 completely different pieces on the board then it would simply be 8! ways of arranging the pieces. But if you had 8 pieces and two of them were white pawns then that would change the answer because white pawns are indistinguishable from each other.  Also remember that I am counting empty squares as "pieces".  All empty squares are identical.

White & Black each have 8 pawns, 2 rooks, 2 knights, 2 bishops, 1 queen, and 1 king.  The empty square does not belong to a color.
For the sake of keeping things simple follow the next few conditions

1)Like pieces of the same color are identical as far as the math is concerned.  What I mean is that if you put all 8 black pawns on the squares then I don't care how the pawns are arranged or the order they are placed in. The same goes for all white pawns.  Or if you have two white rooks on the board I don't care if the rooks trade places.  There is only 1 way to arrange 8 white pawns.

Given 8 squares.  How many ways could you arrange the pieces if you consider that empty squares are allowed.

Anonymous · Accepted Answer

So you want to know how many permutations there are of the 16 chess pieces, taken 8 at a time, if the same type of pieces of the same color are indistinguishable.  That's equivalent to figuring out the number of different 8 letter strings can be made from the following set of 40 letters:
RRNNBBKQPPPPPPPP
rrnnbbkqpppppppp
xxxxxxxx
That's 13 different letters, BTW.

The x represents your case of an empty square.

The calculation is long and tedious.

First you have to figure out how many combinations there are with limited repeats (like no more than 2 R or 8 p).  Then for each of those, you have to figure out how many permutations there are.

That last part is easy, if you know the make up of the combination.  For n objects, it's n! / k! for every distinct set of k repeated elements. So if you have, say, KKpppQxx, it's 8! / (2! 3! 2!) because you have 8 objects, 2 of one, 3 of another, and 2 of a third.  We see questions like that here all the time:  "How many words can you make out of REFERENCE or MISSISSIPPI?"

You need to do an awful lot of analysis for the first part.  Finding all the combinations of pieces and spaces is quite lengthy.

I don't think there's a easy way to break it down.  You just have to list all the cases individually.  You'd probably want a computer program to do that.

I think the program would start with the piece with the greatest number.
If there are 8 of P, p or x, there is only 1 each, so that gives you 3.

If there are 7 of one of those 3 letters, the other piece can be any of the other 12, and they can each go into any of the 8 spaces.  So that gives you:
3x12x8 = 336.  That's also equal to 3 repeated pieces X 12 other pieces X 8! / 7! permutations using the formula above.

If there are 6 of those, the other pieces can be different in 12C2 ways, or the same 8 ways (there are 4 pieces that are unique--KQkq--and 9 pieces where there are at least 2. That gives you:
3 X 12C2 X 8! / 6!
+
3 X 8 X 8! / (6! 2!)

If you think that's bad, now it gets complicated.

If there are 5 of the same piece, the other 3 can be all the same, two of one and one of another, or 3 different.  You need to determine the number of all of those, how many n-tuples there are in the 8, and then calculate the permutations.

It's so tedious because you have 4 unique pieces, 6 pieces that come in pairs, and 3 pieces that come in octuples.  That gives you 4 + 12 + 24 = 40 pieces.  And you need to find all the ways to partition a set of 8 into subsets that can be filled by those pieces.
8 = 1+1+1+1+1+1+1+1
8 = 1+1+1+1+1+1+2
8 = 1+1+1+1+1+3

You have to be careful with something like
1+1+1+1+2+2.
If you have, say 1 B and 1 n used for some of the 1's, then B and n aren't available for the 2's. In other words, what you are using for the 1's matters.  if the 1's are KQkq, then any 2 of the 9 other types of pieces could fill the 2's.  But if you have KQNB, then the 2's must be 2 of the other 7 types of pieces that have multiples.

8 = 3+3+2
8 = 3+2+2+1

The cases I described above are:
8 = 8
8 = 7+1
8 = 6+2
8 = 6+1+1

Actually, that looks doable without a computer.  Organize it by the largest subset and work your way down to smaller ones.  But I don't want to go through all of that--I'll leave it to you.

KevinM · Answer

Could all the pieces be white kings, or are you limited to the pieces at the start of the game?

If there are no limits, then you have 6 each of black/white pieces (KQRNBP) or empty, for 13 options. So the answer would be:

13^8

Trending News

Chess PERMUTATION with 8 squares?

2 Answers