2
$\begingroup$

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?

$\endgroup$

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.