Number of ways of choosing seven children from a classroom of 32 (15 boys, 17 girls) with at least 1 boy

Question

I know that the correct solution can be calculated as: $$ \binom {32} {7} - \binom {17}{7}$$

But why is the following solution incorrect? (I am interested in why the following reasoning is incorrect, I realize that the two numbers are not equal): $$ \frac{15 \binom {31} {6}}{2!} $$

The reasoning is that we first pick a boy ($15$ options) and then pick $6$ children out of $31$ remaining in an arbitrary manner. Finally divide by $2!$ since the order of the two groups does not matter.

Answer 1

Let's enumerate boys as $B_1,B_2,...,B_{15}$ and girls as $G_1,G_2,...,G_{17}$. Then in your method, we choose one of them first, say $B_1$. Then for the remaining $6$ children, say $B_2$ is among them and the rest is $G_1,G_2,...,G_5$. But this is as same as choosing $B_2$ first and then choosing other $6$ children as $B_1,G_1,G_2,...,G_5$. Although this is only one example, you can easily see that in your method we are overcounting.

Answer 2

Firstly, dividing by $2!$ is not correct, since the groups are not indistinguishable (the first group has one boy, whereas the second group has $6$ children).

But the numerator is also not correct, since some of the resulting choices are counted exactly once, and some are counted more than once.

For example . . .

If after choosing one boy, the other $6$ choices are girls, the numerator counts that selection exactly once.

On the other hand, if boy #$1$ is chosen first, and boy #$2$ is one of the other $6$ choices, the numerator counts that selection more than once, since you can get the same result by choosing boy #$2$ first, and boy #$1$ as one of the other $6$ choices.

Answer 3

I think the best explanation is to take a group with lets say 4 boys and 3 girls.

With your method, any of those boys could have been the first one to be chosen, and the rest was picked as the group of six kids from the remaining 31 children. Meaning, in your expression $15 {31 \choose 6}$ every group with four boys is counted four times.

The same goes for groups with 5 boys, where every such group is counted five times. Yet you divide that number by two, as if they were counted only twice.

Answer 4

Division by 2 is uncorrect, as an alternative you could calculate it as

$$\binom {15}{1}\binom {17}{6}+\binom {15}{2}\binom {17}{5}+\binom {15}{3}\binom {17}{4}+\binom {15}{4}\binom {17}{3}+\binom {15}{5}\binom {17}{2}+\binom {15}{6}\binom {17}{1}+\binom {15}{7}\binom {17}{0}=\sum_{k=1}^7\binom{15}{k}\binom{17}{7-k}$$

showing also that by counting principle

$$\sum_{k=1}^7\binom{15}{k}\binom{17}{7-k}=\binom{32}{7} - \binom{17}{7}$$

and more in general the Vandermonde's identity

$$\binom{m+n}{r}=\sum_{k=0}^r\binom{m}{k}\binom{n}{r-k}$$

Answer 5

Just for fun here is a way to modify your approach to get the correct answer as suggested by @ArsenBerk in a comment.

Assuming you want to choose the $1$ boy first in $\binom{15}{1}$ ways, then we must break the remaining choices from $31$ students into cases where $k=0,1,\ldots, 6$ remaining boys from $14$ are chosen and $6-k$ girls are chosen from $17$. For each $k$ this may be done in $\binom{14}{k}\binom{17}{6-k}$ ways.

However each of these cases must be divided by the number of equivalent ways that $1$ of the $k+1$ chosen boys can be selected first, there are clearly $\binom{k+1}{1}$ of these so dividing each term by this, summing and multiplying this sum by the initial $\binom{15}{1}$ term gives:

$$\binom{15}{1}\sum_{k=0}^{6}\binom{14}{k}\binom{17}{6-k}/\binom{k+1}{1}\tag{Answer}$$

which you can confirm equals $\binom{32}{7}-\binom{17}{7}$.

In fact by taking $\binom{15}{1}$ inside the summation a little algebraic manipulation shows this is just part of the Vandermonde identity summation presented by @gimusi.