Combinatorics problem: probability of picking balls of $K$ different colours

Question

There is a box with unlimited number of balls of $C$ different colours. Balls of the same colour are indistinguishable. We are picking balls at random with equal probability for each colour. What is the probability of picking $N$ balls out of the box such that there are $K$ balls of specific different colours?

My idea is as follows:

Select $K$ of $N$ bins - there are $\binom{N}{K}$ ways to do that. Next, we need to place $K$ balls in those places - there are $K!$ ways to do that. After these steps, there are $N - K$ places left empty, and we fill them with balls of any colour - $C^{N - K}$ ways. To obtain the probability we need to divide by total number of sequences - $C^N$. Finally, we have this formula: $\frac{\binom{N}{K} \times K! \times C^{N - K}}{C^N}$.

This formula seems to be wrong. An example: assume $N = 4$, $C = 4$, $K = 3$. I have programmatically calculated that there are 60 such sequences. So, the probability of getting such a sequence is $\frac{60}{4^4} = \frac{15}{64}$. According to the formula, this should be equal to $\frac{\binom{4}{3} \times 3! \times 4^{4 - 3}}{4^4} = \frac{24}{64}$, which is wrong.

Answer 1

There are actually two counting errors in your attempt.

Consider your example, $N = 4$, $C = 4$, $K = 3$. Let the four colors be $\{b,g,r,y\}$ and the three selected colors be $\{b,g,r\}.$ Select $3$ of $4$ bins: $1,2,3.$ Place three balls of the selected colors in those bins: $1\to b,\ 2\to g,\ 3\to r.$ Place a ball of any color in the remaining bin (bin number $4$); suppose we pick the color $b.$ So we have the following colors of balls in the four bins: $$1\to b,\ 2\to g,\ 3\to r,\ 4\to b.$$

Now select a different subset of $3$ of the $4$ bins: $2,3,4.$ Place three balls of the selected colors in those bins: $2\to g,\ 3\to r,\ 4\to b.$ Place a ball of any color in the remaining bin (bin number $1$); suppose we pick the color $b.$ Then we have the following colors of balls in the four bins: $$1\to b,\ 2\to g,\ 3\to r,\ 4\to b.$$

Notice that it's the exact same sequence of colors each time. But we generated the sequences in two different ways, and your verbal description counts them as two sequences.

On the other hand, you count $(N-K)^C$ ways to fill $N-K$ spaces with balls of $C$ different possible colors. The correct number of possibilities for that action is $C^{N-K},$ which comes out to $4$ rather than $1$ in your example. That is, applying your verbal description of the count accurately, you would compute the probability $\frac{96}{4^4} = \frac{24}{4^4}.$

In summary, you start with a method that overcounts, but then you apply a formula incorrectly and thereby undercount one of the steps of your method by a factor of $4,$ and you end up with too low a probability in the end.

---

To do the actual probability, you might start by calculating the probability that a particular color is missing from the $N$ random balls, then find the probability that at least one of your $K$ selected colors is missing. But then (I think) you would have to do an inclusion-exclusion process to avoid excluding the various combinations of two colors, three colors, etc., too many times or too few times.

Answer 2

Seeing there is no constraint on the number of balls in the box, the number of ways to pick N balls with at least K colors is infinite.

Answer 3

You are asking for the number of compositions of $N$ into $C$ parts. $K$ of those parts are required to have at least one item, the remaining $C-K$ can have zero. Add one ball of the $C-K$ colors and ask about compositions of $N+C-K$ into $C$ parts where every part has to be at least $1$. This is a classic stars and bars problem which has ${N+C-K-1 \choose C-1}$ possibilities.

Answer 4

Let me use lower case characters to keep the notation cleaner, and let me replace $K$ with $m$ to keep $k$ as a variable index.
So from a pool of balls with $c$ different colors, $n$ balls extracted, out of which "$m$ balls with specific different colors";
or
from the alphabet $\{1,2,\cdots,c\}$, words of length $n$ containing "$m$ specific different characters".

In the comments, me and others, tried to warn that the expression in ".." is not well specified.
I will try some possible interpretations.

Start with $$ \left( {p_{\,1} + p_{\,2} + \cdots + p_{\,c} } \right) = 1 $$ where in this case $p_1=p_2=\cdots=p_c=1/c$.

Then $$ \bbox[lightyellow] { \begin{array}{l} 1 = \left( {p_{\,1} + p_{\,2} + \cdots + p_{\,c} } \right)^{\,n} = \\ = \sum\limits_{\left\{ {\begin{array}{*{20}c} {0\, \le \,k_{\,j} \, \le \,n} \\ {k_{\,1} + k_{\,2} + \, \cdots + k_{\,c} \, = \,n} \\ \end{array}} \right.\;} {\left( \begin{array}{c} n \\ k_{\,1} ,k_{\,2} ,\, \cdots ,k_{\,c} \\ \end{array} \right)p_{\,1} ^{\,k_{\,1} } p_{\,2} ^{\,k_{\,2} } \cdots p_{\,c} ^{\,k_{\,c} } } \\ \end{array} } \tag{1}$$ where the multinomial coefficient give the number of ways of having $k_1$ repetitions of color 1, $k_2$ of color 2, etc. irrespective of the order, out of $c^n$ total possible extractions (words of length $n$).

Now, if you want that
the $n$ extracted balls be of exactly $m$ specified colors
since the colors are equi-probable we can assume them to be colors $1,2,\cdots,m$, therefore $$ \begin{array}{l} P(m,n)\quad \left| {\;m \le n} \right.\quad = \sum\limits_{\left\{ {\begin{array}{*{20}c} {1\, \le \,k_{\,j} \,\left( { \le \,n} \right)} \\ {k_{\,1} + k_{\,2} + \, \cdots + k_{\,m} \, = \,n} \\ \end{array}} \right.\;} {\frac{{n!}}{{k_{\,1} !k_{\,2} !\, \cdots k_{\,m} !}}p_{\,1} ^{\,k_{\,1} } p_{\,2} ^{\,k_{\,2} } \cdots p_{\,m} ^{\,k_{\,m} } } = \\ = \left( {p_{\,1} p_{\,2} \cdots p_{\,m} } \right)\sum\limits_{\left\{ {\begin{array}{*{20}c} {0\, \le \,l_{\,j} \,\left( { \le \,n - m} \right)} \\ {l_{\,1} + l_{\,2} + \, \cdots + l_{\,m} \, = \,n - m} \\ \end{array}} \right.\;} {\frac{{n!}}{{\left( {l_{\,1} + 1} \right)!\left( {l_{\,2} + 1} \right)!\, \cdots \left( {l_{\,m} + 1} \right)!}} p_{\,1} ^{\,l_{\,1} } p_{\,2} ^{\,l_{\,2} } \cdots p_{\,m} ^{\,l_{\,m} } } = \\ = \frac{{n!}}{{\left( {n - m} \right)!}}\left( {p_{\,1} p_{\,2} \cdots p_{\,m} } \right)\sum\limits_{\left\{ {\begin{array}{*{20}c} {0\, \le \,l_{\,j} \,\left( { \le \,n - m} \right)} \\ {l_{\,1} + l_{\,2} + \, \cdots + l_{\,m} \, = \,n - m} \\ \end{array}} \right.\;} {\frac{1}{{\left( {l_{\,1} + 1} \right)\left( {l_{\,2} + 1} \right)\, \cdots \left( {l_{\,m} + 1} \right)}}\left( \begin{array}{c} n - m \\ l_{\,1} ,l_{\,2} ,\, \cdots ,l_{\,m} \\ \end{array} \right)p_{\,1} ^{\,l_{\,1} } p_{\,2} ^{\,l_{\,2} } \cdots p_{\,m} ^{\,l_{\,m} } } \\ \end{array} $$ which for constant probabilities $p_1=p_2=\cdots=p_m=1/c$ gives $$ \bbox[lightyellow] { P(m,n)\quad \left| {\;m \le n} \right.\quad = \frac{{n!}}{{\left( {n - m} \right)!}}c^{\, - \,n} \sum\limits_{\left\{ {\begin{array}{*{20}c} {0\, \le \,l_{\,j} \,\left( { \le \,n - m} \right)} \\ {l_{\,1} + l_{\,2} + \, \cdots + l_{\,m} \, = \,n - m} \\ \end{array}} \right.\;} {\frac{1}{{\left( {l_{\,1} + 1} \right)\left( {l_{\,2} + 1} \right)\, \cdots \left( {l_{\,m} + 1} \right)}}\left( \begin{array}{c} n - m \\ l_{\,1} ,l_{\,2} ,\, \cdots ,l_{\,m} \\ \end{array} \right)} } \tag{2}$$

We have better to take it from the Cumulative side, i.e.
the $n$ extracted balls consist of up to $m$ specified colors
that is, we admit that some of the wanted colors may be absent. Then $$ \begin{array}{l} Q(m,n) = \sum\limits_{\left\{ {\begin{array}{*{20}c} {0\, \le \,k_{\,j} \,\left( { \le \,n} \right)} \\ {k_{\,1} + k_{\,2} + \, \cdots + k_{\,m} \, = \,n} \\ \end{array}} \right.\;} {\left( \begin{array}{c} n \\ k_{\,1} ,k_{\,2} ,\, \cdots ,k_{\,m} \\ \end{array} \right)p_{\,1} ^{\,k_{\,1} } p_{\,2} ^{\,k_{\,2} } \cdots p_{\,m} ^{\,k_{\,m} } } = \\ = \left( {p_{\,1} + p_{\,2} + \cdots + p_{\,m} } \right)^{\,n} = \left( {\frac{m}{c}} \right)^{\,n} \quad \left| \begin{array}{l} \;\left( {m \le n} \right) \\ \;0 \le m \le c \\ \end{array} \right.\quad \\ \end{array} $$ which is obvious.

After which we can write that $$ Q(m,n) = {1 \over {c^{\,n} }}m^{\,n} = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,m} \right)} { \binom{m}{k} P(k,n)} $$ because there are $\binom{m}{k}$ ways to choose the $k$ colors to be present, out of $m$.

According to [Binomial Inversion theorem] we can invert the above as: $$ P(m,n) = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,m} \right)} {\left( { - 1} \right)^{\,m - k} \binom {m}{k} Q(k,n)} = {1 \over {c^{\,n} }}\sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,m} \right)} {\left( { - 1} \right)^{\,m - k} \binom {m}{k} k^{\,n} } $$ and using this definition of Stirling Numbers of the 2nd kind $$ \left\{ \matrix{ n \cr m \cr} \right\}\quad = {1 \over {m!}}\sum\limits_k {\left( { - 1} \right)^{\,m - k} \binom {m}{k} k^{\,n} } $$

we finally get $$ \bbox[lightyellow] { P(m,n) = {1 \over {c^{\,n} }}m!\left\{ \matrix{n \cr m \cr} \right\} } \tag{3}$$

In fact, the combinatorial interpretation of the Stirling Numbers of 2nd kind gives that
- $\left\{ \matrix{n \cr m \cr} \right\}$ is the number of ways to partition a set of $n$ labelled objects into $m$ nonempty unlabelled subsets;
- $m! \left\{ \matrix{n \cr m \cr} \right\}$ is the number of surjections from a $|n|$-set into a $|m|$-set.

And the last is just another way to express your question, under the considered interpretation.
In fact identity (3) matches with (2).

If instead the interpretation is
the $n$ extracted balls consist of exactly $m$ distinct colors (whichever, out of the $c$ available)
then clearly $$ \bbox[lightyellow] { R(m,n) = {1 \over {c^{\,n} }}\left( \matrix{ c \cr m \cr} \right) m! \left\{ \matrix{ n \cr m \cr} \right\} = {1 \over {c^{\,n} }} \left\{ \matrix{ n \cr m \cr} \right\} c^{\,\underline {\,m\,} } }\tag{4} $$

Now, for your example with $N=n=4\; C=c=4$ and with $K=m=0,1,2,3,4$ the above give $$ \eqalign{ & P(m,4)\quad \left| {\;m = 0 \cdots 4} \right.\quad = {1 \over {4^{\,4} }}\left( {0,\;1,\;14,\;36,\;24} \right) \cr & R(m,4)\quad \left| {\;m = 0 \cdots 4} \right.\quad = {1 \over {4^{\,4} }}\left( {0,\;4,\;84,\;144,\;24} \right) \cr} $$ and in fact $$ \eqalign{ & P(2,4) = \mathop {\left( \matrix{ 4 \cr 1 \cr} \right)}\limits_{\left( {a,b,b,b} \right)} + \mathop {\left( \matrix{ 4 \cr 2 \cr} \right)}\limits_{\left( {a,a,b,b} \right)} + \mathop {\left( \matrix{ 4 \cr 3 \cr} \right)}\limits_{\left( {a,a,a,b} \right)} = 2^{\,4} - 2 = 14 \cr & P(3,4) = \mathop {{{4!} \over {2!}}}\limits_{\left( {a,b,c,a} \right)} + \mathop {{{4!} \over {2!}}}\limits_{\left( {a,b,c,b} \right)} + \mathop {{{4!} \over {2!}}}\limits_{\left( {a,b,c,c} \right)} = 12 \cdot 3 = 36 \cr} $$

I checked (3) and (4) brute force for small values.