(i) How many functions are there from the set $\{ 1 , \ldots , k \}$ to the set $\{ 1 , \ldots , n \}$ ?
(ii) Let $P _ { k }$ denote the set of all subsets of $\{ 1 , \ldots , k \}$. Find a formula for the number of functions $f$ from $P _ { k }$ to $\{ 1 , \ldots , n \}$ such that $f ( A \cup B ) =$ the larger of the two integers $f ( A )$ and $f ( B )$. Your answer need not be a closed formula but it should be simple enough to use for given values of $n$ and $k$, e.g., to see that for $k = 3$ and $n = 4$ there are 100 such functions. Example: When $k = 2$, the set $P _ { 2 }$ contains 4 elements: the empty set $\phi , \{ 1 \} , \{ 2 \}$ and $\{ 1,2 \}$. The function $f$ given by $\phi \rightarrow 2 , \{ 1 \} \rightarrow 3 , \{ 2 \} \rightarrow 4 , \{ 1,2 \} \rightarrow 4$ satisfies the given condition. But the function $g$ given by $\phi \rightarrow 2 , \{ 1 \} \rightarrow 3 , \{ 2 \} \rightarrow 4 , \{ 1,2 \} \rightarrow 5$ does not, because $g ( \{ 1 \} \cup \{ 2 \} ) = g ( \{ 1,2 \} ) = 5 \neq$ the larger of $g ( \{ 1 \} )$ and $g ( \{ 2 \} ) = \max ( 3,4 ) = 4$.