1
$\begingroup$

I am reaching out for assistance in understanding this issue in combinations / permutations.

The background for this question is for a board game that is being developed, but it can be simplified into the following problem.

There are 6 categories each of which has 4 levels. In the game, players can assign points to a category to gain access to certain abilities. Players have exactly 7 points to distribute into the categories, such that they could choose to do any one of the following combinations.

  • 4 points in one category, 3 points in another
  • 4 points in one category, 2 points in another, and 1 point in a third.
  • 4,1,1,1 (edit, added this in, missed it)
  • 3,3,1
  • 3,2,1,1
  • 3,1,1,1,1
  • 3,2,2 (edit, missed this distribution completely)
  • 2,2,2,1
  • 2,2,1,1,1
  • 2,1,1,1,1,1

For marketing purposes, it is desired to advertise the number of total possible combinations available to the players. To simplify the math, each unique distribution is being handled separately, such that I want to first find out the number of combinations for the (4 in one, 3 in another) type of distribution, and then solve each of the other possible distributions, after which they can all be summed up for a grand total.

The initial problem of 4 in one and 3 in another seems trivial.

4 and 3 picture

The possible combinations are as follows with the level 4 being first and level 3 being second.

{A,B} {A,C} {A,D} {A,E} {A,F} {B,A} {B,C} {B,D} {B,E} {B,F} {C,A} {C,B} {C,D} {C,E} {C,F} {D,A} {D,B} {D,C} {D,E} {D,F} {E,A} {E,B} {E,C} {E,D} {E,F} {F,A} {F,B} {F,C} {F,D} {F,E}

Which totals to 30 different possibilities.

This seemed to imply that permutation formula was appropriate, since P(6,2) = 30.

However, when you look at the case of the distribution of 2,1,1,1,1,1; it is clear that there are in fact only 6 possibilities, and not the 720 which P(6,6) would equal.

one level 2, rest level 1

The six possibilities being when the "2" is in each of the six different columns.

I am struggling to understand how I can correctly apply math to solve the overall problem. Any input would be appreciated.

$\endgroup$
  • 1
    $\begingroup$ Your list of possible combinations has 4,3 and 4,2,1, but not 4,1,1,1. It also omits 3,2,2. Any reason for this? $\endgroup$ – Barry Cipra Jul 5 '17 at 19:22
  • $\begingroup$ I missed putting 4,1,1,1 in the list. Good catch. Also I missed 3,2,2 entirely !!! Thank you very much. $\endgroup$ – mls3590712 Jul 6 '17 at 15:11
1
$\begingroup$

There is a reason why it is once the same as permutation and another time it is different.

When you need to find out how many ways you can distribute your points to two categories, one with 4 points, another with 3, then it is the same as saying: I have 6 possibilities to place the 4 points, and once I choose one, I have 5 remaining possibilities where can I place the 3 points. Then it is truly 6*5.

But when you want to distribute for instance 2 points and 2 points, there is problem. Because when you choose for the "first" two points say category A and then category B, it results in the same distribution as when you choose at first category B and then A, because in both cases categories A and B have two points. This however does not apply for the previous case, because in the first case category A would have 4 points and category B would have 3 points, and switching the order causes the category B to have 4 points and category A 3 points, which are different distributions.

So in order to find out the number of possible distributions, you need to take the number of permutations, and for each number of points that is in your chosen distribution multiple times, divide the number of possibilities with factorial of the count of appearances of this number. For instance distribution 2,2,1,1,1 would be $$\frac {6\cdot 5\cdot 4\cdot 3\cdot 2}{2!\cdot 3!}$$ because there are two numbers "2" and three numbers "1". The same goes for your mentioned case 2,1,1,1,1,1. It is not $P(6,6)=720$, it is in fact $\frac {P(6,6)}{5!}$, because the count of number ones is five. So it just 6.

$\endgroup$
  • $\begingroup$ It does appear that you are correct in your reasoning and in the answer. I am unsure of why dividing by the factorial of the count of appearances for each number does in fact work however. It may be that my math skill is not high enough to understand that reasoning. $\endgroup$ – mls3590712 Jul 5 '17 at 19:12
  • $\begingroup$ It is quite simple, because there will be factorial of possibilities, which result in the same distribution of that value. When there are three "ones", all possibilities of order of choosing {A,B,C}, {A,C,B},{B,A,C},{B,C,A},{C,B,A},{C,A,B} cause that categories A,B,C have one point each. And you want all these six possibilities to be taken into account as one. So divide it with the number of permutations $P(3,3)$, which is $3!$. Or in general case $P(n,n)=n!$. Hope it makes sense a little bit. $\endgroup$ – TStancek Jul 5 '17 at 19:20
  • $\begingroup$ Ahh I see your reasoning now. Thank you for the reply. $\endgroup$ – mls3590712 Jul 5 '17 at 19:22
  • $\begingroup$ You're welcome :) $\endgroup$ – TStancek Jul 5 '17 at 19:24
0
$\begingroup$

For the over-all problem, if I understand it correctly, you want to count the number of solutions in integers of $$x_1+x_2+x_3+x_4+x_5+x_6 = 7$$ subject to $0 \le x_i \le 4$ for $i = 1,2,3,4,5,6$.

More generally, suppose we are interested in the number of solutions, say $a_r$, to $$x_1+x_2+x_3+x_4+x_5+x_6 = r$$ subject to the same constraints. We define the generating function of $a_r$ by $f(x)=\sum_{r=0}^{\infty} a_r x^r$. Then it's fairly easy to see that $$\begin{align} f(x) &= (1+x+x^2+x^3+x^4)^6 \\ &= \left( \frac{1-x^5}{1-x} \right)^6 \\ &= (1-x^5)^6 \cdot (1-x)^{-6} \\ &= \sum_{i=0}^6 (-1)^i \binom{6}{i} x^{5i} \cdot \sum_{j=0}^{\infty} \binom{6+j-1}{j} x^j \end{align}$$ where we have used the binomial theorem twice in the last step. From the last equation we can read off the coefficient of $x^7$: $$a_7 = \binom{6}{0} \binom{12}{7} - \binom{6}{1} \binom{7}{2} = \boxed{666}$$

$\endgroup$
  • $\begingroup$ I can see that your equation does in fact solve the general problem posted. It is not as clear to me as the other solution however. How did you get the first f(x)? You say that it is fairly easy to see, but it is not to me. $\endgroup$ – mls3590712 Jul 6 '17 at 15:12
  • $\begingroup$ @mls3590712 You can find an introduction to generating functions in "Bogart's Combinatorics Notes" : math.dartmouth.edu/~kpbogart/ComboNotes3-20-05.pdf and in many other texts on combinatorics. $\endgroup$ – awkward Jul 7 '17 at 23:47

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.