6
$\begingroup$

I have to prove the following using a combinatorial proof:

$\binom{n}{a}\binom{a}{k}\binom{n-a}{b-k} = \binom{n}{b}\binom{b}{k}\binom{n-b}{a-k}$

Ok, so here is what I have worked out so far:

We have some sets a, b, n, k.

From what I can see in the identity: a is subset of n; k is subset of a; b is subset of n; k is subset of b

Here is what I think the combinatorial proof should be (using the committee forming method):

We have a total of n people. We want to form 2 teams: Team 1 and Team 2, containing a and b number of people, respectively. And elect a total of k people as leaders of the 2 teams.

there are 2 different ways of forming such sets.

Out of n, choose the number of people to be in team 1. $\binom{n}{a}$ ways of doing this. Then we choose to select all the k leaders out of team 1. $\binom{a}{k}$ ways of doing this. Out of the remaining people, select the total number of people to be in team 2. We have already selected a people out of n, and already selected all the k leaders, hence $\binom{n-a}{b-k}$ ways of doing this.

Out of n total people, chose all the people to be in team 2. $\binom{n}{b}$ ways of doing this. Then we choose to elect all the k leaders from team 2. $\binom{b}{k}$ ways of doing this. Out of the remaining (n-b) people, we need to select the people to be in team 1, but since all the leaders are taken from team 2 already, we have $\binom{n-b}{a-k}$ ways of doing this.

What do you guys think?

Most of it makes sense to me, although I am really not sure if I am doing the $\binom{n-a}{b-k}$ and $\binom{n-b}{a-k}$ parts right in each side of the equation.

  • 1
    Try instead: n = total number of people. a = number of people on team 1 (so n-a people on team 2). b = total number of leaders. k = number of leaders on team 1 (so b-k leaders on team 2). Then the left hand side picks the team then the leaders and the right hand side picks the leaders and then the team.2011-10-02
  • 0
    @Bill Cook: Ok, let me try it out.2011-10-02
  • 1
    @BillCook: you should make that comment into an answer.2011-10-02

3 Answers 3