Restricted Permutations

This paper is concerned with counting permutations which do not contain certain subsequences. The number of even and odd such permutations is found and the involutions among them are counted. Bijections are determined between sets of such permutations and other combinatorial objects. A discussion is given of lattices whose maximum length chains correspond to restricted permutations. The results in this paper complement previous work by Knuth, Lovász, Rotem and Stanley