0
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$
    – imbAF
    Sep 26, 2022 at 20:23
  • 1
    $\begingroup$ 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. $\endgroup$
    – lulu
    Sep 26, 2022 at 20:24
  • 1
    $\begingroup$ 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. $\endgroup$
    – lulu
    Sep 26, 2022 at 20:25
  • $\begingroup$ thanks for the clarification $\endgroup$
    – imbAF
    Sep 26, 2022 at 20:28

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Yes, I was able to deduce that eventually. But your answer also helps me, specially the example, which makes things clearer. Thank you $\endgroup$
    – imbAF
    Sep 26, 2022 at 20:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .