Show that ${{n}\choose{k}} = {{n}\choose{n-k}}$ without using ${{n}\choose{k}} = \frac{n!}{k!(n-k)!}$ Suppose $n,k \in \mathbb{Z} $ and $0 \leq k \leq n$. Show that ${{n}\choose{k}} = {{n}\choose{n-k}}$ without using ${{n}\choose{k}} = \frac{n!}{k!(n-k)!}$
It's easy to prove by using that definition, but I'm supposed to use the following fact:
"If $n$ and $k$ are integers, then ${{n}\choose{k}}$ denotes the number of subsets that can be made by choosing $k$ elements from a set with $n$ elements."
So if $S$ is a set and $|S| = n$, then ${{n}\choose{k}} = |\{X: X \in \wp(S)$ and $|X| = k \}|$ and  ${{n}\choose{n-k}} = |\{X: X \in \wp(S)$ and $|X| = n - k \}|$
From there, I'm stuck. Any hints?
Thank you.
 A: Use the following bijection $$\varphi:\{X\ :\ X\in\wp(S), \vert{X}\vert=k \}\longrightarrow\{Y\ :\ Y\in\wp(S), \vert{Y}\vert=n-k\}$$ such that $X\longmapsto X^{c}$ where $X^{c}$ is the complement of $X$ w.r.t $\wp(S)$. This map is bijective because it is it's own inverse (is an involution on $\wp(S)$).
A: The answer just given got my vote but other people may prefer a more wordy version.
$n\choose k$ counts in how many ways you can pick $k$ elements from a bag of $n$ different elements.
$n\choose n-k$ counts in how many ways you can pick $n-k$ elements from the same bag.
Now imagine when you pick the $n-k$ elements, you leave remaining $k$ elements to your friend.
So $n \choose n-k$ also counts in how many ways your friend can receive $k$ elements from that bag, but there are $n\choose k$ such ways.
A: I am not sure if this is helpful and I think you are already well aware of this but just in case :
nCk denotes how many combinations are there to choose k items from a set of n items, but choosing k items is the also same as choosing and discarding (n-k) items, thus proven verbally. 
