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

Mathematics Asked by ijm on November 30, 2020

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?

One 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.

Correct answer by N. F. Taussig on November 30, 2020

Add your own answers!

Related Questions

An orthonormal basis in a subspace.

1  Asked on December 13, 2021 by ryuta-osawa


Summation involving Gamma function

1  Asked on December 10, 2021 by paranoid


Find x in a multiple arithmetic sequence

1  Asked on December 10, 2021 by billy-senders


Proof that this is a Primitive Recursive function

2  Asked on December 10, 2021 by user6767509


Ask a Question

Get help from others!

© 2022 All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP, SolveDir