3
$\begingroup$

In a class of $n$ students, how many ways can we choose a size $k$ committee that contains a size m subcommittee?

The committee can be chosen in $\binom nk$ ways and subcommittee can be chosen in $\binom km$ ways. So the answer is $\binom nk$$\binom km$. Why do we use multiplication here instead of, say, addition?

$\endgroup$
4
$\begingroup$

Because for each committee of size $k$ there are $\binom {k}{m}$ committees of size $m$. So you need to add $\binom {k}{m}$ as many as the number of committees with size $k$. You have:

$$ \binom {k}{m} + \binom {k}{m} + \dots + \binom {k}{m} $$ This addition has $\binom {n}{k}$ terms, it sums up to $\binom {n}{k}\binom {k}{m}$

$\endgroup$
0
$\begingroup$

The Fundamental Counting Principle states that if you have $m$ choices and $n$ choices, if you choose one of each, then the total number of choices is $m*n$. This is the basis of probability.

Above you have $\binom{n}{k}$ choices for a committee and $\binom{k}{m}$ choices for subcommittees, so you multiply the choices together $\binom{n}{k}$*$\binom{k}{m}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.