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

Thanks in advance.

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*

Please state the question in a readable form.

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.