Document Type

Article

Language

eng

Publication Date

1-2019

Publisher

Elsevier

Source Publication

Journal of Combinatorial Theory, Series A

Source ISSN

0097-3165

Abstract

Given R⊆Nlet {nk}R, [nk]R, and L(n, k)Rcount the number of ways of partitioning the set [n] :={1, 2, ..., n}into knon-empty subsets, cycles and lists, respectively, with each block having cardinality in R. We refer to these as the R-restricted Stirling numbers of the second kind, R-restricted unsigned Stirling numbers of the first kind and the R-restricted Lah numbers, respectively. Note that the classical Stirling numbers of the second kind, unsigned Stirling numbers of the first kind, and Lah numbers are {nk}={nk}N, [nk]=[nk]Nand L(n, k) =L(n, k)N, respectively.It is well-known that the infinite matrices [{nk}]n,k≥1, [[nk]]n,k≥1and [L(n, k)]n,k≥1have inverses [(−1)n−k[nk]]n,k≥1,[(−1)n−k{nk}]n,k≥1and [(−1)n−kL(n, k)]n,k≥1respectively. The inverse matrices [{nk}R]−1n,k≥1, [[nk]R]−1n,k≥1and[L(n, k)R]−1n,k≥1exist and have integer entries if and only if 1 ∈R. We express each entry of each of these matrices as the difference between the cardinalities of two explicitly defined families of labeled forests. In particular the entries of[{nk}[r]]−1n,k≥1have combinatorial interpretations, affirmatively answering a question of Choi, Long, Ng and Smith from 2006.If we have 1, 2 ∈Rand if for all n ∈Rwith nodd and n ≥3, we have n ±1 ∈R, we additionally show that each entry of [{nk}R]−1n,k≥1, [[nk]R]−1n,k≥1and [L(n, k)R]−1n,k≥1is up to an explicit sign the cardinality of a single explicitly defined family of labeled forests. With Ras before we also do the same for restriction sets of the form R(d) ={d(r−1) +1 :r∈R}for all d ≥1. Our results also provide combinatorial interpretations of the kth Whitney numbers of the first and second kinds of Π1,dn, the poset of partitions of [n]that have each part size congruent to 1mod d.

Comments

Accepted version. Journal of Combinatorial Theory, Series A, Vol. 161 (January 2019): 271-298. DOI. © 2019 Elsevier. Used with permission.

Download
engbers_13244acc.docx (159 kB)
ADA Accessible Version

Share

COinS