For an integer n 2 1, let Sn be the set of all subsets of {1, ..., n}. We define the weight function w by w(X) is the sum of all the elements in X for any X E Sn, with w(0) = 0. For example, w({3, 14, 15} ) = 32 in S92. (a) Define a set In that is the cartesian product of n sets of integers, and define a weight function w* such that a bijection fn : Sn + In exists with w(X) = w* (f(X)) for all X E Sn. You need to state your bijection and inverse, define w*, and explain why w(o) = w*(f()). You do not need to prove that your function is a bijection, but it should be easy for the markers to see that it is a bijection. (b) Use part (a) to prove that n DSn (a) = (1 + 2 ). i=1