Forests and pattern-avoiding permutations modulo pure descents
Abstract
We investigate an equivalence relation on permutations based on the pure descent statistic. Generating functions are given for the number of equivalence classes for the set of all permutations, and the sets of permutations avoiding exactly one pattern of length three. As a byproduct, we exhibit a permutation set in one-to-one correspondence with forests of ordered binary trees, which provides a new combinatorial class enumerated by the single-source directed animals on the square lattice. Furthermore, bivariate generating functions for these sets are given according to various statistics.
© 2018 Jean-Luc Baril, Sergey Kirgizov, Armen Petrossian, published by Corvinus University of Budapest
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.