When do we use multiplication instead of addition?

Question

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?

Mehdi Jafarnia Jahromi · Accepted Answer · 2015-04-29T16:41:24.837

4

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}$

edited Apr 29 '15 at 16:41

answered Apr 29 '15 at 16:34

Mehdi Jafarnia Jahromi

1,718

So, $\binom km$ is is a coefficient of $\binom nk$, right? – shake-up Apr 29 '15 at 16:38
Right, in fact you need to look deeper to the Rule of Product. Look at this link: http://en.wikipedia.org/wiki/Rule_of_product – Mehdi Jafarnia Jahromi Apr 29 '15 at 16:44
@avid19: Fair enough. – Brian M. Scott Apr 30 '15 at 06:31

score 0 · Answer 2 · answered Apr 29 '15 at 16:48

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}$

When do we use multiplication instead of addition?

2 Answers2