Restricted growth function patterns and statistics

DOI10.1016/J.AAM.2018.05.002zbMATH Open1393.05008arXiv1605.04807OpenAlexW2963778499WikidataQ129776655 ScholiaQ129776655MaRDI QIDQ1661480FDOQ1661480

Authors: Lindsey R. Campbell, Samantha Dahlberg, Robert Dorward, Jonathan Gerhard, Carlin Purcell, Bruce E. Sagan, Thomas L. Grubb 

Publication date: 16 August 2018

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Abstract: A restricted growth function (RGF) of length n is a sequence w = w_1 w_2 ... w_n of positive integers such that w_1 = 1 and w_i is at most 1 + max{w_1,..., w_{i-1}} for i at least 2. RGFs are of interest because they are in natural bijection with set partitions of {1, 2, ..., n}. RGF w avoids RGF v if there is no subword of w which standardizes to v. We study the generating functions sum_{w in R_n(v)} q^{st(w)} where R_n(v) is the set of RGFs of length n which avoid v and st(w) is any of the four fundamental statistics on RGFs defined by Wachs and White. These generating functions exhibit interesting connections with integer partitions and two-colored Motzkin paths, as well as noncrossing and nonnesting set partitions.

Full work available at URL: https://arxiv.org/abs/1605.04807

Recommendations

• On 1212-avoiding restricted growth functions
• \(\sigma\)-restricted growth functions and \(p,q\)-Stirling numbers
• Set partition patterns and statistics
• Efficient generation of restricted growth words
• Alphabetic points in restricted growth functions

zbMATH Keywords

partitiongenerating functionpatternnoncrossing partitionGaussian polynomialstatisticlblsrbrsrestricted growth functionnonnesting partitiontwo-colored Motzkin path

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Partitions of sets (05A18) Combinatorial identities, bijective combinatorics (05A19)

Cites Work

• On the parity of certain coefficients for a \(q\)-analogue of the Catalan numbers
• On \(abab\)-free and \(abba\)-free set partitions
• Pattern avoidance in set partitions.
• On pattern-avoiding partitions
• Pattern avoidance for set partitions à la Klazar
• Pattern-avoiding set partitions and Catalan numbers
• Counting pattern-free set partitions. II: Noncrossing and other hypergraphs
• Generalized permutation patterns and a classification of the Mahonian statistics
• Generalized noncrossing partitions and combinatorics of Coxeter groups
• Permutation patterns and statistics
• Inversion polynomials for 321-avoiding permutations
• Set partition statistics and \(q\)-Fibonacci numbers
• \(p,q\)-Stirling numbers and set partition statistics
• Avoidance of partitions of a three-element set
• Octabasic Laguerre polynomials and permutation statistics
• Title not available (Why is that?)
• Mahonian pairs
• Pattern avoidance in ascent sequences
• Combinatorial statistics on non-crossing partitions
• Counting pattern-free set partitions. I: A generalization of Stirling numbers of the second kind
• Limits of areas under lattice paths
• Set partition patterns and statistics
• Front representation of set partitions
• Permutation statistics and \(q\)-Fibonacci numbers
• On 021-avoiding ascent sequences

Cited In (9)

• Sorting with pattern-avoiding stacks: the \(132\)-machine
• Difference ascent sequences
• Catalan words avoiding pairs of length three patterns
• \(\sigma\)-restricted growth functions and \(p,q\)-Stirling numbers
• Set partition patterns and the dimension index
• Efficient generation of restricted growth words
• Alphabetic points in restricted growth functions
• On 1212-avoiding restricted growth functions
• Transport of patterns by Burge transpose

This page was built for publication: Restricted growth function patterns and statistics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1661480)