How many ways to distribute $n$ objects into $r$ boxes so that each box have at least $1$ (but no more than $k$) objects?

Question

Example: How many ways are there to distribute 15 fruits to 6 people so that each person has at least 1 fruit but no more than 3?

I understand how to do it when we need to make sure that at least 1 object goes to 1 box. This is the same as the number of surjections from a set of size $n$ to a set of size $r$. However, I am lost on finding the way to restrict the number of maximum number of objects that can be placed at each box.

Answer 1

You can do the calculation with recurrences.

Supposing you have $f$ fruit, $p$ people, $x$ maximum to each person, $y$ minimum to each person, want you want to count $w(f,p,x,y)$ ways of distributing the fruit. You can use:

• for distinguishable people and distinguishable fruit $$w(f,p,x,y)=\sum_{i=y}^{x} {f\choose i}w(f-i,p-1,x,y)$$
• for distinguishable people and indistinguishable fruit $$w(f,p,x,y)=\sum_{i=y}^{x} w(f-i,p-1,x,y)$$
• for indistinguishable people and indistinguishable fruit $$w(f,p,x,y)=\sum_{i=y}^{x} w(f-i,p-1,\max(x,i),y)$$

in each case starting from $w(0,0,x,y)=1$ and $w(f,0,x,y)=0$ when $f\not = 1$.

Answer 2

How many ways are there to distribute 15 fruits to 6 people so that each person has at least 1 fruit but no more than 3?

Well, if everybody gets 1 fruit, that reduces you down to 9 fruit that you need to distribute. So then it's just a matter of how you can distribute those 9 such that nobody gets more than 2 more.

You can't have two or fewer people getting 2 fruit, since there aren't enough people, so that's only two terms you have to add:

$$\begin{split} N &= \sum_{i=0}^4N(\text{i people get 2 fruit}) \\ &= N(\text{3 people get 2}) + N(\text{4 people get 2}) \\ &= \binom{6}{3} + \binom{6}{4}\cdot2 \\ &= 20 + 30 \\ &= 50 \end{split}$$