3
$\begingroup$

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!

$\endgroup$
0
1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ – rob Nov 16 '15 at 5:39
  • $\begingroup$ 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. $\endgroup$ – rob Nov 16 '15 at 5:44
  • $\begingroup$ @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. $\endgroup$ – String Nov 16 '15 at 18:02
2
$\begingroup$

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!

$\endgroup$
4
  • $\begingroup$ 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! $\endgroup$ – rob Nov 12 '15 at 2:47
  • $\begingroup$ 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? $\endgroup$ – Paco Jain Nov 12 '15 at 21:06
  • $\begingroup$ 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. $\endgroup$ – rob Nov 13 '15 at 2:45
  • $\begingroup$ It looks really cool! I hope I'll get the chance to play it someday :). $\endgroup$ – Paco Jain Nov 13 '15 at 21:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.