In: Advanced Math
Let S be a set of n numbers. Let X be the set of all subsets of S of size k, and let Y be the set of all ordered k-tuples
(s1, s2, , sk)
such that
s1 < s2 < < sk.
That is,
X | = | {{s1, s2, , sk} | si S and all si's are distinct}, and |
Y | = | {(s1, s2, , sk) | si S and s1 < s2 < < sk}. |
(a) Define a one-to-one correspondence
f : X → Y.
Explain why f is one-to-one and onto.
(b) Determine |X| and |Y|.
|X| | = | |
|Y| | = |