Tony Guttmann (28/05/18)

Anders Claesson, maí 25, 2018

Málstofa í stærðfræði

Fyrirlesari: Tony Guttmann, The University of Melbourne

Titill: On the number of Av(1324) permutations

Staðsetning: V-147 (VR-II)
Tími: Mánudagur 28. maí kl. 10:50


We give an improved algorithm for counting the number of 1324-avoiding permutations, resulting in 14 further terms of the generating function, which is now known to length 50.
We re-analyse the generating function and find compelling evidence that unlike other classical length-4 pattern-avoiding permutations, the generating function does not have a simple power-law singularity, but rather, the number of 1324-avoiding permutations of length n behaves as \(B\cdot \mu^n \cdot \mu_1^{\sqrt{n}} \cdot n^g\).
We estimate \(\mu = 11.600 \pm 0.003.\) The presence of the stretched exponential term \(\mu_1^{\sqrt{n}}\) is an unexpected feature of the conjectured solution, but we show that such a term is present in a number of other combinatorial problems.
(A.J. Guttmann with A.R. Conway and P. Zinn-Justin)