Stirling numbers of forests and cycles

Abstract

For a graph $G$ and a positive integer $k$, the {\em graphical Stirling number} $S(G,k)$ is the number of partitions of the vertex set of $G$ into $k$ non-empty independent sets. Equivalently it is the number of proper colorings of $G$ that use exactly $k$ colors, with two colorings identified if they differ only on the names of the colors. If $G$ is the empty graph on $n$ vertices then $S(G,k)$ reduces to $S(n,k)$, the familiar Stirling number of the second kind. In this note we first consider Stirling numbers of forests. We show that if $(F_n^{c(n)}{)}_{n\ge 0}$ is any sequence of forests with $F_n^{c(n)}$ having $n$ vertices and $c(n)=o(\sqrt{n/\log n})$ components, and if $X_n^{c(n)}$ is a random variable that takes value $k$ with probability proportional to $S(F_n^{c(n)},k)$ (that is, $X_n^{c(n)}$ is the number of classes in a uniformly chosen partition of $F_n^{c(n)}$ into non-empty independent sets), then $X_n^{c(n)}$ is asymptotically normal, meaning that suitably normalized it tends in distribution to the standard normal. This generalizes a seminal result of Harper on the ordinary Stirling numbers. Along the way we give recurrences for calculating the generating functions of the sequences $(S(F_n^c,k){)}_{k\ge 0}$, show that these functions have all real zeroes, and exhibit three different interlacing patterns between the zeroes of pairs of consecutive generating functions. We next consider Stirling numbers of cycles. We establish asymptotic normality for the number of classes in a uniformly chosen partition of $C_n$ (the cycle on $n$ vertices) into non-empty independent sets. We give a recurrence for calculating the generating function of the sequence $(S(C_n,k){)}_{k\ge 0}$, and use this to give a direct proof of a log-concavity result that had previously only been arrived at in a very indirect way.

17 pages