Permutations with conditions - small exclusions from a finite pool

Question

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!

Answer 1

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, we are looking to find out what replaces 18! when we arrange 18 distinguishable, colored beads onto 18 squares, BUT requiring that there are two squares for every color where that color is excluded. Let's imagine drawing a random first bead from a jar and placing it on the empty board. Clearly, since exactly two squares are excluded for whatever color the bead is, this number of ways is 16. We are well on our way to getting 16! which was your guess! Now we pick the second bead from the jar and try to place it. Trouble already!! It's true that, for most placements of our first bead, the second bead will have 15 remaining allowed placements, but what if our first bead went on one of the squares where the second bead would have been excluded anyway due to it's color? In that case, there are STILL 16 places left to put the second bead (we didn't "use up" any with the first bead). Here's the rub: with the color constraints in place, we cannot imagine sequentially placing beads where each of these placements is independent.

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!

Answer 2

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$.