Avoiding patterns with finite automata

   Mike Zabrocki, (York University)

Abstract: Classes of permutations which do not contain certain patterns arise in several areas of algebraic combinatorics (e.g. in Schubert calculus vexillary permutations avoid the pattern 2143). The problem of enumerating permutations which avoid any given pattern has become a small subfield of combinatorics in recent years. There are very few general techniques to approach these enumeration problems and we will discuss a new way of looking at pattern avoiding permutations which will help to understand some of the results that are known.

Part one of this talk will include an introduction to the theory of languages and finite automata. We will talk about the Chomsky heirarchy of langauages and discuss the relationship between classes of languages and their generating functions. In the second part we will apply these results to pattern avoiding permutations and show that the class of permutations with a fixed number of descents that avoid any fixed pattern has a rational generating function.

A permutation, pi in S_n, is said to contain a pattern, X in S_m with m<=n, if there is a subword of pi, pi_{i_1} p_{i_2} ... p_{i_m} where i_r < i_{r+1} such that pi_{i_r} < pi_{i_s} if and only if X_r < X_s.
e.g. 6132754 contains the pattern 4132 since the subword 6254 has the same relative order
6132754 avoids the pattern 1234 since there is no increasing subsequence of 4 numbers

Applied Algebra seminar home