Constrained combinations of marbles in jars

Question

I'm fairly new to combinations so I apologize upfront that I don't even know where to start with this one. My problem is of the form: If I have $N$ marbles, and $M$ jars that can only fit a max of $Z$ marbles each, for how many combinations may I distribute all marbles amongst the jars? (Assume $N$ is between $1$ and $M \cdot Z$, such that you are guaranteed to have at least one jar to place a marble.) Can someone please provide some insight, or point me in the right direction?

Answer 1

Generating Function Approach

The coefficient of $x^N$ in $$ \left(1+x+x^2+\cdots+x^Z\right)^M=\left(\frac{1-x^{Z+1}}{1-x}\right)^M $$ is the number of ways to pick $x^0$, $x^1$, $x^2$, ... , $x^Z$ from each of the $M$ factors so that the exponents sum to $N$. This corresponds to putting $N$ marbles into $M$ bins with a maximum of $Z$ marbles per bin.

Thus, the number of ways to put $N$ marbles into $M$ bins with no more than $Z$ marbles per bin is $$ \left[x^N\right]\left(\frac{1-x^{Z+1}}{1-x}\right)^M $$ Applying the Binomial Theorem, we get $$ \begin{align} \left[x^N\right]\left(\frac{1-x^{Z+1}}{1-x}\right)^M &=\left[x^N\right]\left[\sum_{k=0}^M(-1)^k\binom{M}{k}x^{k(Z+1)}\sum_{j=0}^\infty(-1)^j\binom{-M}{j}x^j\right]\\ &=\bbox[5px,border:2px solid #C0A000]{\sum_{k=0}^M(-1)^k\binom{M}{k}\binom{N+M-1-k(Z+1)}{N-k(Z+1)}} \end{align} $$ Note that when $Z\ge N$, so that all the marbles can be fit into any jar, the formula above reduces to $\binom{N+M-1}{N}$, which is the same number as given by the "stars and bars" method.

Answer 2

You need to use the multinomial coefficient:

$$\frac{N!}{k_1!k_2! \ldots k_M!},$$

where $k_i$ denotes the number of marbles put in the $i$-th jar. The number you are looking for is:

$$\begin{array}{c} \displaystyle\displaystyle\sum_{k_1 = 0}^Z \sum_{k_2 = 0}^Z \ldots \sum_{k_M = 0}^Z\\ \small{\text{s.t.}~k_1 + k_2 + \ldots k_M = N}\end{array} \frac{N!}{k_1!k_2! \ldots k_M!},$$

with the assumption that each combination of $k_1$, $k_2, \ldots, k_M$ sums up to $N$