Restricted generating trees for weak orderings

DOI10.46298/DMTCS.8350MaRDI QIDQ6045409zbMATH OpenOpenAlexFDO

Authors Daniel Birmajer, Juan B. Gil, Michael D. Weiner

Publication date 30 May 2023

Published in Discrete Mathematics & Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

generating treespattern avoidanceweak orderings

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Partitions of sets (05A18) Trees (05C05) Combinatorics of partially ordered sets (06A07)

Abstract: Motivated by the study of pattern avoidance in the context of permutations and ordered partitions, we consider the enumeration of weak-ordering chains obtained as leaves of certain restricted rooted trees. A tree of order $n$ is generated by inserting a new variable into each node at every step. A node becomes a leaf either after $n$ steps or when a certain stopping condition is met. In this paper we focus on conditions of size 2 ($x=y$, $x<y$, or $xley$) and several conditions of size 3. Some of the cases considered here lead to the study of descent statistics of certain `almost' pattern-avoiding permutations.

Recommendations

• Finitely labeled generating trees and restricted permutations
• Generating trees for permutations avoiding generalized patterns
• Pattern avoidance in binary trees
• scientific article; zbMATH DE number 3961006
• Generating functions for generating trees

Cites work

• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• Ordered partitions avoiding a permutation pattern of length 3
• Patterns in permutations and words.
• Permutations with restricted patterns and Dyck paths
• The descent statistic on 123-avoiding permutations

Cited in

(3)

• Weak sequential theories of finite full binary trees
• Finitely labeled generating trees and restricted permutations
• Pattern-avoiding Cayley permutations via combinatorial species

This page was built for publication: Restricted generating trees for weak orderings

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