
In Any Way but This. Pattern Avoidance. The Basics. 157
empty. This can be seen as in the proof of Lemma 4.3. Therefore, C contains
at least one 1234-avoiding permutation.
On the other hand, we claim that the decreasing order of the remaining
entries is the only one that will result in a 1234-avoiding permutation. Indeed,
if we put two of the remaining entries, say a and b, in increasing order, then
together with the rightmost left-to-right minimum on the left of a and the
leftmost right-to-left maximum on the right of b they would form a 1234-
pattern.
The second half of our argument is somewhat subtler.
LEMMA 4.22
Each nonempty class contains at le