5
$\begingroup$

Suppose that you have a set of 12 colored balls, two each of six different colors $C_{1}$ through $C_{6}$. Find the number of six-ball combinations if balls of the same color are considered identical.

Using the Inclusion-Exclusion Principle and $\binom{n}{m}_{R}=\binom{n+m-1}{m}$ where m is the number of balls and n is the number of boxes (or in this case the length of the combination), I should he able to solve this problem.

However, I have not idea how to solving this problems. Can someone please help me? Thank you

$\endgroup$
  • $\begingroup$ must you use those two methods ? or also others? $\endgroup$ – G Cab Aug 2 '17 at 10:48
  • $\begingroup$ Yes I do. They need to be used together. @GCab $\endgroup$ – Nixie777 Aug 2 '17 at 11:23
  • $\begingroup$ then true blue anil already gave you an answer in that direction $\endgroup$ – G Cab Aug 2 '17 at 15:57
4
$\begingroup$

To solve it in the particular way specified, reverse the problem.

Imagine that the balls are identical,
and that that they magically acquire the color of $6$ distinctly colored boxes in which they are put,
none of which can hold more than $2$ balls, which translates to solving over non-negative integers, $x_1+x_2+.....+ x_6 = 6,\;\; 0\le x_i\le2$

To take care of the upper limit, we exclude inadmissible combos by putting $3$ in one or more boxes and apply inclusion-exclusion, thus

$\binom{11}5 - \binom61\binom{8}5 + \binom62\binom{5}5 = 141$

$\endgroup$
4
$\begingroup$

Generating Function Approach $$ \begin{align} \left[x^6\right]\left(1+x+x^2\right)^6 &=\left[x^6\right]\left(\frac{1-x^3}{1-x}\right)^6\\ &=\left[x^6\right]\sum_{k=0}^6(-1)^k\binom{6}{k}x^{3k}\sum_{j=0}^\infty(-1)^j\binom{-6}{j}x^j\\ &=\sum_{k=0}^2(-1)^k\binom{6}{k}(-1)^{6-3k}\binom{-6}{6-3k}\\ &=\sum_{k=0}^2(-1)^k\binom{6}{k}\binom{11-3k}{5}\\ &=\binom{6}{0}\binom{11}{5}-\binom{6}{1}\binom{8}{5}+\binom{6}{2}\binom{5}{5}\\[9pt] &=462-336+15\\[15pt] &=141 \end{align} $$


Casing on the Number of Pairs

Choose $k$ colors to have two balls of each of those colors and one of the rest $$ \begin{align} \sum_{k=0}^3\overbrace{\ \ \ \binom{6}{k}\ \ \ }^{\substack{\text{number of}\\\text{ways to choose}\\\text{paired colors}}}\overbrace{\binom{6-k}{6-2k}}^{\substack{\text{number of}\\\text{ways to choose}\\\text{singleton colors}}} &=\binom{6}{0}\binom{6}{6}+\binom{6}{1}\binom{5}{4}+\binom{6}{2}\binom{4}{2}+\binom{6}{3}\binom{3}{0}\\ &=1+30+90+20\\[9pt] &=141 \end{align} $$

$\endgroup$
3
$\begingroup$

In problems like this I find it a little easier to break it down into multiple cases:

  1. All the balls are different colours.
  2. One pair of chosen balls are the same colour.
  3. Two pairs of chosen balls are the same colour.
  4. Three pairs of chosen balls are the same colour.

How many combinations are there in case 1? Well, just one. There are six colours, and balls of the same colour are considered identical.

How many combinations are there in case 2? Say that $C_1$ is the colour ball which is paired. Then there are 4 balls, all of different colours, remaining. That means there's one colour missing. There are 5 ways for that to happen, because there are 5 colours left when $C_1$ is the colour of the ball which is paired. This should be a clue as to how many total combinations there are for case two, given that I've only considered here the possibility of $C_1$ being the colour of the paired ball.

In case three, we use similar logic. Say that $C_1$ and $C_2$ are the colours which are paired. There are two balls of different colours remaining, and two colours missing. There's only a limited number of ways to have two colours remaining. You should be able to do that. Remember again that this is only the case where $C_1$ and $C_2$ are the colours of the paired balls.

The last case is where three pairs are the same colour. There are a number of ways which that can happen, and it's the same as the number of ways of picking 3 objects from 6.

$\endgroup$
3
$\begingroup$

Begin with $6$ different balls, and replace $j\in\{0,1,2,3\}$ of them by balls of $j$ different other colors. This can be done in $$\sum_{j=0}^3{6\choose j}{6-j\choose j}=141$$ ways.

$\endgroup$

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.