There is the following identity:
$C(n,r)=C(n,n-r)$.
While it is easy, to algebraically prove this identity, one can also use a combinatorial proof to do so. In my script the two types of combinatorial proof that were used to prove the identity were:
1.Bijective proof 2.Double Counting Proof
This is what it is written, when using the Bijective proof:
Bijective Proof: Suppose that S is a set with n elements. The function that maps a subset A of S to $\bar {A}$ is a bijection between the subsets of S with r elements and the subsets with n-r elements. Since there is a bijection between the two sets, they must have the same number of elements.
"..there is a bijection between the two sets..", which two sets? The set with r elements and n-r elements?
If that's the case, how is that possible. Let's say we have a set with n=10. r=4, then n-r=6. So clearly, the two subsets do not have the same nr. of elements, therefore there can be no bijection here.
Am I missing something?
It is a bijection from the set of all $k$-element subsets to the set of all $(n-k)$-element subsets.
Perhaps an illustration would help. Suppose $n=5$ and $k=2$. Here is the set of all $2$-element subsets of $\{1,2,3,4,5\}$: $$ \{1,2\},\{1,3\},\{1,4\},\{1,5\},\{2,3\},\{2,4\},\{2,5\},\{3,4\},\{3,5\},\{4,5\} $$ Here is the set of all $3$-element subsets of $\{1,2,3,4,5\}$: $$ \{3,4,5\},\{2,4,5\},\{2,3,5\},\{2,3,5\},\{1,4,5\},\{1,3,5\},\{1,3,4\},\{1,2,5\},\{1,2,4\},\{1,2,3\} $$ The claim is that there is a bijection between these two groups of sets. Indeed, for each element in the first group, you can match its set-theoretic complement in the second group, which is a one-to-one and onto correspondence between these two groups.