0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Distributing $15$ fruits to $6$ people so that everyone gets between $1$ and $3$ is the same as distributing $9$ fruits to $6$ people so that everyone gets between $0$ and $2$, because you start by giving one fruit to everyone before you worry about distributing the rest. $\endgroup$ – Arthur Jun 10 '15 at 14:42
  • 1
    $\begingroup$ Distinguishable people? Indistinguishable fruit? $\endgroup$ – Henry Jun 10 '15 at 14:43
  • $\begingroup$ @Arthur I still don't understand how can I go from that fact you suggest to solving a general problem of this type. $\endgroup$ – Camilo Celis Guzman Jun 10 '15 at 14:55
  • $\begingroup$ @Henry yes. The objects (fruits) are indistinguishable and the boxes (people) are distinguishable. $\endgroup$ – Camilo Celis Guzman Jun 10 '15 at 14:55
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Thank you very much. Also, I assumed that people are distinguishable because each one is a different person, and the fruits are of the same kind so they are indistinguishable. Am I correctly assuming those facts based on the definitions of indistinguishable or distinguishable objects? $\endgroup$ – Camilo Celis Guzman Jun 10 '15 at 15:07
  • 1
    $\begingroup$ I cannot tell you whether the fruit or people are distinguishable or indistinguishable - that must come from the question. $\endgroup$ – Henry Jun 10 '15 at 15:12
  • 1
    $\begingroup$ For what it is worth, I get the answers $30270240000$, $50$ and $2$; the last two agreeing with Barry (with the $2$ being patterns like $3+3+3+3+2+1$ or $3+3+3+2+2+2$) $\endgroup$ – Henry Jun 10 '15 at 15:21
1
$\begingroup$

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}$$

$\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.