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).
Proof:
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?
"Every subset A of S with r elements corresponds to a subset of S with n - r elements, namely the complement of A."
Well, let , a subset then you have a subset such that
So however you chose a subset with k elements you will have the n-k elements that form another subset.