Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

5 Answers 5

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

share|improve this answer
1  
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
    
Thanks. I will correct it. –  Mike Spivey Dec 5 '12 at 19:26
up vote 3 down vote accepted

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.

share|improve this answer
    
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$.

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

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


share|improve this answer
    
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

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.