Enumeration of smooth inversion sequences and proof of a recent related conjecture. Issue 3 (4th March 2023)

• Record Type: Journal Article
• Authors: Mansour, Toufik; Shattuck, Mark
• Is Part Of: Journal of difference equations and applications. Volume 29:Issue 3(2023)
• Page Start: 270
• Page End: 296
• Publication Date: 2023-03-04
• Subjects: Inversion sequence -- smooth sequence -- generating function -- Catalan number; 05A15 -- 05A05; Difference equations -- Periodicals; 515.625
• DOI: 10.1080/10236198.2023.2193659
• Languages: English
• ISSNs: 1023-6198

Abstract

ABSTRACT: Let I n denote the set consisting of integer sequences π = π 1 … π n such that 0 ≤ π i < i for all i, which are referred to as inversion sequences. In this paper, we enumerate members of I n whose consecutive differences are bounded in three different ways: | π i + 1 − π i | ≤ 1, π i + 1 − π i ≤ 1 and π i + 1 − π i ≥ − 1 for all i . In the first two cases, the corresponding subsets of I n have cardinality given by the enumerator of the so-called Motzkin left-factors of length n −1 and by the Catalan number C n for all n ≥ 1, respectively. In the third case, the subset of I n is equinumerous with the set of rooted tandem duplication trees on n gene segments, which arise in applications to DNA research. Using our results from this case, we establish a conjecture concerning the enumerator of a certain class of Catalan restricted growth sequences. Finally, new polynomial generalizations of the underlying counting sequences are obtained in the first two cases above by considering the joint distribution of parameters on the corresponding subsets of I n .