Sum of product of certain binomial coefficients: $\sum\limits_{m = 0}^k \sum\limits_{n = 0}^m \binom{k}{m} \binom mn$ 
Given a nonnegative integer $k$. What is the value of the following sum:
  $$\sum_{m = 0}^k \sum_{n = 0}^m \binom{k}{m} \binom{m}{n}$$

I need this in order to simplify some of my work. I tried to expand it using binomial formula but didn't lead anywhere. I am simplifying weyl denominator formula for certain Kac-Moody algebras and I end up with this sum.
 A: $${k\choose m}{m \choose n} = {k!\over m!(k-m)!}{m!\over n!(m-n)!}={k\choose k-m,n,m-n}$$ so we have $$\sum_{m=0}^k\sum_{n=0}^m{k\choose k-m,n,m-n}=3^k,$$ the number of ways to distribute $k$ objects in $3$ piles.
A: The  sum $$S=\sum_{m=0}^{k} \sum_{n=0}^{m} {k \choose m}{m \choose n}=\sum_{m=0}^{k} {k  \choose m}\sum_{n=0}^{m} {m \choose n}= \sum_{m=0}^{k} 2^m {k \choose m}=3^k.$$
A: The answer given by @saulspatz is correct. I would like to give an alternative way to get to the result that helps understanding what is actually going on.

The binomial coefficient $\binom{k}{m}$ is the number of ways in which we can choose $m$ elements out of a set of $k$ elements. In other words, it is the number of elements of the set
$$\{f:\{x_1,\ldots,x_k\}\to\{1,2\}\mid \#f^{-1}(2)=m\}.$$
Of course, we have a similar interpretation for $\binom{m}{n}$. Thus,
\begin{align}
\binom{k}{m}\binom{m}{n} ={}& \#\{f:\{x_1,\ldots,x_k\}\to\{0,1\}\mid \#f^{-1}(0)=m\}\cdot\#\{g:f^{-1}(0)\to\{2,3\}\mid \#g^{-1}(3)=n\}\\
={}&\#\{(f,g)\mid\#f^{-1}(0)=m,\ \#g^{-1}(3)=n\}
\end{align}
(I've omitted the domains and codomains of the maps in the last line). Now, given two such maps we can construct
$$h:\{x_1,\ldots,x_k\}\longrightarrow\{1,2,3\}$$
as the map given by $f$ on $f^{-1}(1)$ and $g\circ f$ otherwise, thus giving
$$\binom{k}{m}\binom{m}{n}=\#\{h:\{x_1,\ldots,x_k\}\to\{1,2,3\}\mid h^{-1}(3)=n,\ h^{-1}(2)=m-n\}\ .$$
Taking the sum over $m$ and $n$ is given by taking the union on the sets we are counting, which eliminates the conditions giving
$$\sum_{m=0}^k\sum_{n=0}^m\binom{k}{m}\binom{m}{n} = \#\{h:\{x_1,\ldots,x_k\}\to\{1,2,3\}\} = 3^k.$$
