Stirling Binomial Polynomial Let $\{\cdot\}$ denote Stirling Numbers of the second kind. Let $(\cdot)$ denote the usual binomial coefficients. It is known that $$\sum_{j=k}^n {n\choose j} \left\{\begin{matrix} j \\ k \end{matrix}\right\} = \left\{\begin{matrix} n+1 \\ k+1 \end{matrix}\right\}.$$ Note: The indexes for $j$ aren't really needed since the terms are zero when $j>n$ or $j<k$. 
How do I calculate $$\sum_{j=k}^n 4^j{n\choose j} \left\{\begin{matrix} j \\ k \end{matrix}\right\} = ?$$ I have been trying to think of this sum as some special polynomial (maybe a Bell polynomial of some kind) that has been evaluated at 4. 
I have little knowledge of Stirling Numbers in the context of polynomials. Any help would be appreciated; even a reference to a comprehensive book on Stirling Numbers and polynomials. 
 A: It appears we  can give another derivation of the  closed form by @vadim123 for the
sum $$q_n = \sum_{j=k}^n m^j {n\choose j} {j \brace k}$$
using the bivariate generating function of the Stirling numbers of the
second kind. This computation illustrates generating function techniques as presented in Wilf's generatingfunctionology as well as the technique of annihilating coefficient extractors.
Recall the species for set partitions which is
$$\mathfrak{P}(\mathcal{U} \mathfrak{P}_{\ge 1}(\mathcal{Z}))$$
which gives the generating function
$$G(z, u) = \exp(u(\exp(z)-1)).$$
Introduce the generating function
$$Q(z) = \sum_{n\ge k} q_n \frac{z^n}{n!}.$$
We thus have
$$Q(z) = \sum_{n\ge k} \frac{z^n}{n!}
\sum_{j=k}^n m^j {n\choose j} {j \brace k}.$$
Substitute $G(z, u)$ into the sum to get
$$Q(z) = \sum_{n\ge k} \frac{z^n}{n!}
\sum_{j=k}^n m^j {n\choose j} 
j! [z^j] \frac{(\exp(z)-1)^k}{k!}
\\ = \sum_{j\ge k} m^j \left([z^j] \frac{(\exp(z)-1)^k}{k!}\right)
\sum_{n\ge j} j!  \frac{z^n}{n!} {n\choose j}
\\ = \sum_{j\ge k} m^j \left([z^j] \frac{(\exp(z)-1)^k}{k!}\right)
\sum_{n\ge j}  \frac{z^n}{(n-j)!}
\\= \sum_{j\ge k} m^j \left([z^j] \frac{(\exp(z)-1)^k}{k!}\right)
z^j \sum_{n\ge j}  \frac{z^{n-j}}{(n-j)!}
\\ = \exp(z)
\sum_{j\ge k} m^j z^j \left([z^j] \frac{(\exp(z)-1)^k}{k!}\right).$$
Observe that the sum annihilates the coefficient extractor, producing
$$Q(z) = \exp(z)\frac{(\exp(mz)-1)^k}{k!}.$$
Extracting coefficients from $Q(z)$ we get
$$q_n = \frac{n!}{k!} 
[z^n] \exp(z) 
\sum_{q=0}^k {k\choose q} (-1)^{k-q} \exp(mqz)
\\ = \frac{n!}{k!} 
[z^n] \sum_{q=0}^k {k\choose q} (-1)^{k-q} \exp((mq+1)z)
= \frac{n!}{k!} 
\sum_{q=0}^k {k\choose q} (-1)^{k-q} \frac{(mq+1)^n}{n!}
\\ = \frac{1}{k!} 
\sum_{q=0}^k {k\choose q} (-1)^{k-q} (mq+1)^n.$$
Note that when $m=1$ $Q(z)$ becomes
$$\exp(z)\frac{(\exp(z)-1)^k}{k!}
= \frac{(\exp(z)-1)^{k+1}}{k!}
+ \frac{(\exp(z)-1)^k}{k!}$$
so that
$$[z^n] Q(z) = (k+1){n\brace k+1} + {n\brace k}
= {n+1\brace k+1},$$
which can also be derived using a very simple combinatorial argument.
Addendum. 
Here is another derivation of the formula for $Q(z).$
Observe that when we  multiply two exponential generating functions of
the sequences $\{a_n\}$ and $\{b_n\}$ we get that
$$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} 
\sum_{n\ge 0} b_n \frac{z^n}{n!}
= \sum_{n\ge 0} 
\sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\
= \sum_{n\ge 0} 
\sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!}
= \sum_{n\ge 0} 
\left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$
i.e. the  product of  the two generating  functions is  the generating
function of $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$
(I have included this derivation in several of my posts.)
Now in the present case we have
$$A(z) = \sum_{j\ge k} {j\brace k} m^j \frac{z^j}{j!}
\quad\text{and}\quad
B(z) = \sum_{j\ge 0} \frac{z^j}{j!} = \exp(z).$$
Evidently $A(z)$  is just the exponential generating  function for set
partitions into $k$ sets evaluated at $mz,$ so we get
$$A(z) = \frac{(\exp(mz)-1)^k}{k!}$$
and with $Q(z) = A(z) B(z)$ the formula for $Q(z)$ follows.
A: This is as far as I got; for small $n$ or small $k$ I can work out what this is.
$$\sum_j 4^j{n\choose j} \left\{\begin{matrix} j \\ k \end{matrix}\right\}=$$
$$\sum_j 4^j{n\choose j} \frac{1}{k!}\sum_i(-1)^{k-i}{k\choose i} i^j=$$
$$\sum_i  \frac{1}{k!}(-1)^{k-i}{k\choose i} \sum_j (4i)^j{n\choose j} =$$
$$\frac{(-1)^k}{k!}\sum_i  (-1)^{i}{k\choose i} (4i+1)^n $$
A: One can continue vadim123's approach with the ideas presented here (A sum with binomial coefficients).
