# Combinatorial proof of $\binom{n}{k} = \binom{n}{n-k}$

How do I prove this combinatorially?

$$\displaystyle \binom{n}{k} = \binom{n}{n-k}$$

-

## 3 Answers

Picking the $k$ elements you want out of $n$ possibilities amounts to the same thing as picking the $n-k$ elements you don't want out of $n$ possibilities.

-

If $X$ is a set, we denote its cardinality with $\# X$ . If $A$ is a set with $\# A = n$ and $0 \leq k \leq n$, then there exists a bijective mapping between the two following sets: $$U = \{ X \subseteq A \mid \ \#X = k \},$$ $$V = \{ Y \subseteq A \mid \ \#Y = n-k \};$$ the map is $X \mapsto A \setminus X$.

-

$$\binom 62 =15 = \binom 64.$$ The number of ways to choose 2 out of 6 equals the number of ways to choose 4 out of 6, since every way of choosing 2 out of 6 corresponds to a way of choosing 4 out of 6, namely the 4 that are not among the chosen 2: $$\begin{array}{rcl} AB & \leftrightarrow & CDEF \\ AC & \leftrightarrow & BDEF \\ AD & \leftrightarrow & BCEF \\ AE & \leftrightarrow & BCDF \\ AF & \leftrightarrow & BCDE \\ BC & \leftrightarrow & ADEF \\ BD & \leftrightarrow & ACEF \\ BE & \leftrightarrow & ACDF \\ BF & \leftrightarrow & ACDE \\ CD & \leftrightarrow & ABEF \\ CE & \leftrightarrow & ABDF \\ CF & \leftrightarrow & ABDE \\ DE & \leftrightarrow & ABCD \\ DF & \leftrightarrow & ABCE \\ EF & \leftrightarrow & ABCD \end{array}$$ (And simlilarly with other numbers.)

-