Penn Arts & Sciences Logo

Probability and Combinatorics

Tuesday, November 15, 2005 - 4:00pm

Vince Vatter

University of St. Andrews

Location

University of Pennsylvania

DRL 4N30

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.