Results 1 to 7 of 7

Math Help - Combinatorial proof?

  1. #1
    Member
    Joined
    May 2008
    Posts
    87

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,966
    Thanks
    1785
    Awards
    1
    Quote Originally Posted by posix_memalign View Post
    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 <br />
\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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Mar 2011
    From
    Awetuouncsygg
    Posts
    182
    Thanks
    12
    "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.
    Last edited by veileen; April 3rd 2011 at 12:51 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    Quote Originally Posted by Plato View Post
    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}|.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    May 2008
    Posts
    87
    Quote Originally Posted by veileen View Post
    "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

    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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Mar 2011
    From
    Awetuouncsygg
    Posts
    182
    Thanks
    12
    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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,966
    Thanks
    1785
    Awards
    1
    Quote Originally Posted by posix_memalign View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combinatorial Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 10th 2011, 02:42 PM
  2. Combinatorial proof
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: September 30th 2010, 01:33 AM
  3. Combinatorial Proof
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: August 18th 2010, 05:08 AM
  4. Combinatorial proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 10th 2009, 01:20 PM
  5. combinatorial proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 30th 2008, 03:13 PM

Search Tags


/mathhelpforum @mathhelpforum