Restricted r-Stirling Numbers and Their Combinatorial Applications

Abstract

We study set partitions with r distinguished elements and block sizes found in an arbitrary index set S . The enumeration of these ( S, r )-partitions leads to the introduc- tion of ( S, r )-Stirling numbers, an extremely wide-ranging generalization of the classical Stirling numbers and the r -Stirling numbers. We also introduce the associated ( S, r )-Bell and (S, r )-factorial numbers. We study fundamental aspects of these n umbers, including recurrence relations and determinantal expressions. For S with some extra structure, we show that the inverse of the ( S, r )-Stirling matrix encodes the M ?obius functions of two families of posets. Through several examples, we demonstrate th at for some S the matri- ces and their inverses involve the enumeration sequences of sever al combinatorial objects. Further, we highlight how the ( S, r )-Stirling numbers naturally arise in the enumeration of cliques and acyclic orientations of special graphs, underlining the ir ubiquity and im- portance. Finally, we introduce related ( S, r ) generalizations of the poly-Bernoulli and poly-Cauchy numbers, uniting many past works on generalized comb inatorial sequences.