# Why aren't these two solutions equivalent? Combinatorics problem

I was given the following fact: there is a set $$S$$ of $$11$$ people, among which there are $$4$$ professors and $$7$$ students,

$$S=\{p_1, p_2, p_3,p_4, s_1, s_2,...,s_7\}$$

We are requested to form from it a group of $$5$$ people, and we must have at least 3 professors.

I find that the two answers I will expose should be equivalent, but are not, and I can't figure out why.

The group of $$5$$ people must have at least $$3$$ professors. This means that three of the $$5$$ people will necessarily be a subset of $$S_p$$, the subset of $$S$$ containing only the professors. There are $$\binom{4}{3}$$ subsets of $$S_p$$, and therefore I have $$\binom{4}{3}$$ alternatives for the three professors that must be in the group.

Now that I've made sure this $$3$$ professors are in the group, I have $$11-3=8$$ people left to choose from. The remaining two persons of the group can either be professors or students, so I can pick any of those $$8$$. So for the two remaining places I have $$\binom{8}{2}$$ alternatives. At last, I have $$\binom{4}{3} \binom{8}{2} = 112$$ ways of forming a group of $$5$$ people in which there will definitely be at least $$3$$ professors.

There are $$4$$ professors and, in my group of $$5$$ people, I must have at least $$3$$ of them. So I'll either have $$3$$ or $$4$$ professors.

If I have $$3$$ professors, I'll choose them from the $$4$$ professors, and fill the remaining two places with $$2$$ of $$7$$ students. This is $$\binom{4}{3} \binom{7}{2}$$.

If on the other hand I have $$4$$ professors, I'll have $$\binom{4}{4}$$ alternatives for choosing them, and $$\binom{7}{1}$$ ways of choosing a student for the remaining last place.

So at last there are $$\binom{4}{3}\binom{7}{2}+\binom{4}{4}\binom{7}{1} = 91$$ ways of making the group.

Doubt

As you can see, the answers are different. Answer $$1$$ says there are $$112$$ ways of making the group; answer two says $$91$$. However, both reasonings seem okay to me and I can't see why should they differ nor where. Perhaps someone can clear this up for me.

• This was my #1 favorite counterintuitive math problem that completely caught me out for years. I asked every teacher I had since, no one could answer, until I got to college and finally received the answer that I'd been looking for for years. – Flater Apr 23 '19 at 11:25
• It is a real head-cracker I should say, got me really confused for several days until I decided to ask it here. It is a huge "oooooohhhhhh" when one realizes the mistake. – lafinur Apr 23 '19 at 16:52

Your second solution is the correct one.

Your first solution is incorrect because you overcount the scenarios where a professor is picked in the second step.

The outcome where you pick the first three professors in the first step followed by the fourth professor in the second step: $$\{p_1,p_2,p_3\},\{p_4,s_1\}$$ is also counted where you picked the last three professors in the first step and the first professor in the second step: $$\{p_2,p_3,p_4\},\{p_1,s_1\}$$. These outcomes should be considered the same however since in both scenarios you have the same five people selected.

Be careful not to overcount things with multiplication principle. Objects selected in one step are treated differently than objects selected in a later step.

• Of course! Now I understand. Thank you for answering my doubt. – lafinur Apr 22 '19 at 20:13

The first answer is wrong. It overestimates the count by double-counting the four-professors solutions. This is because each can begin with three of the four in four different ways. Note that $$\binom{4}{3}\binom{7}{2}+4\binom{4}{4}\binom{7}{1}=112.$$Although "double counting" referred above to a fallacy, it's also the name of a valid, useful technique one should be happy to use.

• This is right, thank you for taking the trouble and answering my doubt! – lafinur Apr 22 '19 at 20:13