# Validity of an Identity proven via combinatorial proof

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?

• I think I understood it. The bijection isn't considering the elements of a subset A of S and the elements of the complementary of A, but rather the nr. of subsets with r elements and the nr. of complementary subsets with n-r elements. But I am not entirely certain. Therefore I'd like a confirmation and maybe a better worded explanation Sep 26, 2022 at 20:23
• the bijection is between the two sets of choices. Let's say you are computing $\binom 31$. That's the number of ways to choose $1$ element out of $3$ so, if your objects are $\{1,2,3\}$ your choices are $\{1\}, \{2\},\{3\}$. But now mapping each of those choices to its complement gives $\{2,3\}, \{1,3\}, \{1,2\}$ which are the ways to choose $2$ elements out of the same set.
– lulu
Sep 26, 2022 at 20:24
• Phrased informally: to identify a subset of a given set one can either list the elements which are in that subset or list the elements which are not in the subset.
– lulu
Sep 26, 2022 at 20:25
• thanks for the clarification Sep 26, 2022 at 20:28

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.