# Combinatorial interpretation of the identity: ${n \choose k} = {n \choose n-k}$

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?

-
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? –  user123454321 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

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.

-
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.

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

-