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.
Graduate Student Combinatorics Seminar
Wednesday, January 27, 2010 - 12:30pm
Michael Lugo
University of Pennsylvania