Given $n = a_1 + \cdots+ a_k$ where $a_i$ is the number of (indistinguishable) balls with an $i$ on them.

Question

Given $n = a_1 + \cdots+a_k$ where $a_i$ is the number of (indistinguishable) balls with an $i$ on them. Then how many ways can you uniquely pick $m$ balls from $n$?

I have just been pondering this question. I have not come across this is any texts before, and I assume this is probably because a formula would be messy! I would be interested to hear if anyone has come across a solution before though!

Answer 1

I don't think there is an easy answer.

If you define $f(m)$ to be your value, then the generating function will be:

$$\sum_{m=0}^n f(m)x^m = \prod_{i=1}^k \frac{x^{a_i+1}-1}{x-1}$$

If you let $F(m;a_1,a_2,\dots,a_k)$ be your count for fixed $k$, then I believe the generating function is:

$$\sum_{m,a_1,a_2,\dots,a_k} F(m;a_1,\dots,a_k) y^mx_1^{a_1}\dots x_k^{a_k} = \prod_{i=1}^k \frac{1}{(1-x_iy)(1-x_i)}$$

I don't see how that is useful for calculating $F$, however.

Answer 2

There doesn't seem to be a closed formula.

However, given concrete $a_i$'s and $m$, it's possible to solve it in at least two ways.

---

Dynamic programming (or call it recursion if you like, since no optimization is involved).

Let $f[i,j]$ be the number of ways to choose $j$ balls from the first $i$ kinds of balls (i.e. using only balls with number $1,...,i$), $1\le i\le k$, $0\le j\le m$.

Then $f[i,j]=\sum_{p=0}^{\min(a_i,j)}f[i-1,j-p]$, with some simple boundary conditions. This results in an algorithm of $\mathcal{O}(m n k)$.

---

The other is to use the Inclusion–exclusion principle to calculate the intersection of $k$ sets. See any textbooks on combinatorics for details.