Here's a question from my probability textbook:
All the combinations $n$ together of $mn$ letters being written down, a person selects $m$ of these combinations at random. Find the chance that the resulting combination will contain all the $mn$ letters.
I ended up getting$${{\underbrace{\binom{mn}{n,n,\ldots, n}}_{m\text{ }n\text{'s}}\over{m!}}\over{\binom{\binom{mn}{n}}{m}}} = {{(mn)! – m!n!(mn – n)!}\over{(n!)^m}}.$$Is this correct? If not, where did I go wrong and how can I fix my answer into a correct one?
Best Answer
I like to consider a simplified example to solve these types of probability problems. Let $m=3$ and $n=2$ so $mn=6$ and assign six letters as { A,B,C,D,E,F }. The denominator of the solution requires the total number of combinations of the $n=2$-letter pairs, from which the $m=3$ draws are made. If you consider AB to be the same as BA then there are $6 \choose {2} $$ = \frac{6!}{4!2!} = $$\frac{6\times5}2 = 15$ combinations of two letters. If you consider AB and BA to be two different combinations then there are $6\times5 = 30$. For simplicity and following $ n \choose r $ convention I will use the first case. For a reasonability check, the pairs can be listed as {AB, AC, AD, ... BC, BD, ..., EF} and it can further be noted for $k = 5 = (mn-1)$ that this list contains 5 + 4 + 3 + 2 + 1 = $\frac{(k+1) \times k}{2}$ = $\frac{6 \times 5}2 = 15$ pairs. Next we want to pick $m=3$ of the $15$ pairs at random, which for example might be AB, BC, DF; and $15 \choose {3}$ = $ \frac{15 \times 14 \times 13}{3 \times2}$ $= 455$. Out of these selections of three pairs, we want to know how many sets will not repeat any of the $6$ letters, so in our example if we have chosen AB then CB can not be in the same group. So, we want to know how many ways we can partition all $mn=6$ letters into distinct pairs, given that our groupings are in pairs for $n=2$. For non-distinct pairings, this is going to be $6 \choose {2,2,2}$ = $6 \choose {2}$$4 \choose {2}$$2 \choose {2}$ $ = \frac {6 \times 5 \times 4 \times 3 \times 2}{ 2 \times 2 \times 2} = \frac{6!}{2^3}$ = 90. Then divide by $3!$ to account for permutations of the three pairs and $\frac{90}{3 \times 2} = 15$. A reasonability check can be done where the possible three pairs are listed as {AB, CD, EF}, {AB, CE, DF}, {AB, CD, DE} ... {AF, BE, CD}. Finally $ \frac{15}{455} = \frac{3}{91} = 3.3$%. Now this solution can be extended to the general case for $m, n$. First for the denominator let J = $mn \choose n$ = $\frac{(mn)!}{(mn-n)!n!}$ then $J \choose m$ = $\frac{J!}{(J-m)!m!}$ and in the numerator $\frac{ {mn \choose n} {(mn-n) \choose n} {(mn-2n) \choose n} ... {n \choose n}}{m!}$ = $ \frac {(mn)!}{(n!)^m(m!)} $ and together this is $ \frac {(mn)!}{(n!)^mm!} $ $\times $ $\frac{(J-m)!m!}{J!}$ = $ \frac {(J-m)! \times (mn)! }{J!(n!)^m} $