This is a problem from CMI Entrance 2014 based on Map from a power set to n-set.
Problem: Map from a power set to n-set
(1) Let A = {1, ... , k} and B = {1, ... , n}. Find the number of maps from A to B .
(2) Define $latex \mathbf{ P_k } $ be the set of subsets of A. Let f be a map from $latex \mathbf{P_k to B }$ such that if $latex \mathbf{ U , V \in P_k }$ then $latex \mathbf{ f(U \cup V) }$= $latex \mathbf{\text{max} { f(U) , f(V) } }$ . Find the number of such functions. (For example if k = 3 and n =4 then answer is 100)
Discussion:
(1) For each member x of set A we have n choices for f(x) in B. Hence the number of functions is $latex mathbf{ n^k }$
(2) Claim (i): $latex \mathbf{ f(\phi) }$ is minimum for any such function f from $latex \mathbf{P_k to B }$ . This is because $latex \mathbf{ f(A_1) = f(\phi \cup A_1 ) = \text{max} { f(A_1), f(\phi) } }$ hence $latex \mathbf{f(A_1)}$ must be larger than $latex \mathbf{ f(\phi) }$ for any member $latex \mathbf{A_1}$ of $latex \mathbf{ P_k }$
Claim (ii) If we fix the values of the singleton sets then the entire function is fixed. That is if we fix the values of f({1}) , f({2}) , ... , f({k}). Since for any member $latex \mathbf{A_1}$ of $latex \mathbf{P_k , {A_1} }$ is union of several singleton sets. Hence it's value is the maximum of the functional values of those singleton sets. For example let $latex \mathbf{ A_1 = (1, 2) }$ then $latex \mathbf{f(A_1) = f({1}\cup{2}) = \text {max} {f({1}) , f({2}) } }$
Claim (iii) f({1}) , ... , f({k}) are individually independent of each other.
Now we fix $latex \mathbf{ f(\phi) = i}$. Since it is the smallest, the singleton sets map to i to n.
Hence if $latex \mathbf{ f(\phi) = 1}$ each of the singleton sets have n choices from 1 to n; hence there are $latex \mathbf{ n^k }$ functions. Similarly $latex \mathbf{ f(\phi) = 2}$ each of the singleton sets have n-1 choices from 2 to n; hence there are $latex \mathbf{ (n-1)^k }$ functions.
Thus the total number of functions = $latex \mathbf{ \sum_{i=1}^n i^k }$
[…] Let A = {1, … , k} and B = {1, … , n}. Find the number of maps from A to B . Define be the set of subsets of A. Let f be a map from such that if then = . Find the number of such functions. (For example if k = 3 and n =4 then answer is 100). Solution […]