Combinatorially interpreting generalized Stirling numbers

The Stirling numbers of the second kind n k (counting the number of partitions of a set of size n into k non-empty classes) satisfy the relation ( x D ) n f ( x ) = ∑ k ≥ 0 n k x k D k f ( x ) where f is an arbitrary function and D is differentiation with respect to x . More generally, for every word w in alphabet { x , D } the identity w f ( x ) = x ( # ( x ’s in  w ) − # ( D ’s in  w ) ) ∑ k ≥ 0 S w ( k ) x k D k f ( x ) defines a sequence ( S w ( k ) ) k of Stirling numbers (of the second kind) of w . Explicit expressions for, and identities satisfied by, the S w ( k ) have been obtained by numerous authors, and combinatorial interpretations have been presented. e provide a new combinatorial interpretation that, unlike previous ones, retains the spirit of the familiar interpretation of n k as a count of partitions. Specifically, we associate to each w a quasi-threshold graph G w , and we show that S w ( k ) enumerates partitions of the vertex set of G w into classes that do not span an edge of G w . We use our interpretation to re-derive a known explicit expression for S w ( k ) , and in the case w = ( x s D s ) n to find a new summation formula linking S w ( k ) to ordinary Stirling numbers. We also explore a natural q -analog of our interpretation. case w = ( x r D ) n it is known that S w ( k ) counts increasing, n -vertex, k -component r -ary forests. Motivated by our combinatorial interpretation we exhibit bijections between increasing r -ary forests and certain classes of restricted partitions.