Results 1 to 3 of 3

Math Help - Bijective proof for how many sequences of subsets

  1. #1
    Newbie
    Joined
    Feb 2014
    From
    Texas
    Posts
    3

    Bijective proof for how many sequences of subsets

    I need to write a bijective proof for the following. I just don't know how to start. Any suggestions. Yes, it is due tonight. It is my last problem of my homework.

    Find out how many how many sequences of subsets (Subscript[X, 1],Subscript[X, 2],..., Subscript[X, k]) of [n] are there that satisfy Subscript[X, 1]\[Intersection]Subscript[X, 2]\[Intersection]...\[Intersection]Subscript[X, k]=\[EmptySet] ?

    Thanks in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,386
    Thanks
    1476
    Awards
    1

    Re: Bijective proof for how many sequences of subsets

    Quote Originally Posted by Caross1177 View Post
    I need to write a bijective proof for the following. I just don't know how to start. Any suggestions. Yes, it is due tonight. It is my last problem of my homework.

    Find out how many how many sequences of subsets (Subscript[X, 1],Subscript[X, 2],..., Subscript[X, k]) of [n] are there that satisfy Subscript[X, 1]\[Intersection]Subscript[X, 2]\[Intersection]...\[Intersection]Subscript[X, k]=\[EmptySet] ?
    Having taught Proof Theory at a university lever for many years, I must say that I have never heard of a bijective proof

    Please state the question in a readable form.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2014
    From
    Texas
    Posts
    3

    Re: Bijective proof for how many sequences of subsets

    These are the notes about it from my professor.

    SECOND PROOF: For a bijective (combinatorial) proof, construct a one-to-one correspondence (a bijection, that is a one-to-one and surjective map).

    Note that the left hand side of the identity
    (a+b
    n) the number of all n-element subsets, say X, of the set [a+b]
    Suppose there are i elements in X\[Intersection][a]. Then there are
    (a
    i) choices for X\[Intersection][a]
    and (b
    n-i) choices for X\[Intersection]{a+1, ..., a+b}
    Therefore, there are (a (b
    i) n-i)

    possibilities for X\[Intersection][a] can have i elements with #X=n.
    Summing over i now completes the proof.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Closed and bounded convergent sequences and subsets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 22nd 2012, 11:04 AM
  2. Bijective Proof
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 30th 2012, 06:50 PM
  3. Bijective proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 27th 2010, 11:11 PM
  4. Bijective Proof
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 30th 2010, 09:49 PM
  5. bijective proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 12th 2009, 01:09 PM

Search Tags


/mathhelpforum @mathhelpforum