$q$-Difference Equations for two classes of Pattern Avoiding Permutations

Abstract

We study the nested permutation classes $Av(4123,4231,4312)\subset Av(4123,4312)$. We relate the corresponding generating functions $D^{(2)}(z)$, $D^{(3)}(z)$ to $q$-difference equations. Solving these equations allows to show that the generation functions are not D-finite, and that $[z^n]D^{(3)}(z)\sim 0.0189672325071988\dots (4.46840899160393\dots {)}^n$, $[z^n]D^{(2)}(z)\sim 0.0849833632890843\dots (3+2\sqrt{2}{)}^n{n}^{-3/2}$.