I'm am not completely clear on what is means to count in two different ways.

Here is the question.

$m$ and $n$ are integers with $0 \le m \le n$. In a town in the USA there are $n+1$ townspeople. This town is run by one mayor and $m$ council-members (the mayor cannot be a councillor). Prove the following by counting in two different ways the number of ways to choose a town's elected officials.

$(n+1)$$n \choose m$$=(n+1-m)$${n+1}\choose m$

So if anyone can explain how to do these types of questions that would be great.



These kinds of proofs are called combinatorial proofs. In order to choose a mayor and $m$ council-members, we can do it in two ways: we can choose a mayor and then the council-members, or we can choose the council-members and then choose the mayor.

In the first way, we have $n + 1$ choices for the mayor. To choose a council, we need to pick $m$ people from the remaining $n$ townspeople (as the mayor cannot be a councillor). Thus, there are $\binom{n}{m}$ ways to choose the council; multiplying the two together gives $(n + 1)\binom{n}{m}$ ways in total.

Can you see how to get the other formula combinatorially?

  • 1
    $\begingroup$ I think so. So I guess that in the other formula there are $n+1$ choices for councillors and we need $m$ councillors. Once we have chosen the councillors we choose the mayor second. This is still out of the population of $n+1$ but we need to subtract the $m$ council-members. $\endgroup$ – Steph Sep 20 '15 at 22:34
  • $\begingroup$ @Steph, Yes, that's exactly correct. $\endgroup$ – Marcus M Sep 20 '15 at 22:36

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.