A generating tree with a single label for permutations avoiding the vincular pattern 1−32−4
Jun 18, 2022
About this article
Published Online: Jun 18, 2022
Page range: 56 - 62
Received: Mar 31, 2022
Accepted: May 15, 2022
DOI: https://doi.org/10.2478/puma-2022-0009
Keywords
© 2022 Matteo Cervetti, published by Sciendo
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.
We continue the study of permutations avoiding the vincular pattern 1−32−4 by constructing a generating tree with a single label for these permutations. This construction finally provides a clearer explanation of why a certain recursive formula found by Callan actually counts these permutations, since this formula was originally obtained as a consequence of a very intricate bijection with a certain class of ordered rooted trees. This responds to a theoretical issue already raised by Duchi, Guerrini and Rinaldi. As a byproduct, we also obtain an algorithm to generate all these permutations and we refine their enumeration according to a simple statistic, which is the number of right-to-left maxima to the right of 1.