0
$\begingroup$

I have a problem that I have not been able to find a solution to:

There are 9 black fishes, 1 yellow fish and 1 blue fish that are to be given to four (distinct) persons. Each person should have at least one fish. In how many ways can this be done?

$\endgroup$
  • 2
    $\begingroup$ You asked this question before at math.stackexchange.com/questions/541805/…. It's best not to have duplicates, so could you delete one of them? $\endgroup$ – user21820 Feb 6 '14 at 10:55
  • $\begingroup$ @user21820. It is not exactly the same : objects became fishes ! Cheers. $\endgroup$ – Claude Leibovici Feb 6 '14 at 11:23
  • $\begingroup$ @ClaudeLeibovici: If that is sufficient to make them different, then next month we will see fishes become sweets and... $\endgroup$ – user21820 Feb 6 '14 at 11:26
  • $\begingroup$ @user21820. I was just kidding ! I just cannot believe that OP's can do that. Cheers. $\endgroup$ – Claude Leibovici Feb 6 '14 at 11:28
  • $\begingroup$ @ClaudeLeibovici: Haha! It's hard to tell whether people online are joking! $\endgroup$ – user21820 Feb 6 '14 at 11:29
5
$\begingroup$

In special cases such as this, you can find specific properties to split cases. Here the most "constrictive" is the red and yellow objects, and either they both go to one person, or they to different people. In the first case, there are 4 ways to assign the red and yellow objects, and you need to use 3 blue objects to satisfy the other 3 people, and the other 6 can be distributed in any of $\binom{6+3}{3}$ ways (place 3 dividers between 6 objects). In the second case, there are $4 \times 3$ ways to assign the red and yellow objects, and you need 2 blue objects to satisfy the other 2 people, and the remaining 7 can be distributed in any of $\binom{7+3}{3}$ ways.

In general, you'll want to learn how to use the principle of inclusion and exclusion (see Wikipedia). There isn't necessarily a unique way to use it but often a natural way works. For this example, you can just assign all the objects first, ignoring the "at least one" criterion, giving $4^2 \binom{9+3}{3}$ ways, then exclude invalid configurations using inclusion-exclusion. Here the sets can be "configurations where at least $k$ people get no object" where $k$ runs from 1 to 4 (actually 4 is impossible). The result is $\binom{4}{0} 4^2 \binom{9+3}{3} - \binom{4}{1} 3^2 \binom{9+2}{2} + \binom{4}{2} 2^2 \binom{9+1}{1} - \binom{4}{3} 1^2 \binom{9+0}{0}$.

$\endgroup$
  • $\begingroup$ Good answer and good approach. See you for a dinner one of these days. $\endgroup$ – Claude Leibovici Feb 6 '14 at 11:46
2
$\begingroup$

There are $11$ fish, and the partitions of $11$ into $4$ parts are: $$\big\{\{3,3,3,2\},\{4,3,2,2\},\{4,3,3,1\},\{4,4,2,1\},\{5,2,2,2\},\{5,3,2,1\},\{5,4,1,1\},\{6,2,2,1\},\{6,3,1,1\},\{7,2,1,1\},\{8,1,1,1\}\big\}.$$ These are the possible unordered frequencies of fish that people can have.

Given unordered frequencies, the multinomial coefficient counts the number of ordered ways the people can have those fish frequencies. E.g., the unordered frequencies $\{4,3,3,1\}$ give rise to $\binom{4}{1,2,1}=6$ ordered frequences.

Given an ordered frequency, we need to determine who gets the two distinguished fish. If the frequencies contain no $1$s, such as $(3,3,3,2)$, then we can give the colored fish away in $4^2$ ways. If the frequencies contain one $1$, such as $(4,3,3,1)$, then we can give the colored fish away in $4^2-1$ ways (we subtract $1$ to account for the person who receives one fish being assigned both distinguished fish). We account similarly for when two people receive one fish, and when three people receive one fish.

Now we just do the bookkeeping:

$$\begin{array}{c|c|c} \text{partition} & \text{multinomial} & \text{nr fish assign.} \\ \hline \{3,3,3,2\} & \binom{4}{3,1}=4 & 4^2 \\ \{4,3,2,2\} & \binom{4}{2,1,1}=12 & 4^2 \\ \{4,3,3,1\} & \binom{4}{2,1,1}=12 & 4^2-1 \\ \{4,4,2,1\} & \binom{4}{2,1,1}=12 & 4^2-1 \\ \{5,2,2,2\} & \binom{4}{3,1}=4 & 4^2 \\ \{5,3,2,1\} & \binom{4}{1,1,1,1}=24 & 4^2-1 \\ \{5,4,1,1\} & \binom{4}{2,1,1}=12 & 4^2-2 \\ \{6,2,2,1\} & \binom{4}{2,1,1}=12 & 4^2-1 \\ \{6,3,1,1\} & \binom{4}{2,1,1}=12 & 4^2-2 \\ \{7,2,1,1\} & \binom{4}{2,1,1}=12 & 4^2-2 \\ \{8,1,1,1\} & \binom{4}{3,1}=4 & 4^2-3 \\ \end{array}$$

So the total number is $$4(4^2)+12(4^2)+12(4^2-1)+12(4^2-1)+4(4^2)+24(4^2-1)+12(4^2-2)+12(4^2-1)+12(4^2-2)+12(4^2-2)+4(4^2-3)=1776.$$

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