Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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. –  Bill Cook Oct 2 '11 at 19:08
    
@Bill Cook: Ok, let me try it out. –  user952949 Oct 2 '11 at 19:16
1  
@BillCook: you should make that comment into an answer. –  Greg Martin Oct 2 '11 at 19:45

3 Answers 3

Consider this question:

From a group of $n$ people how many ways can we choose $a$ people to have an A on their jersey and $b$ people to have a B on their jersey while having $k$ people with both an A and a B on their jersey?

Once you have explained why both sides must be equal, you should be able to see that both sides must equal $\displaystyle\frac{n!}{(a-k)!(b-k)!k!(n-a-b+k)!}$.

jersey

share|improve this answer

To expand my comment:

If you let $n$ be the total number of people, let $a$ be the number of people on team 1 (so $n-a$ people are on team 2), let $b$ be the total number of leaders, and let $k$ be the number of leaders on team 1 (so $b-k$ leaders are on team 2).

Consider the left hand side: $n \choose a$ is the number of ways of selecting team members. Then $a \choose k$ chooses the leaders on team 1. This leaves $b-k$ leaders to be chosen from the remaining $n-a$ people (who are on team 2).

Now the right hand side: $n \choose b$ is the number of ways of choosing leaders. $b \choose k$ is the number of ways of choosing leaders on team 1. Since $k$ people have been chosen for team 1, $a-k$ more members of team 1 must be chosen. These must be chosen from the pool of non-leaders (of which there are $n-b$). The number of ways of choosing the remaining team members is then $n-b \choose a-k$.

share|improve this answer
    
Thanks a lot for your help Bill. I got the answer already from your helpful suggestion above itself. I guess I just word my answers very badly. This answer helped me organise my answer better. –  user952949 Oct 2 '11 at 20:43
    
Glad to help. I could tell you just needed a little "push" –  Bill Cook Oct 2 '11 at 21:23

Both products are easily seen to be expressions for the quadrinomial coefficient $$ \binom n{a-k,\quad k,\quad b-k,\quad n-a-b+k}. $$ In other words they count ways to colour $n$ object with $4$ colours, using each colour repectively $a-k$ $k$, $b-k$ and $n-a-b+k$ times. The different products correspond to two ways of making a first selection into two batches of $2$ colours each first, and then selecting one colour within each batch. See robjohn's anwer for a nice description of two ways of dividing into batches (based on A's respectively on B's). There is no need for the formula for the quadrinomial coefficient.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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