Given a set R of natural numbers let S(n,k,R) be the restricted Stirling number of the second kind: the number of ways of partitioning a set of size n into k non-empty subsets with the sizes of these subsets restricted to lie in R. Let S(R) be the matrix with S(n,k,R) in its (n,k) entry. If R contains 1, S(R) has an inverse T(R) with integer entries. We find that, for many R, the entries T(n,k,R) of T(R) are expressible (up to sign) as the cardinalities of explicitly defined sets of trees and forests. For example, this is the case when R has no exposed odds, i.e. R contains 1 and 2 and R never contains an odd number n greater than 1 without also containing n+1 and n-1. We have similar results for restricted Stirling numbers of the first kind (partitions into cycles) and Lah numbers (partitions into ordered lists). Our proofs depend in part on a combinatorial formula for the coefficients of the compositional inverse of a power series.
This is joint work with David Galvin of the University of Notre Dame and John Engebers of Marquette University.