Combinatorics: Probability of Finding a Particular Set from a Random Source I have a problem that I want to solve involving marking neurons in a brain; however, for simplicity I have decided to frame the question in the form of ice cream flavors. A nice piece of background is on this website:
Combinations with Repetition
https://www.mathsisfun.com/combinatorics/combinations-permutations.html
--
I have a source that gives me randomly flavored ice cream scoops. There are five flavors and each scoop has an equal probability of being any of the five flavors. The source scoops out all of the ice cream and then gives me the cup, so order is irrelevant.
Let's assume the five flavors are a, b, c, d, e.
I represent a cup of ice cream by the kinds of scoops inside without order.
I.e. {a, b, c} = {a, c, b} = {b, a, c} = {b, c, a} = {c, a, b} = {c, b, a}
The Question:
Given r ice cream scoops distributed by my random source, what is the probability that I will receive at least three scoops of every flavor? (Therefore, $r \geq 15$.)
If $r=15$ then I must get a cup that looks like this:
{a, a, a, b, b, b, c, c, c, d, d, d, e, e, e}  
However, if $r > 15$ then I can get a cup that looks like this:
{a, a, a, b, b, b, c, c, c, d, d, d, e, e, e, ?, ?, ..., ?} s.t. there are r scoops in the cup and ? is a scoop of any flavor.
--
My Thinking:
The answer in the case of $r=15$ is fairly clear to me. There is only one kind of cup I am looking for so I must divide one by the number of possible combinations with repetition of flavors.
If we look back to mathisfun.com we find that we are using a system with $n = 5$ because there are five flavors. We know order doesn't matter so we use the following equation:
$$ {n + r - 1 \choose r} = {5 + 15 - 1 \choose 15} = \frac{19!}{15!4!} = 3876 $$
Therefore the chance of getting our desired ice cream cup is given by $\frac{1}{3876} \approx 0.000258 $
...
Now given $r>15$ I was thinking about the problem in this way:
The denominator is found in exactly the same way.
$$ {n + r - 1 \choose r} $$
The numerator is a little bit more complicated. I think that we need to consider how many ways there are to pick the extraneous flavors. For example, if we picked 20 brains the numerator would be equal to the number of ways to pick with repetition a cup that looked like this:
{a, a, a, b, b, b, c, c, c, d, d, d, e, e, e, ?, ?, ?, ?, ?}
I think we can determine the number of different ice cream cups by essentially subtracting 15 from r. This would yield the number of different ways to arrange the ? flavors.
$$ {n + ( r- 15) - 1 \choose r} = {n + r - 16 \choose r} $$
My Final Answer
I believe the probability of finding a cup of ice cream s.t.:
{a, a, a, b, b, b, c, c, c, d, d, d, e, e, e, ?, ?, .., ?} with r scoops.
Is given by
$$ \frac{{n + r - 16 \choose r}}{{n + r - 1 \choose r}} $$
What do you think Stack Exchange?
--
I've done a few of the calculations and I am getting these kinds of probabilities. Given r scoops of ice cream, the chance of finding at least 3 scoops of every flavor in your cup looks like:
r = 15 ----> 0.0257998 %
r = 25 ----> 4.21456 %
r = 50 ----> 26.0081 %
r = 75 ----> 42.2879 %
r = 150 ---> 66.0877 %
r = 200 ---> 73.5022 %  
 A: With $m$ flavours, let $F(r,m)$ be the probability of receiving at least $3$ of each flavour in $r$ scoops.  Conditioning on the number of scoops of the last flavour (which is $x$ with probability ${r \choose x} (1/m)^x (1-1/m)^{r-x}$), we get
$$F(r,m) = \sum_{x=3}^r {r \choose x} \dfrac{(m-1)^{r-x}}{m^r}  F(r-x, m-1) $$
Of course, $F(r,m) = 0$ if $r < 3m$, and $F(r,1) = 1$ if $r \ge 3$.
Using this recursion, you can compute $F(r,m)$ for each $(r,m)$.  For example, with $m=5$ I get
$$ \eqalign{F(15, 5) &= \frac{1345344}{244140625} \approx 0.005510529024\cr
F(25, 5) &= \frac{33011014178535624}{59604644775390625}\approx 0.553832915252\cr
F(50, 5) &\approx 0.993574702931\cr
F(75, 5) &\approx 0.999947916777\cr
F(150, 5) &\approx 0.999999999989\cr
F(200, 5) &\approx 0.99999999999999973\cr
}$$
A: As Jmoravitz noted in a comment, your assumption that the combinations with repetition are equiprobable is incompatible with your prescription that each scoop has an equal probability of being any of the five flavours.
Assuming independent uniform selection of the scoop flavours, we can solve the problem using inclusion-exclusion. If $k$ particular flavours are constrained to have less than $3$ scoops, the number of (ordered) flavour tuples is
$$
n_k(r)=\sum_{l_1\ldots l_k=0}^2\binom r{l_1,\ldots,l_k,r-\sum l_i}(5-k)^{r-\sum l_i}\;.
$$
A bit of summation in Sage yields
\begin{align}
n_0(r)&=5^r\;,\\
n_1(r)&=\frac{4^r}{32}\left(r^2+7r+32\right)\;,\\
n_2(r)&=\frac{3^r}{324}\left(r^4+6r^3+47r^2+162r+324\right)\;,\\
n_3(r)&=\frac{2^r}{512}\left(r^6-3r^5+37r^4+19r^3+274r^2+440r+512\right)\;,\\
n_4(r)&=\frac1{16}\left(r^8-20r^7+186r^6-960r^5+2945r^4-5196r^3+4868r^2-1760r+16\right)\;.
\end{align}
Then by inclusion-exclusion there are
$$
\sum_{k=0}^5(-1)^k\binom5kn_k(r)
$$
admissible flavour touples, and dividing by the total number $5^r$ of tuples yields the probability of obtaining an admissible one. The results agree with Robert's.
Here's the Sage code.
