Interdisciplinary Seminar Series

Title: Enumerating permutations with exactly r copies of a pattern

Speaker: Brian Nakamura, CCICADA/DIMACS, Rutgers University

Date: Tuesday, September 10, 2013 11:00am - 12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ


The study of patterns in permutations gained interest after some early results on permutation sorting. This naturally led to enumerative questions such as "How many length n permutations avoid a given pattern?" I will begin by providing some background and then discuss a generalization to the avoidance problem, where one is now interested in permutations with exactly r copies of a pattern. I will present a functional equations approach to derive a new enumeration algorithm. I will discuss what types of patterns this approach works for (so far) and also how this approach can be extended to multiple patterns.

DIMACS/CCICADA Interdisciplinary Series, Complete Calendar