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