Permutations with conditions - small exclusions from a finite pool

I am trying to calculate the number of possible set-ups for a game. There are 4 colors of beads (red, blue, green, and clear) and 18 places the beads can be placed. Using 5 beads of each color, you have 4×(18!/3!5!5!5!)+6×(18!/4!4!5!5!) (Roughly 7 Billion: 7.1E9) possible combinations.

BUT

There are two places for each color where that color is excluded. So two spots can only have red, blue, or green, two other spaces can only have blue, green, and clear, etc. Am I correct in thinking that the number of possible permutations is simply calculated by changing the number of possible places from 18 to 16, since there are only 16 places available for each color? That is: 4×(16!/3!5!5!5!)+6×(16!/4!4!5!5!) (Roughly 23 Million: 2.3E7) combinations?

This solution strikes me as too simplistic, but I am unsure how else I can calculate these results.

Thanks!

If we only consider 8 places, these can contain one of the following eleven distributions of colors:

   [2, 2, 2, 2]    2520
[1, 2, 2, 3]    20160
[1, 1, 3, 3]    6720
[0, 0, 3, 5]    672
[0, 2, 3, 3]    6720
[0, 1, 3, 4]    6720
[0, 1, 2, 5]    4032
[0, 2, 2, 4]    5040
[0, 0, 4, 4]    420
[1, 1, 2, 4]    10080
[1, 1, 1, 5]    1344


So for instance one can have two of each color ie. [2, 2, 2, 2] which can happen in $$1\times \binom{8}{2, 2, 2, 2}=\frac{8!}{(2!)^4}=2520\text{ ways}$$ The total number of combinations above is $64428$, which is entirely feasible to analyze using a computer. After excluding each color from two places each, a program tracing the valid combintaions yielded:

   [2, 2, 2, 2]    297
[1, 2, 2, 3]    2256
[1, 1, 3, 3]    720
[0, 0, 3, 5]    48
[0, 2, 3, 3]    696
[0, 1, 3, 4]    624
[0, 1, 2, 5]    288
[0, 2, 2, 4]    480
[0, 0, 4, 4]    36
[1, 1, 2, 4]    984
[1, 1, 1, 5]    96


After this I programmed another part accounting for how many ways the remaining $12$ beads can be placed in the remaining $10$ places. Finally I multiplied and added these figures together and ended up with $758833488$. This figure was based on the following data, which is essentially summarizing the analysis my program carried out:

   8:   [2, 2, 2, 2]    297
10:  [1, 3, 3, 3]    67200
10:  [2, 2, 3, 3]    151200

8:   [1, 2, 2, 3]    2256
10:  [1, 3, 3, 3]    16800
10:  [1, 2, 3, 4]    50400
10:  [2, 2, 3, 3]    75600
10:  [2, 2, 2, 4]    18900
10:  [0, 3, 3, 4]    4200

8:   [1, 1, 3, 3]    720
10:  [0, 2, 4, 4]    6300
10:  [1, 2, 3, 4]    50400
10:  [2, 2, 3, 3]    25200
10:  [2, 2, 2, 4]    37800
10:  [1, 1, 4, 4]    6300

8:   [0, 0, 3, 5]    48
10:  [0, 2, 4, 4]    3150
10:  [0, 0, 5, 5]    252
10:  [0, 1, 4, 5]    2520
10:  [0, 2, 3, 5]    5040


and

   8:   [0, 2, 3, 3]    696
10:  [1, 2, 2, 5]    22680
10:  [0, 2, 3, 5]    5040
10:  [1, 2, 3, 4]    25200
10:  [1, 1, 3, 5]    5040
10:  [2, 2, 3, 3]    25200
10:  [2, 2, 2, 4]    18900

8:   [0, 1, 3, 4]    624
10:  [1, 2, 2, 5]    7560
10:  [0, 2, 4, 4]    3150
10:  [0, 1, 4, 5]    2520
10:  [0, 2, 3, 5]    2520
10:  [1, 2, 3, 4]    25200
10:  [1, 1, 3, 5]    5040
10:  [1, 1, 4, 4]    6300

8:   [0, 1, 2, 5]    288
10:  [0, 3, 3, 4]    8400
10:  [0, 2, 4, 4]    3150
10:  [0, 1, 4, 5]    1260
10:  [0, 2, 3, 5]    5040


and

   8:   [0, 2, 2, 4]    480
10:  [0, 3, 3, 4]    4200
10:  [1, 2, 2, 5]    7560
10:  [0, 2, 3, 5]    5040
10:  [1, 3, 3, 3]    16800
10:  [1, 2, 3, 4]    25200
10:  [1, 1, 3, 5]    10080

8:   [0, 0, 4, 4]    36
10:  [1, 1, 3, 5]    10080
10:  [1, 1, 4, 4]    6300
10:  [0, 0, 5, 5]    252
10:  [0, 1, 4, 5]    5040

8:   [1, 1, 2, 4]    984
10:  [1, 3, 3, 3]    16800
10:  [1, 2, 3, 4]    50400
10:  [1, 1, 4, 4]    6300
10:  [0, 3, 3, 4]    8400
10:  [0, 2, 4, 4]    3150

8:   [1, 1, 1, 5]    96
10:  [0, 3, 3, 4]    12600
10:  [0, 2, 4, 4]    9450


where 8:and 10: respectively stand for partitions of the 8 and 10 places, and the figures are multiplied and added as follows: \begin{align} T&=297\cdot(67200+151200)+2256\cdot(16800+...)+...+96\cdot(12600+9450)\\ &=758833488 \end{align} This is roughly one $10^{\text{th}}$ of your first figure without the exclusions, which BTW is what you get if you use $2520,20160,...,1344$ in stead of $297,2256,...,96$ in the expression for $T$ above. So I believe the answer to be $758833488$.

• Wow - you appear to have calculated the results far faster than I could have. I was barely started. I checked what I had against your results for the number of possible outcomes for the excluded spots only, and found two errors on my part. – rob Nov 16 '15 at 5:39
• As an aside, I have to say that its really impressive how quickly permutations increase or decrease. Here, excluding one color from two spots out of 18 decreases the permutations by a factor of 10. For the main board - a 5x5 grid where 7 beads of each color are randomly placed, you have around 130 trillion possibilities - but if you have 10 spots with 3 beads each, you only have slightly more than 200,000 possibilities - adding 3 rows - 15 spaces - increases the number of possibilities more than a million-fold. – rob Nov 16 '15 at 5:44
• @rob: The figures really grow fast indeed! I feel a bit surprised about my figure $297$ which is odd. I will double check it some time when I have the time. – String Nov 16 '15 at 18:02

Unfortunately your guess, while tempting at first glance, is not quite correct (it is, as you say, a little too simplistic). Before we look at where it goes wrong, it is instructive to first outline the logic that led to the formula you give for the unrestricted case (the one corresponding to any bead being allowed in any square) for those readers who (like me at first) can't intuit where it comes from:

• There are 20 total beads, and 18 total squares, meaning that when the board is full, two beads are left off
• All arrangements are of two types: ones where the two missing beads are of the same color, and one where they are different.
• In the first case, there are 4 ways to choose the color of the missing beads, and the beads remaining on the board belong to groups with multiplicities 5, 5, 5, and 3. In the second case, there are 4*3/2 = 6 ways to choose the colors of the missing beads, and the remaining beads form color groups of multiplicities 5, 5, 4, and 4.
• Using the standard formulas, then, for permutations of objects, groups of which are indistinguishable, we get the final result $N_{boards}=4 \times \frac{18!}{5!5!5!3!} + 6 \times \frac{18!}{5!5!4!4!}$

This is all well and good; now let's tackle the case where certain squares cannot accept a bead of a certain color.

Let's assume that we've chosen our two beads to leave off the board, and we're interested to find the way of arranging the remaining beads subject to these choices. In the original, unrestricted case, this number was just 18! divided by a product-of-factorials that accounts for the indistinguishability of beads of the same color. Let's ignore these latter factors for now; we can assume that, in addition to colors, numbers 1-18 are painted on our beads, making them distinguishable, count the number of ways of arranging these distinguishable beads subject to the color constraints, and then at the end imagine erasing the numbers and putting back in the product-of-factorials factor (hopefully it won't be too hard to convince yourself that this procedure is valid).

So what's the correct way to do the calculation? The answer is that it's a really hard problem. While the fundamental combinatorics is trivial at each stage, there are just a whole lot of interdependent cases to analyze. I won't do that here, but at least you now know that your original guess needs some refinement, and hopefully have some clues as to how to proceed if you choose to (though I would warn that this seems like a ~100 man-hour or more type of project to me... maybe someone else will find a clever solution :)). Please report back if you end up finding your answer!

• Paco Jain, that was a very clear and well-presented explanation. Especially the recap - I wrote a couple versions that were, shall we say, difficult to follow, and eventually just dropped in the formula without comment. I had a feeling that the problem would be more difficult than I had initially thought, and you showed why in terms I, a non-mathematician, could easily follow. Your explanation has given me ideas how to proceed. I'm hoping it won't be 100 hours of work though! – rob Nov 12 '15 at 2:47
• Glad I could help! It was interesting to think about. Also, maybe my estimate of 100 hours was a little pessimistic; it can't hurt to get started trying and see what kind of progress you make :). BTW, is this about a real game? – Paco Jain Nov 12 '15 at 21:06
• Yes, I made a game a few years ago, but life interfered with my plans to market it. Now I am in a position to try again, and I am putting together a Kickstarter ... which is a lot more work than I anticipated! But this permutation calculation is just a sidebar: something to play with while avoiding real work. ;-) You can see photos of the game at the old website: welldesignedgames.com/… . You can see the main board (a 5x5 grid, with roughly 1.3E14 possible configurations) and the "Price Chart", which is what I am trying to figure out here. – rob Nov 13 '15 at 2:45
• It looks really cool! I hope I'll get the chance to play it someday :). – Paco Jain Nov 13 '15 at 21:04