Generating Function of Ordered Stirling Number of the Second Kind

Question

Let $S(n,k)$ be the Stirling Number of the Second Kind, which counts the number of partitions that divide $\{1,\ldots,n\}$ into $k$ nonempty subsets. Then $k! S(n,k)$ may be interpreted as an ordered version of $S(n,k)$, which counts the number of ways of assigning the elements of $\{1,\ldots,n\}$ to $k$ nonempty labeled groups.

I am interested in finding an interpretation of the generating function $$ G_n(t)=\sum_{k=1}^n k! S(n,k) t^k,\quad t>0. $$

E.g., if $k!$ were absent, then it would lead to the Touchard Polynomials which are moments of a Poisson distribution.

Answer 1

Number of onto functions from [n] to [k]

You can find it using inclusion-exclusion, or the generating function will give you the same.

Answer 2

We write $G_n(t)=\sum_{k=0}^n S(n,k)k!t^k$. This agrees with your definition when $n\geq 1$. For $n=0$, we have $G_0(t)=1$. If $t$ is a positive integer, then $G_n(t)$ is the number of ways to partition $[n]=\{1,2,\ldots, n\}$ into $k\leq n$ parts and give each part a colored label, where there are $t$ available colors and $k$ labels. This $G_n(t)$ is called Fubini polynomial. We have an exponential generating function of Stirling numbers of the second kind: $$ \sum_{n=k}^{\infty} S(n,k)k! \frac{x^n}{n!} = (e^x-1)^k. $$

Applying this, we may find a bivariate generating function: $$ \sum_{k=0}^{\infty}\sum_{n=k}^{\infty} S(n,k)k! t^k\frac{x^n}{n!}=\sum_{k=0}^{\infty} (e^x-1)^k t^k = \frac1{1-t(e^x-1)}. $$

Thus, by switching the order of summation, we have $$ \sum_{n=0}^{\infty} G_n(t)\frac{x^n}{n!} = \frac1{1-t(e^x-1)} $$ with the absolute convergence is provided when $|t(e^x-1)|<1$.

The polynomial $G_n(t)$ enjoys a few nice properties.

We have $G_n(-1)=(-1)^n$. This can be proved through a polynomial identity for Stirling numbers (Theorem 0.1 in my note below). This also has a beautiful combinatorial proof by Grigory M here

By the recurrence relation $S(n+1,k)=kS(n,k)+S(n,k-1)$, we have $$ S(n+1,k)k!=k\big(S(n,k)k!+S(n,k-1)(k-1)!\big).$$ This gives the following recurrence of $G_n(t)$: $$ G_{n+1}(t)=tG_n'(t)+t\big(tG_n(t)\big)' = t\big(G_n(t)+(t+1)G_n'(t)\big) $$ $$ =t\big((t+1)G_n(t)\big)'. $$

Using $G_1(t)=t$ has one real root, we can prove by the above recurrence, Rolle's theorem, and induction on $n$ that $G_n(t)=0$ has $n$ distinct real root for $n\geq 1$. Of course one of the real root is zero, the other roots are negative.

Moreover, by Newton's inequality, the coefficient sequence of $G_n(t)$ is log-concave, and hence unimodal.

There is a symmetry for $F_n(t)=G_n(t)/t$ about $t=-1/2$. We have for $n\geq 1$,

$$F_n(t)=(-1)^{n-1}F_n(-t-1).$$

I wrote proof of this identity (R. Stanley "Enumerative Combinatorics" volume 1, Chapter 3-Exercise 141(d)) here: http://www.csun.edu/~sungjin/SJK_StirlingS2.pdf

There is a combinatorial proof relying solely on $G_n(-1)=(-1)^n$. This is done by first proving $$ S(n,r+1)(r+1)!=\sum_{k=r+1}^n S(n,k)k!(-1)^{n-k}\binom{k-1}{r} $$ considering the identity $G_m(-1)=(-1)^m$ for each partitioned blocks of $[n]$ whose size is $m$.

Therefore, the distinct $n$ real roots of $G_n(t)$ except for $0$ must be symmetric about $t=-1/2$. Since $F_n(t)$ is increasing for $t\geq 0$, there are no roots in $t\leq -1$. Hence, all real roots of $F_n(t)$ are distinct and in $(-1,0)$ interval.