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.

Solution 1:

$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$$

Solution 2:

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.

Solution 3:

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$.

Solution 4:

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.

Solution 5:

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:"