4
$\begingroup$

How do I prove this combinatorially?

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

3 Answers 3

8

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.

3

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

1

$ \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.)