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).
Mathematics Subject Classification (2000) 05D99 - 05A15 - 06A07
Supported by a Royal Society Dorothy Hodgkin Research Fellowship.
Supported by EPSRC grant GR/S53503/01.