Three-letter-pattern avoiding permutations and functional equations
The electronic journal of combinatorics, Tome 13 (2006)
We present an algorithm for finding a system of recurrence relations for the number of permutations of length $n$ that satisfy a certain set of conditions. A rewriting of these relations automatically gives a system of functional equations satisfied by the multivariate generating function that counts permutations by their length and the indices of the corresponding recurrence relations. We propose an approach to describing such equations. In several interesting cases the algorithm recovers and refines, in a unified way, results on $\tau$-avoiding permutations and permutations containing $\tau$ exactly once, where $\tau$ is any classical, generalized, and distanced pattern of length three.
DOI :
10.37236/1077
Classification :
05A15, 05A05
Mots-clés : recurrence relations, generating function
Mots-clés : recurrence relations, generating function
@article{10_37236_1077,
author = {Ghassan Firro and Toufik Mansour},
title = {Three-letter-pattern avoiding permutations and functional equations},
journal = {The electronic journal of combinatorics},
year = {2006},
volume = {13},
doi = {10.37236/1077},
zbl = {1100.05002},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1077/}
}
Ghassan Firro; Toufik Mansour. Three-letter-pattern avoiding permutations and functional equations. The electronic journal of combinatorics, Tome 13 (2006). doi: 10.37236/1077
Cité par Sources :