I find the notion of combinatorial proofs very difficult, I was hoping someone could try to explain a particular problem in different words for me, in hope that I will finally understand the notion at work.
Give a combinatorial proof that C(n, r) = C(n, n - r).
Suppose that S is a set with n elements.
Every subset A of S with r elements corresponds to a subset of S with n - r elements, namely the complement of A.
Thus C(n, r) = C(n, n - r).
I don't understand this proof. I have no trouble at all seeing it with algebra, but I don't understand how this proof supposedly "counts" that the LHS is equal to what the RHS counts.
Why is it that every subset A of S with r elements corresponds to a subset of S with n - r elements? How does this trivial proof show this fact?