How many ways to select 5 objects from 3 groups of 4 objects each?

Question

Consider this problem:

A question paper on mathematics consists of twelve questions divided into three parts A, B
and C, each containing four questions. In how many ways can an examinee answer five
questions, selecting at least one from each part?

I solved this problem taking a case-by-case approach. The examinee could pick 1, 1 and 3 questions, or 2, 2 and 1 questions, from the three sections. Number of ways of picking these questions is ${4 choose 1} times {4 choose 1} times {4 choose 3}$ and ${4 choose 2} times {4 choose 2} times {4 choose 1}$.
We will now multiply the two numbers by $3!/2!=3$ to find the number of permutations. The correct answer is ${4 choose 1} times {4 choose 1} times {4 choose 3} times 3 + {4 choose 2} times {4 choose 2} times {4 choose 1} times 3 = 624$.

Obviously, this approach is not generalizable because it involves thinking about the possible distributions. If the number of questions in each section or the number of sections was large enough, it would be very time-consuming to employ this method. What would be an alternative approach that scales well?

N. F. Taussig · Accepted Answer

We could use the Inclusion-Exclusion Principle.
There are $binom{12}{5}$ ways to select five of the twelve questions on the question paper.  From these, we must subtract those selections which do not contain at least one selection from each section.
There are three ways to exclude a section and $binom{8}{5}$ ways to select five of the remaining eight questions.
Since it is not possible to exclude two of the sections and still select five questions from the remaining four questions, we are done.
$$binom{12}{5} - binom{3}{1}binom{8}{5} = 624$$

Suppose the examinee only had to answer four of the twelve questions, but was still required to answer at least one question from each part.
Observe that the examinee must answer two questions from one part and one from each of the others, which can be done in
$$binom{3}{1}binom{4}{2}binom{4}{1}binom{4}{1} = 288$$
since there are three ways to choose the section from which two questions will be answered, $binom{4}{2}$ ways to choose two questions from that section, and four ways to choose a single question from each of the other sections.
By the Inclusion-Exclusion Principle, there are
$$binom{12}{4} - binom{3}{1}binom{8}{4} + binom{3}{2}binom{4}{4} = 288$$
admissible ways to select the questions since there are $binom{12}{4}$ ways to select four questions, three ways to exclude one section and $binom{8}{4}$ ways to select four of the remaining eight questions, and $binom{3}{2}$ ways to exclude two sections and $binom{4}{4}$ ways to answer all four of the remaining four questions.  The reason we must add the last term is that we subtracted each selection in which all the selected questions are drawn from one section twice, once for each way of designating one of the other two sections as the excluded section.
While the first method of solving this problem is simpler in this case, the Inclusion-Exclusion Principle can be more readily applied if the number of questions in each section ot the number of sections were large.

How many ways to select 5 objects from 3 groups of 4 objects each?

One Answer

Add your own answers!

Ask a Question