Given a list of combinations (not permutations), how many do I need to randomly select to ensure $m$ unique items?
For example, given combinations of $3$ letters, if I want $6$ unique items then it could be accomplished with 2 combinations:
ABC
DEF
which gives me 6 unique letters – $ABCDEF$. But given I'm randomly selecting combinations, I could have also selected:
ABC
ABD
ABE
CDE
CDA
CDB
...
Here I've selected $6$ combinations but so far only have 5 unique items: $ABCDE$
So how many combinations would I need to select to ensure 6 unique letters?
I'll be making sure not to select the same combination twice, so there'll no complication of selecting $ABC$ 6 times!
My actual problem involves selecting 20 unique items from groups of 6, but it'd be nice to have a general formula.
(Note I'm not a mathematician just a lowly computer programmer, so simple formulas and layman answers would be appreciated!)
Best Answer
The answer seems to have been given by
@N.F.Taussigin the question comments and formalised by@John C.To guarantee $m$ unique letters from groups of $n$, I need to select $\binom{n-1}{m} + 1$ combinations.
Wikipedia explains this notation to be: $\binom{g}{k} = \frac{g!}{k!(g-k)!}$
So to answer the example with $n=6$ and $m=3$:
$\binom{n-1}{m} = \binom{6-1}{3} = \binom{5}{3} = \frac{5!}{3!(5-3)!} = \frac{5!}{3!\times2!} = \frac{5\times4\times3\times2\times1}{(3\times2\times1)\times(2\times1)} = \frac{5\times4}{2\times1}$
$\binom{n-1}{m} + 1 = \frac{20}{2}+1 = 11$
And for my own real world use with $n=20$ and $m=6$:
$\binom{n-1}{m} = \binom{20-1}{6} = \binom{19}{6} = \frac{19!}{6!(19-6)!} = \frac{19!}{6!\times13!} = \frac{19\times18\times17\times16\times15\times14}{6\times5\times4\times3\times2\times1} = \frac{19,535,040}{720}$
$\binom{n-1}{m} + 1 = 27,132+1 = 27,133$
Which I must admit, is a heck of lot bigger than I expected!