Distribution of identical objects among people

Question

How to find the number of ways in which n identical objects can be divided among r persons where each person gets a maximum of k objects?

Answer 1

Use generating functions. The number of objects each one of the persons gets is represented by:

$\begin{align} 1 + z + z^2 + \dotsb + z^k = \frac{1 - z^{k + 1}}{1 - z} \end{align}$

The ways of distributing among $r$ persons is:

$\begin{align} \left(\frac{1 - z^{k + 1}}{1 - z}\right)^r &= \frac{(1 - z^{k + 1})^r}{(1 - z)^r} \\ &= \sum_{0 \le i \le r} \binom{r}{i} z^{(k + 1) i} \cdot \sum_{i \ge 0} (-1)^i \binom{-r}{i} z^i \\ &= \sum_{0 \le i \le r} \binom{r}{i} z^{(k + 1) i} \cdot \sum_{i \ge 0} \binom{i + r - 1}{r - 1} z^i \end{align}$

Out of this you want the coefficient of $z^n$, i.e.,

$\begin{align} [z^n] \sum_{0 \le i \le r} \binom{r}{i} z^{(k + 1) i} \cdot \sum_{j \ge 0} \binom{j + r - 1}{r - 1} z^j &= \sum_{\substack{0 \le i \le r \\ (k + 1) i \le n}} \binom{r}{i} [z^{n - (k + 1)i}] \sum_{j \ge 0} \binom{j - r - 1}{r - 1} z^j \\ &= \sum_{\substack{0 \le i \le r \\ (k + 1) i \le n}} \binom{r}{i} \binom{n - (k + 1) i - r - 1}{r - 1} z^j \end{align}$

No, this can't be simplified further.

Answer 2

Another way to do it (which I personally find simpler) is using stars and bars

I am assuming that the only restriction is on the maximum, it is possible to give zero objects to one or more persons.

If there are no restrictions on the maximum, the answer would simply be ${n+r-1\choose r-1}$

but due to the restriction of a maximum of k to any person, we need to apply inclusion-exclusion to subtract forbidden combos, so

$$W(n,r) = \sum_{j=0}^J (-1)^j{r\choose j}{n+r-1-(k+1)j\choose r-1}, J = \lfloor\frac{n}{k+1}\rfloor$$