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.

How do I prove this combinatorially?

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

share|improve this question
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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.