# Probability - multinomial partitioning

Question:

Joe is in his hunting blind when he locates $20$ geese, $25$ ducks, $40$ eagles, $10$ cranes, and $5$ flamingos. Joe randomly selects six birds to target, what is the probability that at least one of each species is targeted?

The correct answer is apparently $0.03985$ according to the textbook solutions.

Work so far:

$${20 \choose 1}{25 \choose 1}{40 \choose 1}{10 \choose 1}{5 \choose 1}{95 \choose 1} = 95,000,000$$

So there are $95,000,000$ total ways to select at least one of each species.

$$95,000,000 \left/ {100 \choose 6}\right. = \frac{95,000,000}{1,192,052,400} = 0.0797$$

Notes:

I'm obviously doing something wrong calculating the number of ways to select at least one of each species, as ${100 \choose 6}$ should be the total ways to randomly select 6 of the 100 birds. Obviously my result is the correct answer multiplied by 2, but I'm not sure why. Any help/hints are greatly appreciated.

EDIT: Dividing my 2 should not normally be done in the solution to a problem like this, therefore, I obviously didn't do my calculation correctly. I'd like to see how the calculation would look if I had done it correctly.

-
use \binom{N}{k} –  Seyhmus Güngören Aug 19 '12 at 12:19
@Shaktal: Thank you for the formatting help. –  CODe Aug 19 '12 at 12:26

You need two birds of some species plus one bird from each of the other species. The total number of favorable combinations is

${20 \choose 2}{25 \choose 1}{40 \choose 1}{10 \choose 1}{5 \choose 1} +{20 \choose 1}{25 \choose 2}{40 \choose 1}{10 \choose 1}{5 \choose 1} +{20 \choose 1}{25 \choose 1}{40 \choose 2}{10 \choose 1}{5 \choose 1} +{20 \choose 1}{25 \choose 1}{40 \choose 1}{10 \choose 2}{5 \choose 1} +{20 \choose 1}{25 \choose 1}{40 \choose 1}{10 \choose 1}{5 \choose 2} =47500000.$

-
@CODe I've double checked my calculations. I think my answer is OK. –  Byron Schmuland Aug 19 '12 at 13:24
Strange, I must have done something wrong (again) calculating the combinations out. Apologies and thanks again! I'll remove my first comment to avoid confusion from others who may view this in the future. –  CODe Aug 19 '12 at 13:30

Your computation is good, but you need to divide it by 2. Because each way of selecting at least one of each species contains one specie with 2 birds. And one of those birds can be selected among his own specie and the other among "the last 95". So each pair of such birds is selected twice in your formula.

$$\begin{array}{cccccc} \binom{20}{1}&\binom{25}{1}&\binom{40}{1}&\binom{10}{1}&\binom{5}{1}&\binom{95}{1}\\ g_1&d_1&e_1&c_1&f_1&g_2\\ g_2&d_1&e_1&c_1&f_1&g_1\\ \end{array}$$

For example, the selection of the first two geese, and the first duck, the first eagle, the first crane and the first flamingo is counted twice in your formula..

So the right result is

$$\frac{\binom{20}{1}\binom{25}{1}\binom{40}{1}\binom{10}{1}\binom{5}{1}\binom{95}{1}}{\binom{2}{1}\binom{100}{6}}\\$$

-
Why does it contain two birds when I'm only choosing one of each species? I'm not following your logic. I select one of each species and then select one from the leftover 95 birds... what do I need to change in my computation to make it correct? –  CODe Aug 19 '12 at 12:51
I add some explanation, is it clear now ? The leftover has a specie too, of course, that's why... –  Xoff Aug 19 '12 at 12:54
Sorry, still not getting it. What do I need to change in my computation to make it correct? That may help me to understand the logic behind my error. –  CODe Aug 19 '12 at 12:55
Consider any selection with your formula. If you switch the last selected bird (among the 95) with the one of the same specie you selected before, you obtain the same selection, but you count this permutation as a different one. So you just need to divide by 2 your final result. –  Xoff Aug 19 '12 at 12:58
Dividing the whole thing by 2 isn't telling me anything I don't already know, I know my calculation is off by 1/2. I'm trying to figure out the error in my logic that led to me having to divide by 2. Dividing by 2 should not be necessary in a problem like this, you should be able to do the calculation and get a correct answer for the number of ways to select at least one of each species. –  CODe Aug 19 '12 at 13:06

This is just a slight restatement of the explanation by Xoff, in which Xoff explains in detail why one should divide your count by $2$. Let us cut down the numbers a lot. We have $20$ geese, and $25$ ducks, that's all, and we want to choose $3$ birds, at least one of each species.

The analogue of your calculation yields $\binom{20}{1}\binom{25}{1}\binom{43}{1}$. Let us see what this counts.

The term $\binom{20}{1}\binom{25}{1}$ counts the number of "bags" that contain a bird of each species. So $\binom{20}{1}\binom{25}{1}\binom{43}{1}$ counts correctly the number of ordered pairs $(x,y)$, where $x$ is a two-bird bag with one of each species, and $y$ is a single bird.

There is no reason to think that the number of such ordered pairs is the same as the number of bags of three, with at least one of each species. And it isn't. But the number of ordered pairs happens to be connected in a simple way with the number of bags of three.

Note that every bag of $3$ birds, with at least one of each species, gives rise to exactly $2$ ordered pairs $(x,y)$ of the kind discussed above. For consider the bag that contains $g_1$ (Goose $1$), $g_7$, and $d_4$. There are two ordered pairs $(x,y)$ that result in this bag of three. They are $x=\{g_1,d_4\}$, $y=g_7$, and $x=\{g_7,d_4\}$, $y=g_1$. In general, the product $\binom{20}{1}\binom{25}{1}\binom{43}{1}$ counts each bag of three, with at least one of each species, twice. So you need to divide $\binom{20}{1}\binom{25}{1}\binom{43}{1}$ by $2$ to get the correct count of bags of three, with each species represented.

The same argument applies to your more complicated situation with five species. Again we get that each bag of $6$ has been counted exactly twice. This kind of multiple counting can get treacherous in more complicated situations. Often the "multiplication factor" is not constant, and deliberate "overcount-and-adjust" breaks down.

-
+1 for explaining Xoff's answer a bit more clearly. –  CODe Aug 20 '12 at 6:57