Count selections with the same numbers

Question

I have a sequence of numbers [1..9], from which do a selection of 5 elements. Numbers in the selection can be repeated, their order does not matter. It is necessary to calculate:

1. The total quantity of all these selections
2. Quantity of selections in which all numbers are different
3. Quantity of such selections, where two numbers are the same. Also for 3, 4 and 5 equal numbers in the sample

My solving is:

1. I use a formula for counting multisets:
   $$C_{all} = \binom{n}{k} = \frac{(n + k - 1)!}{k!(n-1)!} = \frac{(9 + 5 - 1)!}{5!(9 -1)!} = \frac{13!}{5!8!} = 1287$$

2. $$C_{x1} = \binom{n}{k} = \frac{n!}{k!(n - k)!} = \frac{9!}{5!4!} = 126$$

3. To get a quantity of selections where two numbers are the same, we need to

   • select one first number from [1..n] (where n = 9)
   • select second number from [1..n] (where n = 1)
   • select last three numbers without repetition from [1..n] (where n = n - 1)
   • Result will be multiplying these values $$C_{x2} = \binom{n}{1}\binom{1}{1}\binom{n-1}{k-2} = n \frac{(n-1)!}{(k-2)!(n-k+1)!} = 9\frac{8!}{3!5!}=504$$
     Similarly for 3, 4 and 5 the same numbers:
     $$C_{x3} = n\frac{(n-1)!}{(k-3)!(n-k+2)!}=9\frac{8!}{2!6!}=252$$ $$C_{x4} =72$$ $$C_{x5} = 9$$

Seems it looks good, but I'm confused because $C_{all} \neq C_{x1}+C_{x2}+C_{x3}+C_{x4}+C_{x5}$
Please help me to understand what is wrong with my solution. Thank you

Answer 1

These are correct, and shouldn't add up to $C_{\text{all}}$ because they do not cover all the possibilities. Just like a poker hand, an element of $C_{\text{all}}$ can be:

1. Five distinct elements, like $1,2,3,4,5$: these are counted by $C_{x1}$.
2. One element repeated twice, like $1,2,3,4,4$: these are counted by $C_{x2}$.
3. Two elements repeated twice, like $1, 2, 2, 3, 3$.
4. One element repeated three times, like $1, 2, 3, 3, 3$: these are counted by $C_{x3}$.
5. A full house. I mean, one element repeated three times and another twice, like $1, 1, 1, 2, 2$.
6. One element repeated four times, like $1, 2, 2, 2, 2$; these are counted by $C_{x4}$.
7. One element repeated five times, like $1, 1, 1, 1, 1$; these are counted by $C_{x5}$.

So the cases under 3 and 5 are missing, which is why we don't get $C_{\text{all}}$ back when we take the sum.