19
$\begingroup$

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.

$\endgroup$
  • 13
    $\begingroup$ @user477343 That is like saying Pythagoras theorem holds because it can be proven. The questioner is asking for insight. $\endgroup$ – SK19 Feb 15 '18 at 10:05
  • $\begingroup$ @SK19 Well I guess the OP could have been a bit more clearer, because I thought the OP was asking, why isn't this equal to that? or something of that sort. I was ready to explain why they were not equal, but fortunately you commented. $\endgroup$ – Feeds Feb 15 '18 at 10:08
  • 3
    $\begingroup$ @user477343 However, he was asking "But why is the following incorrect?" and gives a reasoning why he assumes that it should be correct. Pretty clear to me. $\endgroup$ – SK19 Feb 15 '18 at 10:10
  • 3
    $\begingroup$ I edited the question to clear any confusion. $\endgroup$ – pseudomarvin Feb 15 '18 at 10:10
15
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So is there any way to save that expression with a correct denominator or would that be too difficult? $\endgroup$ – pseudomarvin Feb 15 '18 at 10:26
  • 2
    $\begingroup$ It would be difficult because you will need to find how many repetitions for different cases where there are different number of boys. Then for each case, you can divide the total number of cases by number of repetitions. $\endgroup$ – ArsenBerk Feb 15 '18 at 10:38
11
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ This is a nice algebraic derivation, but I think some of the other answers provide a better intuitive explanation. $\endgroup$ – Davislor Feb 15 '18 at 21:43
  • 1
    $\begingroup$ @Davislor I agree with you, indeed, since other answers explaind very well where the mistake was, my intention was just to give an alternative (and correct) way to derive the result which gives also a way to prove the given identity. $\endgroup$ – gimusi Feb 15 '18 at 21:47
  • 1
    $\begingroup$ I found this answer very insightful. I did not realize before reading it that the "brute force approach" described in the first equation and the "clever one" in the second were related in this way. $\endgroup$ – pseudomarvin Feb 16 '18 at 15:27
  • 1
    $\begingroup$ @pseudomarvin I'm verry happy that you have found it very insightful and helpful! Thanks $\endgroup$ – gimusi Feb 16 '18 at 15:30
6
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Thanks for the quote! $\endgroup$ – gimusi Feb 15 '18 at 21:49
  • 1
    $\begingroup$ You're welcome @gimusi. Good answer! $\endgroup$ – N. Shales Feb 15 '18 at 21:58
  • 1
    $\begingroup$ Way to go @N.Shales! I'm glad that you explained this one, until now I always say to people it is a hard way but I never did this kind of solution in a systematic way as you do now. I liked it :) $\endgroup$ – ArsenBerk Feb 17 '18 at 19:53
  • 1
    $\begingroup$ Thanks @ArsenBerk. It's a first for me as well. But if you can come up with a systematic way to enumerate, then, no matter how complicated, it ought to give the same answer, and probably a combinatorial identity as a by-product. :) $\endgroup$ – N. Shales Feb 17 '18 at 23:41
2
$\begingroup$

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.

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