0
$\begingroup$

The question is: in how many different ways can I put $N$ indistinguishable balls into $M$ distinguishable boxes such that each box contains no more than $K$ balls it it?

A more general problem: if $K$ is different for different boxes, $K_i$ for the box $i$, $i=1,...,M$.

I tried to find a way to use "stars and bars" method here, but didn't succeed. I would be grateful if anyone could explain how to solve such a task or provide a reference.

$\endgroup$
2
  • $\begingroup$ I swear I’ve seen this question asked a few times on this site recently $\endgroup$ Jun 11, 2020 at 16:31
  • $\begingroup$ Here I gave a thorough answer to the first problem. In this answer Marc van Leeuwen uses generating functions to deal with both problems. $\endgroup$ Jun 11, 2020 at 16:57

1 Answer 1

0
$\begingroup$

Let $a_j$ defines the number of elements in the $j$-th box, then you want to count the $(a_1,\ldots ,a_M)\in (\mathbb N \cup \{0\}) ^M$ such that $a_j\leqslant K$ for each $j\in\{1,\ldots,M\}$ and $\sum_{j=1}^Ma_j=N$. Then note that this number is just the coefficient of $x^N$ in the expansion of the polynomial $(1+x+x^2+\ldots +x^K)^M$, this is notated as $[x^N](1+x+x^2+\ldots +x^K)^M$.

For the general case it is just $$ [x^N]\prod_{j=1}^M(1+x+x^2+\ldots +x^{K_j}) $$

For a way to handle this kind of problems, at least for simpler cases, take a look here. A good book about counting methods using generating functions is this.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .