Count the number of choice functions We call a choice function on a universe $U$ a function $f : 2^U \longrightarrow 2
^U$ such that $f (A) \subseteq A$, for every $A \subseteq U$.
Find the number of choice functions on a universe $U$ with $|U| = n$.
My approach: Let $A$ a fixed subset of $U$ with $|A| = k$. Number of functions from $A$ to $A$ is $k^k$ such that $f(A) \subseteq A$. Knowing the fact the there are $C^k_n$ such sets $A$, then the total number is 
$$\sum_{k=0}^n C^k_n \cdot k^k$$ functions. But I think I made some mistakes because that's not the answer. Any hints on where I made mistakes?
 A: To determine what $f$ does on any given subset $A$, you're not choosing a function $A \to A$: rather, you're choosing a single value $f(A)$, and we're given that $f(A)$ is a set with $f(A) \subseteq A$.
So, if $|A|=k$, then there are $2^k$ ways to pick $f(A)$, because there are $2^k$ subsets of $A$.
The other thing that's going wrong is that if you have $2^{|A_1|}$ ways to pick $f(A_1)$ and $2^{|A_2|}$ ways to pick $f(A_2)$, there are not $2^{|A_1|} + 2^{|A_2|}$ but $2^{|A_1|} \cdot 2^{|A_2|}$ ways to pick both of them: we should be multiplying, not adding. (I also missed this: thank you @NickPavlov for catching my mistake!) So you should combine these values by taking the product
$$\prod_{A \subseteq U}2^{|A|} = 2^{\sum_{A \subseteq U}|A|}$$
where the exponent simplifies as
$$\sum_{A \subseteq U} A = \sum_{k=0}^n \binom nk \cdot k = \sum_{k=0}^n n \binom{n-1}{k-1} = n \cdot 2^{n-1}$$
making $2^{n \cdot 2^{n-1}}$ our final answer.

Another way to get this answer, which involves less trickery with binomial sums, is the following approach. For each element $x \in U$, there are $2^{n-1}$ subsets containing $x$, and for each $A$ such that $x\in A$, we have a choice to make: will $f(A)$ contain $x$ or not? Once we've made this choice for each $x \in U$ and for each $A$ containing $x$, we've specified the function $f$ completely.
Since there are $2^{n-1}$ binary choices about subsets of $U$ containing $x$, there are $2^{2^{n-1}}$ ways to make all the choices that involve $x$. Now we multiply this number over all $x \in \{1, 2, \dots, n\}$, getting
$$\left(2^{2^{n-1}}\right)^n = 2^{n \cdot 2^{n-1}}$$
as our final answer.
