Decomposing simple permutations with enumerative consequences

摘要

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