Combinatorial formulas for restricted Stirling and Lah number matrices and their inverses
- April 7, 2017
- 2:30 p.m.
- LeConte 312
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 many 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 two combinatorial interpretations of the coefficients of the compositional inverse of a power series expressed in terms of trees.
This is joint work with David Galvin of the University of Notre Dame and John Engbers of Marquette University.