Journal of Combinatorics

Volume 8 (2017)

Number 3

Guest Editor: Steve Butler (Iowa State University)

A note on $p$-ascent sequences

Pages: 487 – 506

DOI: https://dx.doi.org/10.4310/JOC.2017.v8.n3.a5

Authors

Sergey Kitaev (University of Strathclyde, Glasgow, Scotland, United Kingdom)

Jeffrey B. Remmel (University of California at San Diego)

Abstract

Ascent sequences were introduced by Bousquet-Mélou, Claesson, Dukes, and Kitaev in [1], who showed that ascent sequences of length $n$ are in $1\textrm{-to-}1$ correspondence with $(2 + 2)$-free posets of size $n$. In this paper, we introduce a generalization of ascent sequences, which we call $p$-ascent sequences, where $p \geq 1$. A sequence $(a_1, \dotsc , a_n)$ of non-negative integers is a $p$-ascent sequence if $a_0 = 0$ and for all $i \geq 2$, $a_i$ is at most $p$ plus the number of ascents in $(a_1 , \dotsc , a_{i-1})$. Thus, in our terminology, ascent sequences are $1$-ascent sequences. We generalize a result of the authors in [9] by enumerating $p$-ascent sequences with respect to the number of $0$s. We also generalize a result of Dukes, Kitaev, Remmel, and Steingrímsson in [4] by finding the generating function for the number of $p$-ascent sequences which have no consecutive repeated elements. Finally, we initiate the study of pattern-avoiding $p$-ascent sequences.

Partially supported by NSF grant DMS 0654060.

Received 24 July 2015

Published 21 June 2017