Consecutive patterns in Catalan words and the descent distribution
This paper studies the descent statistic in Catalan words avoiding a consecutive pattern of length \(3\). A Catalan word is a word \(w = w_1w_2\cdots w_n\) over the set of nonnegative integers with \(w_1 = 0\) and \(w_{i} \leq w_{i-1} + 1\) for all \(i \geq 2\). It is well known that the number of Catalan words of length \(n\) is the Catalan number \(\frac{1}{n+1}\binom{2n}{n}\). A Catalan word \(w\) is said to avoid a consecutive pattern \(p = \underline{p_1p_2\cdots p_k}\) if there is no consecutive subsequence \(w_iw_{i+1} \cdots w_{i+k-1}\) that is order-isomorphic to \(p\). Every Catalan word avoids \(\underline{021}\) and \(\underline{102}\) by definition, leaving eleven possible consecutive patterns of length \(3\) for which enumerating Catalan words avoiding the pattern is meaningful. In each of these cases, the authors determine a bivariate generating function for Catalan words avoiding the pattern, with the second variable marking the number of descents. From this, they also derive the generating function for the total number of descents in each case. As it turns out, the patterns \(\underline{001}\) and \(\underline{011}\) lead to the same generating function, as do the three patterns \(\underline{100},\underline{110}\) and \(\underline{120}\). Thus there are only eight distinct bivariate generating functions that occur.
- Analytic combinatorics
- Catalan Numbers
- Catalan words avoiding pairs of length three patterns
- Consecutive patterns in inversion sequences
- Consecutive patterns in permutations
- Consecutive permutation patterns in trees and mappings
- Counting lattice points on bargraphs of Catalan words
- Counting strings in Dyck paths
- Descent distribution on Catalan words avoiding a pattern of length at most three
- Efficient generation of restricted growth words
- scientific article; zbMATH DE number 2024859 (Why is no real title available?)
- scientific article; zbMATH DE number 1919509 (Why is no real title available?)
- Pattern avoidance in binary trees
- Permutations and words counted by consecutive patterns
- Statistics on bargraphs of Catalan words
- The descent statistic on 123-avoiding permutations
- The descent statistic on signed simsun permutations
- Words restricted by 3-letter generalized multipermutation patterns
- Catalan words avoiding pairs of length three patterns
- Descent distribution on Catalan words avoiding ordered pairs of relations
- Consecutive pattern-avoidance in Catalan words according to the last symbol
- Last symbol distribution in pattern avoiding Catalan words
- Enumerating runs, valleys, and peaks in Catalan words
- Counting subword patterns in Catalan words
- Subword patterns in smooth words
- Avoidance of vincular patterns by Catalan words
- Avoidance of binary patterns by Catalan words
- Enumeration of consecutive patterns in flattened Catalan words
This page was built for publication: Consecutive patterns in Catalan words and the descent distribution
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6133614)
