I have a question regarding a combinatorics problem. A college offers $8$ subjects for the undergraduate course. A student can opt for any three subjects. So there are total in total $\binom{8}{3}$ subjects combinations. However there are certain subject restrictions. A student can not opt Geography and History, Anthropology and Hindi, English and Education, English and Hindi together. Consequently how many subject combinations will be there?
How many ways can a student opt for three subjects given the restrictions
combinationscombinatorics
Best Answer
As you observed, there are $$\binom{8}{3}$$ ways to choose three of the eight subjects without restriction. From these, we must subtract those cases that involve a prohibited combination.
If a student had opted for one of the four prohibited pairs of subjects, he or she would have $8 - 2 = 6$ choices for the third subject in his or her undergraduate course. Hence, we must subtract these $$\binom{4}{1}\binom{6}{1}$$ choices.
However, if we do so, we will have subtracted some combinations twice, once for each way of designating one of the pairs of prohibited subjects as the prohibited pair. We only want to subtract those cases once, so we must add them to the total.
To illustrate, a student who has not taken the restrictions into account could select Anthropology, English, and Hindi. We have subtracted this case twice, once we designated Anthropology and Hindi as the prohibited pair of courses with English as the additional course and once when we designate English and Hindi as the prohibited pair of courses with Anthropology as the additional course. The other case we have subtracted twice is the selection Education, English, and Hindi. Hence, we have subtracted two selections twice.
Therefore, by the Inclusion-Exclusion Principle, the number of undergraduate courses a student is permitted to select at the college is