Drawing balls with a finite number of replacement

Question

I have to solve this problem:

"Suppose a box contains $18$ balls numbered $1–6$, three balls with each number. When $4$ balls are drawn without replacement, how many outcomes are possible?". (The order does not matter).

I can't find a simple formula for it. I've tried in this way and I don't know if it is right way:

---

A random outcome could or could not have the number $1$. If it has it, the outcome could be $111$ plus a number $2\le n \le 6$, or $11$ plus two numbers or $1$ plus three numbers.

• In the first case we have a total of ${{5}\choose{1}} = 5 $ outcomes.
• In the second case we have a total of ${{5}\choose{2}} + 5 = 15$ outcomes.
• In the last case we have a total of ${{5}\choose{3}} + 5 +5\times 4 = 35 $ outcomes.

Finally, if the outcomes does not have the number 1 we have a total of $ {{5}\choose{4}} + 5\times(4\times 3 + 4) + 5\times 4 + 5 = 110$.

So there are 165 possible outcomes.

---

Is it right? If yes, there is a simpler and much more elegant way to prove it?

Thanks

Answer 1

Method I. (case by case)

Case I: all numbers are distinct. Then there are $\binom 64 =15$.

Case II: one pair, the other two distinct. Then there are $6$ ways to choose the rank of the pair, and $\binom 52=10$ ways to choose the odd two. Thus $6\times 10=60$.

Case III: two pairs. There are $\binom 62=15$.

Case IV: one triple. There are $6$ ways to choose the rank of the triple and $5$ ways to choose the odd man out. Thus $30$.

So: $$15+60+15+30=120$$

Method II. (Stars and Bars)

If you ignore the fact that we only have three of each number, then we are just asking for the number of $6-$tuples of non-negative integers that sum to $4$. Stars and Bars then tells us that the answer would be $\binom {4+6-1}4=\binom 94=126$. Of course, this also counts the six cases in which all the balls show the same number. As that is impossible, we must remove those cases, so the answer would then be $$126-6=120$$

Answer 2

First let's solve it for $24$ balls numbered $1-6$, $4$ balls of each number.

Then to be found is the number of sums $a_1+a_2+a_3+a_4+a_5+a_6=4$ where the $a_i$ are nonnegative integers.

Here $a_i$ corresponds with the number of balls that are drawn and carry number $i$.

With stars and bars we find $\binom{9}{5}=126$ possibilities.

Now we must subtract the number of "possibilities" that actually were not possibilities because $4$ balls having the same number were drawn.

Then we end up with $$\binom95-6=120$$ possibilities.

Answer 3

Just for fun, and because it sometimes helps to see the things we are counting:

1112 1113 1114 1115 1116 1122 1123 1124 1125 1126 1133 1134 
1135 1136 1144 1145 1146 1155 1156 1166 1222 1223 1224 1225 
1226 1233 1234 1235 1236 1244 1245 1246 1255 1256 1266 1333 
1334 1335 1336 1344 1345 1346 1355 1356 1366 1444 1445 1446 
1455 1456 1466 1555 1556 1566 1666 2223 2224 2225 2226 2233 
2234 2235 2236 2244 2245 2246 2255 2256 2266 2333 2334 2335 
2336 2344 2345 2346 2355 2356 2366 2444 2445 2446 2455 2456 
2466 2555 2556 2566 2666 3334 3335 3336 3344 3345 3346 3355 
3356 3366 3444 3445 3446 3455 3456 3466 3555 3556 3566 3666 
4445 4446 4455 4456 4466 4555 4556 4566 4666 5556 5566 5666 

Answer 4

One more way is to use a generating function. Consider

$$F(x) = (1+x+x^2+x^3)(1+x+x^2+x^3)(1+x+x^2+x^3)\cdots(1+x+x^2+x^3) = (1+x+x^2+x^3)^6$$

Looking at the first $(1 + x+ x^2 + x^3)$ term, we can think of the exponent of $x$ as representing the number of "1" balls we choose (i.e. $1=x^0 \rightarrow 0,\ x = x^1\rightarrow 1,\ x^2\rightarrow 2,\ x^3\rightarrow 3$). Correspondingly, the second term represents the number of "2" balls we choose, etc. Since the exponents in each term range from 0 to 3, we are restricted to choosing at most 3 of any type of ball. The answer to your question is then given by the coefficient of $x^4$ (since we are choosing a total of 4 balls) in the expansion of $F(x)$. A computer can easily confirm that the coefficient is 120, as given by the other answers.

This method is nice because it can be generalized to more complicated conditions fairly easily. For example, if you are only interested in the number of drawings where an even number of "1" balls are present, you can simply change the first term to be $(1 + x^2)$ (note the even exponents) and find the coefficient again.