The University of Michigan Combinatorics Seminar
Fall 2004
October 8, 4:10-5:00, 3866 East Hall

Refined enumeration of pattern-avoiding permutations

Sergi Elizalde



The talk will begin with a short survey of some of the main enumerative results in the subject of restricted (or pattern-avoiding) permutations. Next I will discuss some recent work concerning statistics on restricted permutations, motivated in part by the surprising result of Zeilberger et al. which states that the number of fixed points has the same distribution in 321-avoiding permutations as in 132-avoiding permutations. I will give two combinatorial proofs of this result, and generalize it to other statistics. Bijections to Dyck paths play an important role in the proofs. Finally I will consider permutations avoiding several patterns simultaneously, as well as generalized patterns (i.e., with the requirement that some elements occur in adjacent positions). Using similar bijections we obtain generating functions enumerating these restricted permutations with respect to several statistics.