**(1) Let A = {1, … , k} and B = {1, … , n}. Find the number of maps from A to B .**

(2) Define \(\mathbf{ P_k } \) be the set of subsets of A. Let f be a map from \(\mathbf{P_k to B }\) such that if \(\mathbf{ U , V \in P_k }\) then \(\mathbf{ f(U \cup V) }\)= \(\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 \(mathbf{ n^k }\)

(2) **Claim (i):** \(\mathbf{ f(\phi) }\) is minimum for any such function f from \(\mathbf{P_k to B }\) . This is because \(\mathbf{ f(A_1) = f(\phi \cup A_1 ) = \text{max} { f(A_1), f(\phi) } }\) hence \(\mathbf{f(A_1)}\) must be larger than \(\mathbf{ f(\phi) }\) for any member \(\mathbf{A_1}\) of \(\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 \(\mathbf{A_1}\) of \(\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 \(\mathbf{ A_1 = (1, 2) }\) then \(\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 \(\mathbf{ f(\phi) = i}\). Since it is the smallest, the singleton sets map to i to n.

Hence if \(\mathbf{ f(\phi) = 1}\) each of the singleton sets have n choices from 1 to n; hence there are \(\mathbf{ n^k }\) functions. Similarly \(\mathbf{ f(\phi) = 2}\) each of the singleton sets have n-1 choices from 2 to n; hence there are \(\mathbf{ (n-1)^k }\) functions.

Thus the total number of functions = \(\mathbf{ \sum_{i=1}^n i^k }\)

*Related*

## 1 comment