Combinatorial proof?

• April 3rd 2011, 09:32 AM
posix_memalign
Combinatorial proof?
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?
• April 3rd 2011, 09:50 AM
Plato
Quote:

Originally Posted by posix_memalign
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).

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?

For each $A\in\mathcal{P}(S)$ consider the pair $
\left( {A,S\backslash A} \right)$
, that is a subset and its relative complement.
If $\|A\|=r~\&~\|S\|=n$ then $\|S\backslash A\|=n-r$.
So counting the subsets with $r$ elements is the same as counting the subsets with $n-r$ elements.
There is a one-to-one correspondence between those to type sets.
• April 3rd 2011, 09:51 AM
veileen
"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 $S=\left \{ a_1, a_2, ..., a_n \right \}$, a subset $A_k=\left \{ a_1, a_2, ..., a_k \right \}$ then you have a $A'_k$ subset such that $A'_k=\left \{ a_{k+1}, a_{k+2}, ..., a_n \right \}$
So however you chose a subset with k elements you will have the n-k elements that form another subset.
• April 3rd 2011, 10:44 AM
emakarov
Quote:

Originally Posted by Plato
So counting the subsets with $r$ elements is the same as counting the subsets with $n-r$ elements.
There is a one-to-one correspondence between those to type sets.

Yes. To be completely precise, one can consider $\mathcal{A}=\{A\subseteq S:|A|=r\}$ and $\mathcal{B}=\{A\subseteq S:|A|=n-r\}$. By definition, $|\mathcal{A}|=C(n,r)$ and $|\mathcal{B}|=C(n,n-r)$. Then one can show that $f(A)=S\setminus A$ is a bijection from $\mathcal{A}$ to $\mathcal{B}$ (note that $f(f(A))=A$), which means that $|\mathcal{A}|=|\mathcal{B}|$.
• April 3rd 2011, 11:39 AM
posix_memalign
Quote:

Originally Posted by veileen
"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 $S=\left \{ a_1, a_2, ..., a_n \right \}$, a subset $A_k=\left \{ a_1, a_2, ..., a_k \right \}$ then you have a $A'_k$ subset such that $A'_k=\left \{ a_k+1, a_k+2, ..., a_n \right \}$
So however you chose a subset with k elements you will have the n-k elements that form another subset.

But how does

Quote:

So however you chose a subset with k elements you will have the n-k elements that form another subset.
show that these two subsets are of equal length?
• April 3rd 2011, 11:53 AM
veileen
There are C(n, k) subsets with k elements. But for every subset with k elements exist another subset containing the n-k elements remained, so there are C(n, k) subsets with n-k elements too.

An example would help?
• April 3rd 2011, 03:22 PM
Plato
Quote:

Originally Posted by posix_memalign
But how does show that these two subsets are of equal length?

In these proofs we are not showing that the two sets are equally numerous.
We are showing that the collection of subsets of k elements is equally numerous with the collection of subsets of n-k elements.