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.

What is the combinatorial interpretation of the identity: ${n \choose k} = {n \choose n-k}$?

Proving this algebraically is trivial, but what exactly is the "symmetry" here. Could someone give me some sort of example to help my understanding?

EDIT: Can someone present a combinatorial proof?

share|improve this question
    
Excuse lack of my background, but I am curious about your second question. What do you mean by 'combinatorial proof'? Are you considering counting two different sets by a bijection? What do you have in mind? –  GYC Jan 28 '13 at 2:53
    
That seems sufficient and like the correct approach. I especially just do not want to see the algebraic proof. –  CodeKingPlusPlus Jan 28 '13 at 2:57

3 Answers 3

up vote 7 down vote accepted

Choosing $k$ objects among $n$ objects is same as leaving $n-k$ objects among $n$ objects.

(Notice that there is no essential difference between the words "choose" and "leave".)


Digression: I also consider this as one of the reasons why $0! = 1$ is a good definition.

share|improve this answer
    
I like the explanation with the words "choose" and "leave". –  CodeKingPlusPlus Jan 28 '13 at 2:50

Let's say you have 3 apples and you want to choose one of them. Then you are left with an apple, which is the same, in a sense, as choosing that apple.

share|improve this answer
1  
I cannot make any sense of this sentence. –  CodeKingPlusPlus Jan 28 '13 at 2:49
    
I think he meant "...choose two of them." –  Pedro Tamaroff Jan 28 '13 at 6:13

$n \choose k$ denotes the number of ways of picking $k$ objects out of $n$ objects, and specifying the $k$ objects that are picked is equivalent to specifying the $n-k$ objects that are not picked.


To put it differently, suppose you have $n$ objects, and you want to partition them into two sets: a set $A$ of size $k$, and a set $B$ of size $n-k$. If you pick which objects go into set $A$, the number of ways of doing so is denoted $n \choose k$, and if you (equivalently!) pick which objects go into set $B$, the number of ways is denoted $n \choose n-k$.

The point here is that the binomial coefficient $n \choose k$ denotes the number of ways partitioning $n$ objects into two sets one of size $k$ and one of size $n-k$, and is thus a special case of the multinomial coefficient $${n \choose k_1, k_2, \dots k_m} \quad \text{where $k_1 + k_2 + \dots k_m = n$}$$ which denotes the number of ways of partitioning $n$ objects into $m$ sets, one of size $k_1$, one of size $k_2$, etc.

Thus ${n \choose k}$ can also be written as ${n \choose k,n-k}$, and when written in this style, the symmetry is apparent in the notation itself: $${n \choose k} = {n \choose k, n-k} = {n \choose n-k, k} = {n \choose n-k}$$

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.