<abstract xmlns="http://www.w3.org/1999/xhtml">

<p>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.</p>
</abstract>

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.

A generating tree with a single label for permutations avoiding the vincular pattern 1−32−4

Pure Mathematics and Applications

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...

A generating tree with a single label for permutations avoiding the vincular pattern 1−32−4

Pubblicato online: 18 giu 2022

Pagine: 56 - 62

Ricevuto: 31 mar 2022

Accettato: 15 mag 2022

DOI: https://doi.org/10.2478/puma-2022-0009

Parole chiave
permutation, vincular pattern, generating tree, powered Catalan numbers

© 2022 Matteo Cervetti, published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

A generating tree with a single label for permutations avoiding the vincular pattern 1−32−4

Pubblicato online: 18 giu 2022

Pagine: 56 - 62

Ricevuto: 31 mar 2022

Accettato: 15 mag 2022

DOI: https://doi.org/10.2478/puma-2022-0009

Parole chiavepermutation, vincular pattern, generating tree, powered Catalan numbers

© 2022 Matteo Cervetti, published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Parole chiave
permutation, vincular pattern, generating tree, powered Catalan numbers