Combinatorial proof (for: $n, m \geq 0$)
$$\sum_{k=1}^n k^m = \sum_{i=1}^m {{n+1}\choose{i+1}} \ {m\brace i} \ i!$$
The story: we have $m$ elements and $n$ empty buckets.
LHS:
We put every element of set $[m]$ in one of $1, 2, 3, ..., n$ buckets.
RHS:
We choose from $n+1$ buckets $1, 2, 3, ... m+1$ of them (there may be as much elements as there are buckets).
We separate [m] elements in $1, 2, 3, ... m$ groups to put them in $1, 2, 3, ... m$ buckets. Then we exchange those groups in i! ways between buckets.
The thing that I don't get is why on the RHS do we choose $i+1$ buckets from $n+1$ available if there are only $n$ buckets in the story and we need only $m$ to put our groups inside of them.
The description "put every element of $[m]$ into one of $n$ buckets" does not correspond to $\sum_{k=1}^n k^m$. That would just be $n^m$. You need to choose a story which uses the summation variable, $k$.
Here is a solution.
LHS: This enumerates ordered pairs, $(k,L)$, where $k$ is an integer between $1$ and $n$, and $L$ is a list of length $m$ with entries in $[k]$. For each choice of $k$, there are $k^m$ choices for $L$. Summing over $k$, there are $\sum_{k=1}^n$ ways to choose $(k,L)$, as desired.
RHS: Let $i$ represent the number of distinct values in $L$. There are ${m\brace i}$ ways to partition the spots of the list into $i$ parts. Then, $\binom{n+1}{i+1}$ respresents choosing a subset, $S$, of $\{0,1,\dots,n\}$ of cardinality $i$. There are two cases two consider.
Suppose $0\notin S$. In this case, let $k=\max(S)$. This means $S\setminus\{k\}$ is a set of $i$ integers between $1$ and $n$. Then, $i!$ is the number of ways to choose a bijection between $S\setminus \{k\}$ and the $i$ parts defined by ${m\brace i}$. If a part is assigned number $x$, then all of the spots in $L$ will get the number $x$. This fully defines $L$, so we have obtained $(k,L)$.
If $0\in S$, then we let $k$ be the largest element of $S$. We then proceed as in the last bullet point, replacing $S\setminus \{k\}$ with $S\setminus \{0\}$.