# Thread: Bijective proof for how many sequences of subsets

1. ## 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] ?

2. ## Re: Bijective proof for how many sequences of subsets

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.

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

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.