# Committee Forming Combinatorics Problem

A five-person committee consisting of students and teachers is being formed to study the issue of student parking privileges. Of those who have expressed an interest in serving on the committee, 12 are teachers and 14 are students. How many ways can the committee be formed if at least one student and one teacher must be included?

What I did: 12C1 * 14C1 * 24C3 = 340032

(Choose out of 12 teachers for one spot, out of 12 students for another, and finally out of 24 people remaining choose 3 for the remaining three spots)

Answer in back of book: 62986

Where am I going wrong?

• Your answer is somehow treating the student picked in step 2 as being more special than any other possible students picked in step 3 of your multiplication principle. Letting capital letters denote teachers and lowercase letters denote students, you are counting (A)(a)(BCd) as a different committee than $(B)(d)(AaC)$. – JMoravitz Feb 4 '17 at 4:08
• As for a correct approach, count how many five person committees can be formed if you don't care about the requirement that at least one must be a student and at least one must be a teacher? How many violate the "at least one student" property? How many violate the "at least one teacher" property? How many violate both? Apply inclusion-exclusion principle and reach a conclusion. – JMoravitz Feb 4 '17 at 4:09
• Inclusion Exclusion Principle, haven't learned that yet – user224997 Feb 4 '17 at 4:10
• Inclusion-Exclusion is one of the very first things taught in introductory counting in the classes I've instructed in the past. The two-set version is $|A\cup B|=|A|+|B|-|A\cap B|$. In this case letting $A$ denote the set of committees with no teachers, $B$ set of committees with no students, you have $|A\cup B|$ is the set which violates at least one of those two conditions. Violating none of the conditions is the opposite event. – JMoravitz Feb 4 '17 at 4:12
• Okay, it's the addition rule in probability, I never knew it as IE Principle with just sets – user224997 Feb 4 '17 at 4:13

So you have a total of $26$ people to choose from, teachers and students but only $5$ can be representatives for the team. We need to keep in mind that we can't have all teachers or students in the committee at one time. So what this means is that the number of ways to arrange the teachers is $$C (12,5) = 792$$ The number of ways to choose the students is $$C(14,5) = 2002$$ This is straight from what we are given. Overall, if we assume that we have no restriction at all, we have a total of $$C(26,5) = 65780$$ Since we can't have all teachers or students represent the team, subtract $$65780 - 2002 - 792 = 62986$$ Another reason we subtract from the total is because we don't want to count our arrangements more than once.

• As mentioned above, this is a practical use of the Inclusion-Exclusion principle. – John Smith Feb 4 '17 at 4:18

Summarizing the conversation from above, your approach is incorrect because it overcounts several scenarios since it somehow distinguishes between people selected in the first two steps versus being selected in the third step so you get committees reappearing in your count such as

$$(A)(a)(BCd)~~~~~~(B)(d)(AaC)$$

despite them both being the same five person committee $(AaBCd)$.

In order to apply multiplication principle, you must ensure that each outcome is counted exactly once (or for a more complicated phrasing, exactly the same number of times so you can divide by that number later on). This is not the case in the setup that you have so far.

Instead, we count how many arrangements there are if we don't care about the condition that there must be at least one student and at least one teacher. In these arrangements, some will be good and some will be bad. By subtracting away how many are bad, we are left with the number of good arrangements.

There are $\binom{26}{5}$ if we don't care.

$\binom{12}{5}$ are bad because they use only teachers (and have no students)

$\binom{14}{5}$ are bad because they use only students (and have no teachers)

Ordinarily we would need to be careful because we might accidentally subtract away some of these bad outcomes twice, so we add back in again the number which violate both to correct it so that the bad outcomes were only subtracted a total of once each, but in this case there are no outcomes which simultaneously have no students and no teachers, so we are only adding back zero.

there are then $\binom{26}{5}-\binom{12}{5}-\binom{14}{5}$ arrangements.

An alternate solution:

Break into cases based on the number of students in the committee. There could be $1,2,3$ or $4$ students. With $k$ students, pick which $k$ students are in the committee and pick which $5-k$ teachers are in the committee.

There are then $\binom{14}{1}\binom{12}{4}+\binom{14}{2}\binom{12}{3}+\binom{14}{3}+\binom{12}{2}+\binom{14}{4}\binom{12}{1}$ arrangements.

One can see that the earlier employed method is less computation heavy and is easier to calculate in this case, and in particular in larger cases too

• Very clever alternate solution! – John Smith Feb 4 '17 at 4:33