Number of ways to write a tuple of positive integers as a sum of tuples with certain constraints

153 Views Asked by At

There are $N$ boxes into which we put $mn$ balls in $m$ steps, where in each step we insert $n$ balls, each of which goes into a different box. In how many ways can we do this so that box $B_i$, $1 \leq i \leq N$, contains $b_i$ balls? Note we may assume that $\sum_{i=1}^N b_i = mn$, otherwise we can not do this.

This is equivalent to the following problem: In how many ways can we write $(b_1, \ldots, b_N)$ as a (component-wise) sum $$ (b_1, \ldots, b_N) = (a_{1,1}, \ldots, a_{1,N}) + (a_{2,1}, \ldots, a_{2,N}) + \cdots + (a_{m,1}, \ldots, a_{m,N}), $$ where the entries of each of the tuples $t_k$ = $(a_{k,1}, \ldots, a_{k,N})$, $1 \leq k \leq m$, belong to $\{0,1\}$ with precisely $n$ of its entries being $1$?

For example, take $N = 3$ and $m = n = 2$ with $(b_1, b_2, b_3) = (2,1,1)$. Note that \begin{align*} (2,1,1) &= (1,1,0) + (1,0,1)\\ &= (1,0,1) + (1,1,0), \end{align*} so that there are only $2$ ways to write $(2,1,1)$ in such a way.

Thanks!