An interval in a permutation (thought of in one-line notation, rather than cycle notation) is a set of consecutive entries with consecutive values, for example, 32 is an interval in 1324. Every permutation of length n has n trivial intervals (each contains one element) and one trivial interval containing all the elements. Permutations that have only these trivial intervals are said to be simple. I will discuss the enumeration and decomposition of simple permutations, as well as their applications to the study of restricted permutations.
Probability and Combinatorics
Tuesday, November 15, 2005 - 4:00pm
Vince Vatter
University of St. Andrews