# Counting interpretation of $\sum^{n}_{i=0}\binom{n}{i}i^n$

$$\sum^{n}_{i=0}\binom{n}{i}i^n$$

I can't find a counting interpretation of this formula. I thought of using the binomial theorem but I don't think it applies here. So, I am not sure how to begin.

• oeis.org/A072034 Mar 21 '21 at 11:32
• @metamorphy I still don't understand. Mar 21 '21 at 16:22
• I got a very bad upper bound, something like $O(n^{n^2})$
– Alex
Mar 21 '21 at 17:56

I will provide a proof of the interpretation that the sum you've given counts the number of functions from $$[n]$$ to a subset of $$[n]$$ summed over all possible subsets(mentioned by @metamorphy) and also $$[n] = \{1,2,...,n\}$$.Consider a function $$f : [n] \to [i]$$ Each element of $$[n]$$ has $$i$$ choices to map to. So there are $$i^n$$ functions in this case. Also there are $$\dbinom{n}{i}$$ subsets of $$[n]$$ of cardinality $$i$$ from the definition of binomial coefficients. Summing over all possible subsets you get that the number of functions from $$[n]$$ into a subset of $$[n]$$ is $$\sum_{i=0}^{n} \binom{n}{i}i^n$$
• hi, why is $n^i$? Mar 21 '21 at 16:46
• @Strange is not supposed to be $i^n$ instead of $n^i$? Mar 21 '21 at 20:40
• If $A\subseteq B\subseteq[n]$, every function from $[n]$ to $A$ is automatically a function from $[n]$ to $B$, so the sum does not count functions from $[n]$ to subsets of $[n]$: it counts ordered pairs $\langle A,f\rangle$ such that $A\subseteq[n]$ and $f:A\to[n]$. Mar 21 '21 at 21:40