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

1. Does this sum simplify?
2. Can someone give a nice interpretation of this sum? (Perhaps a combinatorial one?)
3. Does anyone know any references involving this sum?

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

1. 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.
2. 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.
3. 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.
4. 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.

• I am not so sure what you want, the combinatorial interpretation is directly readable from the sum (as well as from the generating function): Partition $n$ elements in some subsets, select one of the subsets and weight it with $x^{subset size}$. (You have 1/x instead of x, but this does not change much.) – Phira Dec 5 '12 at 18:18
• @Phira: Maybe I'm just rusty or having a mentally off day - would you mind posting the combinatorial interpretation as an answer? You'll get my upvote at least. – Mike Spivey Dec 5 '12 at 18:20
• I was just typing, after hitting enter to get a newline. – Phira Dec 5 '12 at 18:20
• Note that I don't say that you should be happy with this, but if you expect as answer something like involutions or trees, they would still have to have some weight to give the $x$. – Phira Dec 5 '12 at 18:22
• @Phira: Your combinatorial interpretation makes sense. Ugh. I am rusty. I would still take that as an answer to my second question, although I would love to hear about it if you come up with something else, too. – Mike Spivey Dec 5 '12 at 18:32

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

• Change $(-1)^k$ to $(-1)^{j-k}$, and your expression does appear to hold for the few values of $x$ that I just tested. How would you prove that formula? :) – Mike Spivey Dec 5 '12 at 18:58
• Sorry about that misprint $(-1)^k$, I corrected it now. I suspect that you may be able to prove it from your recurrence (which, btw, is missing an $x$ in the term $x S(n-1,k-1,x)$) – Robert Israel Dec 5 '12 at 19:25

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.

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

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

3. 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.)

4. 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.)

5. There are recurrence relations, generating functions, and orthogonality relations with the non-central Stirling numbers of the first kind in Section 8.5.

• Very nice. I did not expect interpretation 2. (+1) – user26872 Dec 8 '12 at 1:41
• @oen: Thanks. I was surprised myself. – Mike Spivey Dec 8 '12 at 14:52

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

• Looks good! Thanks, oen. – Mike Spivey Dec 5 '12 at 21:48
• @MikeSpivey: Glad to help. Cheers! – user26872 Dec 5 '12 at 22:26

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.

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

• Interesting! Thanks. As I said in the comments, I believe this is equivalent to replacing $x^j$ with $x^{j-k}$ in the formula for $S(n,k,x)$. – Mike Spivey Dec 7 '12 at 21:01