Find a formula for the number of functions $f$ from $P_k$ to {$1, . . . , n$} such that $f(A ∪ B)$ = the larger of the two integers $f(A)$ and $f(B)$. Let $P_k$ denote the set of all subsets of {$1, . . . , k$}. Find a formula for the number of
functions $f$ from $P_k$ to {$1, . . . , n$} such that $f(A ∪ 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.
I'm unable to understand the question. Please help.
 A: As  Watercrystal observed, you are asking is the number of monoid morphisms form the monoid $(P_k, \cup)$ to the monoid $(\{1, \ldots, n\}, \max)$. Both monoids are idempotent and commutative and $P_k$ is the free idempotent and commutative monoid on $k$ generators. It means that a monoid morphism $f: (P_k, \cup) \to (\{1, \ldots, n\}, \max)$ is uniquely and entirely determined by the values of $f$ on the singletons of $P_k$. Since there are $n$ possibilities for each singleton, the number of morphisms is $n^k$. For $n = 4$ and $k = 3$ you get $4^3 = 64$ (and not $100$) such morphisms.
EDIT. Let $A = \{a_1, a_2, \ldots, a_r\}$  be a subset of $\{1, \ldots, k\}$. Since $A = \{a_1\} \cup \ldots \cup \{a_r\}$, one gets
$$
f(A) = \max \bigl\{f(\{a_1\}), f(\{a_2\}), \ldots, f(\{a_r\})\bigr\}
$$
Thus the value of $f(A)$ is determined by the values of $f(\{i\})$ for $1 \leqslant i \leqslant k$. There are $n$ possible choices for the value of each $f(\{i\})$ and hence $n^k$ possibilities for $f$.
EDIT. This answer only works for nonempty subsets. See the other answer for a complete solution.
A: In this question, the empty set has to be considered separately. Let $P'_k$ be the set of nonempty subsets of $\{1, \dots, k\}$, let
$$
  m(f) = \min \{f(A) \mid A \in P'_k \}
$$
and let $A$ be a nonemptyset such that $f(A) = m(f)$.
Since
$$
m(f) = f(A) = f(A \cup \emptyset) = \max(f(A), f(\emptyset)) = \max(m, f(\emptyset))
$$
one gets necessarily $f(\emptyset) \leqslant m(f)$.
Moreover, $f$ has to be a semigroup morphism from the semigroup $(P'_k, \cup)$ to the semigroup $(\{1, \ldots, n\}, \max)$. Both semigroups are idempotent and commutative and $P'_k$ is the free idempotent and commutative semigroup on $k$ generators. It means that $f$ is uniquely and entirely determined by the values of $f$ on the singletons of $P'_k$. Indeed, if $A = \{a_1, a_2, \ldots, a_r\}$  is a subset of $\{1, \ldots, k\}$, one has
$$
f(A) = \max \bigl\{f(\{a_1\}), f(\{a_2\}), \ldots, f(\{a_r\})\bigr\}
$$
Now there are $(n-m+1)^k$ semigroup morphisms from $P'_k$ to $\{1, \ldots, n\}$ such that $m \leqslant m(f)$, since the image of such a function is a subset of $\{m, \ldots, n\}$. Among them, there are $(n-m+1)^k - (n-m)^k$ functions such that $m = m(f)$.
For each such function, one can choose for $f(\emptyset)$ any value $\leqslant m$. Altogether we get
\begin{align}
(n^k - (n-1)^k) + 2((n-1)^k - (n-2)^k) + 3 ((n-2)^k - (n-3)^k) + \dotsm + 1^k \\
= n^k + (n-1)^k  + (n-2)^k + \dotsm + 1^k
\end{align}
For $n = 4$ and $k = 3$ you get $4^3 + 3^3 + 2^3 + 1^3 = 64 + 27 + 8 + 1 = 100$.
