Constrained combinations of balls in jars

Question

Not sure how to solve the following problem. Imagine we have balls of $n$ different colors. There are $m$ balls of each color, so in total we have $nm$ number of balls.

The question is how many combinations are there to place these $nm$ marbles into $k$ jars keeping in mind that:

1. Each jar must have exactly $l$ balls ($l \leq n$ and $m < k$).
2. Each jar should not contain $2$ balls of the same color.

The second constraint makes the problem especially hard for me. I'm not sure where to start. If you could help me or point to the paper/article with similar problem, that would be great.

Thank you in advance!

Answer 1

Finding a closed form seems difficult. Here are some ideas.

Let us consider the case where the jars are numbered.

Consider a $n\times k$ matrix with every entry being either $0$ or $1$. If a ball of $i$ th type is present in $j$ th bin, then $(i,j)$ th entry of the matrix is $1$, else it is zero. Each column may be visualized as a 'bin'. We count the matrices such that

1. every column contains exactly $l$ ones.
2. every row contains at most $m$ ones.

Lets assume that $kl\le mn$ (else such matrices do not exist). The strategy is to count all the matrices with restriction (1) and then subtract the number of matrices that do not conform to restriction (2).

The number of matrices with the restriction (1) is ${\binom{n}{l}}^k$. Let $r_i$ be the row sum of the $1\le i\le n$ th row. We have the equation, $$r_1+r_2+\dots +r_n=kl \quad \quad \quad \quad (A)$$

A solution of (A) where at least one $r_i$ exceeds $m$ (and $r_i\le k \quad \forall 1\le i\le n$) corresponds to some matrices that do not conform with (2). Number of such matrices is $$\sum_{S}\binom{k}{r_1}\binom{k}{r_2}\cdots \binom{k}{r_n}$$ where $S=\{(r_1,r_2,\dots r_n), \sum r_i=kl \text{ AND at least one }r_i \text{ exceeds }m \}$

Hence the number of valid matrices is $${\binom{n}{l}}^k-\sum_{S}\binom{k}{r_1}\binom{k}{r_2}\cdots \binom{k}{r_n}$$ This is far from a closed form as we are iterating over a set of ordered tuples which are the solutions of (A)

---

An upper bound: We associate a solution of (A) where at least one $r_i>m$ with a matrix where in every row, all the ones are stacked up to the left followed by $0$'s (if any). Each solution of (A) where at least one $r_i>m$ corresponds to a unique matrix and vice versa.

Number of such solutions is (by inclusion-exclusion) $$E:=\sum_{i=1}^{\lfloor \frac{kl}{m+1}\rfloor}(-1)^{i+1}\binom{n}{i}\binom{kl-(m+1)i+n-1}{n-1}-\sum_{i=1}^{\lfloor \frac{kl}{k+1}\rfloor}(-1)^{i+1}\binom{n}{i}\binom{kl-(k+1)i+n-1}{n-1}$$

Hence, the upper bound is ${\binom{n}{l}}^k-E$

The upper bound will be exact if $k=m+1$.

---

The case of identical bins seems still more harder.

Answer 2

You need $l \times k=n \times m$, in which case we can be more specific and say $l<n$ and $m<k$, right?

Answer 3

If you have $l$ balls in each jar, no colors repeated, that means each jar contains an $l$ subset of the colors, of which there are $\binom{n}{l}$. As there are enough marbles to do this all around (enough marbles of each color so you won't run out if you place one of each color in each jar), if you take the jars distinguishable (i.e., numbered for example), the number of ways of doing this is: $$ \binom{n}{l}^k $$