DIMACS - RUTGERS EXPERIMENTAL MATHEMATICS SEMINAR

Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

Co-organizers:

Brian Nakamura, Rutgers University, bnaka {at} math [dot] rutgers [dot] edu

Doron Zeilberger, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

Title: 321-avoiding permutations

Speaker: Vince Vatter, University of Florida

Date: Thursday, March 7, 2013 5:00pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

It is well-known that the 321-avoiding permutations are counted by the Catalan numbers, and thus have an algebraic generating function. I will prove that every subclass of the 321-avoiding permutations which is defined by only finitely many additional restrictions has a rational generating function. The primary proof technique is the theory of formal languages applied to a restricted version of the ``staircase decomposition'' which every 321-avoiding permutation possesses. This is joint work with Michael Albert and Nik Ruskuc.

See: http://www.math.rutgers.edu/~bnaka/expmath/