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.
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.