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