Completion of the Wilf-classification of 3-5 pairs using generating trees

Mark Lipson

The electronic journal of combinatorics, Tome 13 (2006)

Résumé

A permutation $\pi$ is said to avoid the permutation $\tau$ if no subsequence in $\pi$ has the same order relations as $\tau$. Two sets of permutations $\Pi_1$ and $\Pi_2$ are Wilf-equivalent if, for all $n$, the number of permutations of length $n$ avoiding all of the permutations in $\Pi_1$ equals the number of permutations of length $n$ avoiding all of the permutations in $\Pi_2$. Using generating trees, we complete the problem of finding all Wilf-equivalences among pairs of permutations of which one has length 3 and the other has length 5 by proving that $\{123,32541\}$ is Wilf-equivalent to $\{123,43251\}$ and that $\{123,42513\}$ is Wilf-equivalent to $\{132, 34215\}$. In addition, we provide generating trees for fourteen other pairs, among which there are two examples of pairs that give rise to isomorphic generating trees.

Détail

DOI : 10.37236/1057

Classification : 05A05, 05A15
Mots-clés : Wilf-equivalences, number of permutations