Results 1 to 8 of 8

Math Help - Power set,bijection and binomial coefficient

  1. #1
    Junior Member
    Joined
    Jan 2011
    Posts
    45

    Power set,bijection and binomial coefficient

    Let N={1,2.....n} .Define the Power set of N,P(N), and show that the map f:P(N)->P(N)
    defined by taking A to belong to P(N) to N\A is a bijection.
    Also prove using the above that
    (n)=(n)
    (k-1) (k)

    Now the power set is defined by P(N)=2^n and a bijection is a one-to-one function that is both injective and surjective.But I don't understand the rest.I"ve been looking at it for the past 1 hour.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,956
    Thanks
    1780
    Awards
    1

    Re: Power set,bijection and binomial coefficient

    Quote Originally Posted by AkilMAI View Post
    Let N={1,2.....n} .Define the Power set of N,P(N), and show that the map f:P(N)->P(N)
    defined by taking A to belong to P(N) to N\A is a bijection.
    The LaTeX rendering is down at the present.
    So let C(A) denote the complement of A in N={1,2,3,...,n}.
    The proof that f is invective depends on the fact that C(C(A))=A.
    That is also used to prove it is surjective.
    If B is a subset of N, then f(C(B))=B.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jan 2011
    Posts
    45

    Re: Power set,bijection and binomial coefficient

    That is an interesting ideea...I never thought of using the complement.How can I use that to prove the last binomial relation from the problem?I know that
    (n)=(n-1) + (n-1)
    (k) (k-1) (k)
    but is states to use part a)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Jan 2011
    Posts
    45

    Re: Power set,bijection and binomial coefficient

    For part a) my ideea for to use the fact that the domain and range have the same cardinality since we are using the power set of N but I don't know how to expres this in a mathematical way that will be inteligible.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,956
    Thanks
    1780
    Awards
    1

    Re: Power set,bijection and binomial coefficient

    Quote Originally Posted by AkilMAI View Post
    That is an interesting ideea...I never thought of using the complement.How can I use that to prove the last binomial relation from the problem?I know that
    (n)=(n-1) + (n-1)
    (k) (k-1) (k)
    but is states to use part a)
    First of all the notation N\A means the complement of A in N.

    Let's use C(N,k) to mean combination of N taken k at a time.
    And |A| is the number of elements in A.

    |N\A|=n-|A|. BUT |A|=C(n,|A|).
    Use the symmetry from part a).
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Jan 2011
    Posts
    45

    Re: Power set,bijection and binomial coefficient

    I"m sorry maybe I'm just tired...but I"m more confused about both parts now that I was before.How can I use the complement in part a) to prove injection and surjection and what symmetry are you referring to?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,956
    Thanks
    1780
    Awards
    1

    Re: Power set,bijection and binomial coefficient

    Quote Originally Posted by AkilMAI View Post
    I"m sorry maybe I'm just tired...but I"m more confused
    Sorry, but I will not do this problem for you.
    The last line in reply #2 proves that f is surjective.
    For injectivity note that the complement of the complement is the original set.

    BTW. In part b) you are to prove that C(n,k)=C(n,n-k). Not what you posted in the O.P.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Jan 2011
    Posts
    45

    Re: Power set,bijection and binomial coefficient

    Maybe you do get people asking you to do their problems for them but in this case that wasn't what I was implying...I was only saying that I got more confused.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Binomial Coefficient
    Posted in the Math Challenge Problems Forum
    Replies: 5
    Last Post: August 15th 2010, 09:50 AM
  2. binomial coefficient.
    Posted in the Algebra Forum
    Replies: 3
    Last Post: May 12th 2010, 11:30 PM
  3. Binomial Coefficient
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 1st 2009, 06:37 PM
  4. Binomial Theorem or Binomial Coefficient
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: October 2nd 2009, 02:06 PM
  5. Binomial Coefficient
    Posted in the Algebra Forum
    Replies: 4
    Last Post: October 27th 2007, 05:35 AM

Search Tags


/mathhelpforum @mathhelpforum