1324 pattern-avoiding permutations
The field of pattern-avoiding permutations was introduced by Knuth in the
1960s as a way of characterising
certain data structures. Since then, it has grown into an important area in
its own right. There are a number of classical problems, among which is the
number of \(1324\)-avoiding permutations. We will give some history, and then
give details of a new algorithm we have developed for the generating
function for this problem. As a result we can count these up to length 50.
A new method of analysis we have developed, which can in some circumstances
be an alternative to Monte Carlo analysis, reveals some interesting
features. In particular, we conjecture that the generating function is not
D-finite, and has asymptotics that include a stretched-exponential term.
(Joint work with Andrew Conway and Paul Zinn-Justin).
The late, great Mark Kac often said that his seminars assumed zero knowledge
but infinite wisdom. This seminar only assumes zero knowledge and finite
wisdom.