Decomposing simple permutations, with enumerative consequences

Brignall, Robert; Huczynska, Sophie and Vatter, Vincent (2008). Decomposing simple permutations, with enumerative consequences. Combinatorica, 28(4) pp. 385–400.

DOI: https://doi.org/10.1007/s00493-008-2314-0

Abstract

We prove that every sufficiently long simple permutation contains two long almost disjoint simple subsequences, and then we show how this result has enumerative consequences. For example, it implies that, for any r, the number of permutations with at most r copies of 132 has an algebraic generating function (this was previously proved, constructively, by Bóna and (independently) Mansour and Vainshtein).

Viewing alternatives

Metrics

Public Attention

Altmetrics from Altmetric

Number of Citations

Citations from Dimensions

Item Actions

Export

About

Recommendations