# Bijective proof for how many sequences of subsets

• Feb 16th 2014, 04:36 PM
Caross1177
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.(Headbang)

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] ?

• Feb 16th 2014, 05:12 PM
Plato
Re: Bijective proof for how many sequences of subsets
Quote:

Originally Posted by Caross1177
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.(Headbang)

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

• Feb 16th 2014, 05:47 PM
Caross1177
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.