We have $m$ people and a set of $n$ elements. Each person chooses $l$ elements out of $n$, independently from each other. What is the probability that each element is chosen at least $k$ times?

Let $X_1, \dots X_n$ be the random variables counting how many times each element is chosen. I want to determine the density $\mathbb{P}(X_1=k_1, \dots X_n=k_n)$, then I can sum over all values greater than $k$ to determine the probability.

I am having a hard time trying to compute the combinations. The denominator of the probability is easy, because it's all possible combinations of $l$ elements out of $n$, repeated $m$ times, due to independence: $$\binom{n}{l}^m$$

But how can I determine only those combinations, such that the elements are chosen exactly $k_1, \dots k_n$ times? I don't know if a simple formula exists for this.

Example: Let's say we have $m=10$ people voting for $n=5$ parties. Each person is expressing $l=2$ votes (more precisely, they randomly choose $2$ different parties). What is the probability that each party gets at least $k=1$ vote?

Addendum: I am not sure if it helps, but I also thought of formalizing this problem in a different way. Basically it's a random $m \times n$ binary matrix, with each row summing to $l$ and each column summing to a number $\geq k$. I need to count all the possible matrices.

  • $\begingroup$ The example should be doable using brute force (case-by-case), and using a few tricks here and there to cut down on computation, although even then it's still very long and tedious. I don't see another way. $\endgroup$ Commented Feb 12 at 11:26

1 Answer 1


ۤFor $\color{blue}{l=1}$, the problem is equivalent to count the ways that $m$ distinct things can be distributed in $n$ distinct urns such that each urn has at least $k$ elements. It is given by


where $S_k$ denotes the $k$-associated Stirling number of the second kind; for $k=1$ it is the Stirling number of the second kind (see Variants section in the link).

The probability is then given by


The same idea can be used to find an upper bound for the number as follows:

$$n!S_k(m \times l,n)$$

in which each of the $n$ items can be selected multiple times (each person can give more than one vote to each party). Hence, the probability is less than

$$\frac{n!S_k(m \times l,n)}{\binom{n}{l}^m}.$$

The above results show that the problem for arbitrary $\color{blue}{l \ge 1}$ should be very difficult. I checked different recurrences, but could not find low-dimensional recurrences. Finally I reached to the following one, which seems to be more reasonable when $n$ is not a large number (other similar ones can be developed, but they seem to be less useful).

Let $A_{m,l}(k_1,...,k_n)$ denote the number of ways that $m$ persons can select $l$ items from $n$ distinct items such that each item $i$ is selected at least $k_i$ times by different persons. Then, we have the recurrence

$$A_{\color{blue}{m},l}(k_1,...,k_n)=\sum_{i_1+ \cdots +i_n=l}A_{\color{blue}{m-1},l}([k_1-i_1]^+,...,[k_n-i_n]^+)$$

where $[x]^+=\max(x,0)$, and

$$A_{m,l}(0,...,0)=\binom{n}{l}^m.$$ The recurrence is obtained by assuming that person 1 first selects his/her $l$ items, and the other persons select their items next.

The solution to the OP is $A_{m,l}(k,...,k)$, which can be obtained from the above recurrence.

To see how much the solution can be complex, the explicit formulas for two simple cases $k_2=0,k_3=0,\cdots, k_n=0$ and $k_3=0,k_4=0,\cdots, k_n=0$ are given below:

$$ A_{m,l}(k_1,0,...,0)=\sum_{i=k_1}^{n} \binom{n}{i} \binom{n}{l-1}^i\binom{n}{l}^{n-i}, n\ge \, k_1$$ $$A_{m,l}(k_1,k_2,0,...,0)=\\ \sum_{i=k_1}^{n}\sum_{j=k_2}^{n} \sum_{j_1} \binom{n}{i}\binom{i}{j_1}\binom{n-i}{j-j_1} \binom{n}{l-2}^{j_1}\binom{n}{l-1}^{i-j_1+j-j_1}\binom{n}{l}^{n-(i+j-j_1)}, \, n\ge k_1+k_2.$$


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .