Penn Arts & Sciences Logo

Graduate Student Combinatorics Seminar

Wednesday, January 27, 2010 - 12:30pm

Michael Lugo

University of Pennsylvania

Location

University of Pennsylvania

4C8

Singularity analysis of generating functions allows us to quickly determine the distribution of statistics of random discrete structures. In this way we can answer questions of the type "what does a random structure of type X look like?" I will consider such questions of this type for compositions and partitions of integers, permutations satisfying certain restrictions, and compositions of involutions. I will also speak about algorithms for the random generation of such structures, such as the Boltzmann samplers of Flajolet and coauthors, and show hot such algorithms are useful both for providing intuition and onjecture and as a possible proof technique.