If I have a jar with $n$ jelly beans in it, what is the probability that I am missing at least one of the 49 flavors? Assuming each flavor is equally likely to appear. I initially thought it would be just:
$1 - 49 \left( \frac{48}{49} \right)^n$
But then I realized that couldn't be right because some configurations would be overcounted (resulting in a negative probability with a small enough $n$, like 100). I wrote a program to calculate it, so I have approximations of several of the probabilities, but I would like to know how do it with a general formula (ideally with a variable number of flavors as well).
 A: This probability is related to Stirling numbers of the second kind. Specifically, $\lbrace{n\atop 49}\rbrace$, which counts the number of ways to partition the set $\{1, 2, \dots, n\}$ into $49$ nonempty subsets, is $\frac1{49!}$ of the number of ways to assign a color to each jellybean so that all $49$ colors appear. ($\lbrace{n\atop 49}\rbrace$ will tell you what the color classes are, along the lines of "jelly beans 1, 3, 10, and 41 are one color, 2 and 5 are another, ...", but then you have $49!$ ways to pick which color corresponds to each color class.)
There are two main ways to compute $\lbrace{n\atop k}\rbrace$, which correspond to the two main ways to compute your probability.
First, we may use inclusion-exclusion. The probability that you have all $49$ jellybean colors represented is $$1 - 49 \cdot \left(\frac{48}{49}\right)^n +  \binom{49}{2} \cdot \left(\frac{47}{49}\right)^n - \binom{49}{3} \cdot \left(\frac{46}{49}\right)^n + \dots - \binom{49}{48} \cdot \left(\frac{1}{49}\right)^n.$$ Here, each term of the form $\binom{49}{k} \cdot \left(\frac{49-k}{49}\right)^n$ counts the number of ways to choose $k$ colors to exclude, times the probability that each jellybean gets one of the remaining $49-k$ colors.
Second, there's a recursive approach, which makes more sense in the counting formulation of the problem: we'll count the number of ways to choose colors for the jellybeans such that all 49 colors are represented, and divide by $49^n$ at the end.
Let $J(n,r) = \lbrace{n\atop r}\rbrace\cdot r!$ represent the number of ways to color $n$ jellybeans such that $r$ colors are represented. There are two cases:


*

*Either all $r$ colors were already represented when we colored the first $n-1$ jellybeans (which can be done in $J(n-1,r)$ ways). Then we can color the last jellybean arbitrarily, and have $r$ options.

*Or else one of the $r$ colors has been entirely left out. In that case, we have $r$ ways to choose which color that was; there are $J(n-1,r-1)$ to color the first $n-1$ jellybeans leaving out that color but getting all others, and only one way to color the last jellybean: it must be the left-out color.


This gives the recursion $J(n,r) = r\cdot (J(n,r-1) + J(n-1,r-1))$, which we can use to find $J(n,49)$, for a probability of $\frac{J(n,49)}{49^n}$ that all 49 colors were included.
Note that both of these methods count the probability that all the colors will appear, so you want to take the complementary probability to answer the question in the title. I think that the second method is more efficient if you want to know the exact answer (though I'm not positive about this), but the inclusion-exclusion approach will converge to an approximate probability long before you include all the terms.
