2
$\begingroup$

A combinatorics problem:

There are $N$ balls in total, in every round we randomly pick without replacement $n$ balls ($n < N$), after $k$ rounds, what is the probability that all the $N$ balls are picked at least once? After each round, all the picked balls are placed back into the set. Both the order of ball picking in each round and the order of the $k$ rounds do not matter.

  • 0
    First thanks for your help. Yes, please, can you show me some more details?2012-07-16

1 Answers 1

1

You can use the inclusion–exclusion principle to count the number of ways to do the $k$ rounds so that each ball is picked at least once:
Denote by $X$ the set of all $k$-rounds without restrictions and denote by $A_i$ the set of all the $k$-rounds in which $i$-th ball isn't picked. We are looking for $e_0=|X\setminus(A_1\cup...\cup A_N)|$.
Denote $s_0=|X|=\binom{\binom{N}{n}+k-1}{k}, \hspace{10pt} s_j=\sum_{1\leq i_1<... We have $|A_i|=\binom{\binom{N-1}{n}+k-1}{k}, \hspace{10pt} s_1=\binom{N}{1}\binom{\binom{N-1}{n}+k-1}{k}$ Since each time we picked $n$ balls out of $N-1$ (since we excluded the $i$-th), and we did this $k$ times, i.e. we count $k$-multisubsets of a set with $\binom{N-1}{n}$ elements.. To get $s_1$, we need to choose the $i$ and then multiply by the size of $A_i$, since the size of $A_i$ does not depend on $i$.
Similarly, $|A_i\cap A_j|=\binom{\binom{N-2}{n}+k-1}{k}, \hspace{10pt} s_2=\binom{N}{2}\binom{\binom{N-2}{n}+k-1}{k}$ Since we have to exclude two balls now. Continue in the same fashion to get: $s_j=\binom{N}{j}\binom{\binom{N-j}{n}+k-1}{k}$ Be the inclusion–exclusion principle, we have: $e_0=\sum_{j=0}^N (-1)^js_j=\sum_{j=0}^N (-1)^j\binom{N}{j}\binom{\binom{N-j}{n}+k-1}{k}$ Then the probability you were looking for is $\frac{e_0}{|X|}$.

Remark: Observe that the sum runs up to $N$. It is possible that you won't have enough balls at some point, but the binomial coefficient will vanish once $n>N-j$, so there is no need to fix the summation limits.

  • 0
    @Jin Teng: "still a small problem: there are duplications..." - that's the whole point of inclusion–exclusion! if there where no intersections, the whole sum would be just in one step! read more about it in wikipedia (I gave a link to the relevant page in the answer). About my *answers*: the first was the **correct** answer in case when the order of the rounds **is important**. The current is **correct** assuming the order of rounds is **not important**.2012-07-16