The sum $\sum_{j=0}^n \binom{n}{j} \left\{ j \atop k \right\} x^j$ A recent answer of mine to a question on Math Overflow includes the sum $$S(n,k,x) = \sum_{j=0}^n \binom{n}{j} \left\{ j \atop k \right\} x^j,$$ where $\left\{ j \atop k \right\}$ is a Stirling number of the second kind and $x$ is real.

Questions, in order of interest:

*

*Does this sum simplify?

*Can someone give a nice interpretation of this sum?  (Perhaps a combinatorial one?)

*Does anyone know any references involving this sum?


Here's are some things I've dug up.

*

*When $x = 1$, we get $$\sum_{j=0}^n \binom{n}{j} \left\{ j \atop k \right\} = \left\{ n+1 \atop k+1 \right\}.$$
This is formula 6.15, p. 265, of Concrete Mathematics.

*When $x = 2$, we get sequence A154537 in the OEIS.  There's another formula there.  However, the numbers with $x = 3$ are not in the OEIS.

*If my calculations are correct, $S(n,k,x)$ has the bivariate generating function $$\sum_{n,k \geq 0} S(n,k,x) \, y^k \frac{z^n}{n!} = e^{z + y (e^{xz}-1)}.$$
This agrees with the generating function in the OEIS entry for the $x = 2$ case.

*The sum satisfies the recurrence $$S(n,k,x) = (xk+1)S(n-1,k,x) + x S(n-1,k-1,x) + [n=k=0].$$
These are all interesting facts, but I would like to put some kind of interpretation on the sum or place it in some larger context.
 A: $S(i,0,x) = 1$ for nonnegative integers $i$.
$S(i,1,x) = (x+1)^i-1$
$S(i,2,x) = \dfrac{(2x+1)^i - 2 (x+1)^i + 1}{2}$
It looks to me like 
$$ S(i,j,x) = \frac{1}{j!} \sum_{k=0}^j (-1)^{j+k} {j \choose k} (kx+1)^i$$
A: It appears I was (in a sense) asking the wrong question.  The "right" question would have been to ask about the closely related numbers $T(n,k,x)$, where $$T(n,k,x) = \sum_{j=0}^n \binom{n}{j} \left\{ j \atop k \right\} x^{n-j}.$$
We have $S(n,k,x) = x^n T(n,k,1/x).$
Charalambides' Enumerative Combinatorics calls the $T(n,k,x)$ numbers the non-central Stirling numbers of the second kind.  Section 8.5 is devoted to the non-central Stirling numbers of both kinds, and they appear in a few other places in his book, too.


*

*In Section 8.5, there's the $T(n,k,x)$ version of the formula conjectured by Robert Israel and proved by oen: $$T(n,k,x) = \frac{1}{k!}\sum_{j=0}^k (-1)^{k-j} \binom{k}{j} (x+j)^n.$$

*Charalambides defines $T(n,k,x)$ as the coefficients obtained when converting from $(t+x)^n$ to falling factorial powers of $t$: $$(t+x)^n = \sum_{k=0}^n T(n,k,x) t^{\underline{k}}.$$

*Let $W_{n+x} = \{w_1, w_2, \ldots, w_{n+x}\}$, and let $W_x = \{w_1, w_2, \ldots, w_x\}$.  Then $T(n,k,x)$ counts the number of permutations of $W_{n+x}$ that are decomposed into $k+x$ ordered cycles such that the $x$ elements of the set $W_x$ belong in $x$ distinct cycles.  (See p. 474.)

*The number of ways to distribute $n$ distinguishable balls into $x$ distinguishable urns so that, out of $s$ specified urns, $k$ are occupied, is $s^{\underline{k}} \, T(n,k,x-s)$.  (See p. 341.)

*There are recurrence relations, generating functions, and orthogonality relations with the non-central Stirling numbers of the first kind in Section 8.5.
A: A proof of the formula given by @RobertIsrael: 
$$\begin{align*}
S(n,k,x) &= \sum_{j=0}^n {n\choose j} \left\{j\atop k\right\} x^j \\
&= \sum_{j=0}^n {n\choose j}
\left[
    \frac{1}{k!} \sum_{l=0}^k (-1)^{k-l}{k\choose l} l^j
\right] x^j \\
&= \frac{1}{k!} \sum_{l=0}^k (-1)^{k-l} {k\choose l} \sum_{j=0}^n {n\choose j}(l x)^j \\
&= \frac{1}{k!} \sum_{l=0}^k (-1)^{k-l} {k\choose l} (1+l x)^n
\end{align*}$$
I've reproduced your formula for the generating function using this representation for $S$. 
A: It may interest  the reader that the generating  function $P(z, y)$ of
this  sum  can  be  evaluated  using  the  technique  of  annihilated
coefficient extractors (ACE).

Start by  recalling the bivariate generating function  of the Stirling
numbers of the second kind, which is
$$G(w, u) = \exp(u(\exp(w) -1)).$$

Now  the sum  is $$\sum_{j=0}^n  {n\choose j}  {j\brace  k} x^{n-j}.$$
Therefore the ordinary generating  function of the possible values for
$n$ fixed and $k$ a parameter is
$$\sum_{j=0}^n  {n\choose j} \sum_{k=0}^j y^k {j\brace  k} x^{n-j}.$$

This gives for $P(z, y)$ the form
$$P(z, y) =
\sum_{n\ge 0} \frac{z^n}{n!}
\sum_{j=0}^n  {n\choose j} \sum_{k=0}^j y^k {j\brace  k} x^{n-j}.$$
Using $G(w, u)$ this becomes
$$\sum_{n\ge 0} \frac{z^n}{n!}
\sum_{j=0}^n  {n\choose j} 
\sum_{k=0}^j y^k x^{n-j} \times j! [w^j][u^k] \exp(u(\exp(w) - 1)).$$
This simplifies to
$$\sum_{n\ge 0} z^n
\sum_{j=0}^n  \frac{1}{(n-j)!}
\sum_{k=0}^j y^k x^{n-j} \times [w^j] \frac{(\exp(w) - 1)^k}{k!}$$
or
$$\sum_{n\ge 0} z^n
\sum_{j=0}^n  \frac{x^{n-j}}{(n-j)!}
\sum_{k=0}^j y^k \times [w^j] \frac{(\exp(w) - 1)^k}{k!}.$$
Now reverse the order of the three sums to get
$$\sum_{k\ge 0} y^k 
\sum_{j\ge k} [w^j] \frac{(\exp(w) - 1)^k}{k!}
\sum_{n\ge j} z^n  \frac{x^{n-j}}{(n-j)!}$$
which is
$$\sum_{k\ge 0} y^k 
\sum_{j\ge k} z^j [w^j] \frac{(\exp(w) - 1)^k}{k!}
\sum_{n\ge j} z^{n-j}  \frac{x^{n-j}}{(n-j)!}$$
or
$$\exp(xz) \sum_{k\ge 0} y^k 
\sum_{j\ge k} z^j [w^j] \frac{(\exp(w) - 1)^k}{k!}.$$
The inner  sum is the promised annihilated  coefficient extractor and
transforms into
$$\exp(xz) \sum_{k\ge 0} y^k \frac{(\exp(z) - 1)^k}{k!}$$
which finally yields
$$P(z, y) = \exp(xz) \exp(y (\exp(z) - 1)).$$
Observe that with $x=1$ we obtain
$$\exp(z) \exp(y (\exp(z) - 1))$$
which we immediately recognize as the combinatorial species
$$\mathfrak{P}(\mathcal{Z}) \times 
\mathfrak{P}(\mathcal{Y}\times \mathfrak{P}_{\ge 1}(\mathcal{Z})).$$
This amounts to taking $n$  labelled elements and choosing some subset
of  them, possibly empty,  to mark,  and partition  the rest  into $k$
non-empty subsets which indeed has the count
$$\sum_{j=0}^n  {n\choose j}  {j\brace  k}.$$
There is another annihilated coefficient extractor at this
MSE link.
A: I do the following in Pari/GP.
Let P denote the lower triangular Pascalmatrix
containing the binomial coefficients: 
$$ \small \begin{array} {} 
 1 & . & . & . & . \\
 1 & 1 & . & . & . \\
 1 & 2 & 1 & . & . \\
 1 & 3 & 3 & 1 & . \\
 1 & 4 & 6 & 4 & 1
 \end{array} $$
S2 the lower triangular matrix of Stirling numbers second kind $$ \small \begin{array} {rrrr}
 1 & . & . & . & . \\
 0 & 1 & . & . & . \\
 0 & 1 & 1 & . & . \\
 0 & 1 & 3 & 1 & . \\
 0 & 1 & 7 & 6 & 1
 \end{array} $$
 and $V(x)$ a diagonal matrix containing the consecutive powers of x $diag(1,x,x^2,x^3,...)$
then the following gives some answers to 2), where your question is referred, if instead of the similarity-transformation of the $S2$-matrix the rhs-postmultiplication $V(x)^{-1}$ were deleted: 

$$ P \cdot \left( V(1)  \cdot S2  \cdot V(1)^{-1} \right) = \small \begin{array} {rrrr}
 1 & . & . & . & . \\
 1 & 1 & . & . & . \\
 1 & 3 & 1 & . & . \\
 1 & 7 & 6 & 1 & . \\
 1 & 15 & 25 & 10 & 1
 \end{array} $$ (S2, upshifted)

$$ P \cdot \left( V(2)  \cdot S2  \cdot V(2)^{-1} \right) = \small \begin{array} {rrrr}
 1 & . & . & . & . \\
 1 & 1 & . & . & . \\
 1 & 4 & 1 & . & . \\
 1 & 13 & 9 & 1 & . \\
 1 & 40 & 58 & 16 & 1
 \end{array} $$ 
in: http://oeis.org/A039755 "B-Analogues of Stirling numbers 2nd kind"

$$ P \cdot \left( V(3)  \cdot S2  \cdot V(3)^{-1} \right) = \small \begin{array} {rrrr}
 1 & . & . & . & . \\
 1 & 1 & . & . & . \\
 1 & 5 & 1 & . & . \\
 1 & 21 & 12 & 1 & . \\
 1 & 85 & 105 & 22 & 1
 \end{array}$$
in: http://oeis.org/A111577 , Galton table

$$ P \cdot \left( V(4)  \cdot S2  \cdot V(4)^{-1} \right) = \small \begin{array} {rrrr}
 1 & . & . & . & . \\
 1 & 1 & . & . & . \\
 1 & 6 & 1 & . & . \\
 1 & 31 & 15 & 1 & . \\
 1 & 156 & 166 & 28 & 1
 \end{array} $$
in: http://oeis.org/A111578 (no name)

$$ P \cdot \left( V(5)  \cdot S2  \cdot V(5)^{-1} \right) = \small \begin{array} {rrrr}
 1 & . & . & . & . \\
 1 & 1 & . & . & . \\
 1 & 7 & 1 & . & . \\
 1 & 43 & 18 & 1 & . \\
 1 & 259 & 241 & 34 & 1
 \end{array}  $$
in: http://oeis.org/A166973 "A generalized recursion:"


