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.