The limit of a Stanley-Wilf sequence is not always rational, and layered patterns beat monotone patterns (Q556857): Difference between revisions

If \(p=p_1p_2\dots p_n\) and \(q\) are permutations of \(\{ 1,2,\dots,n\}\) and \(\{ 1,2,\dots,k\}\) for \(k\leq n\), respectively, then \(p\) is said to contain the pattern \(q\) if \(q\) and \(p_{i_1}p_{i_2}\dots p_{i_k}\) are order isomorphic for some \(1\leq i_1<i_2<\dots<i_k\leq n\), i.e. the terms are ordered in the same relative way. Let \(S_n(q)\) denote the number of permutations of \(\{ 1,2,\dots,n\}\) that do not contain a pattern \(q\). It follows from a recent result of Marcus and Tardos that the limit \(L(q)=\lim_{n\to\infty}(S_n(q))^{1/n}\) exists. In the present paper the author proves that \(L(12453)=9+4\sqrt{2}\) providing the first example of a pattern \(q\) for which \(L(q)\) is not an integer. He also determines \(L(q_k)\) for \(q_k=12\dots(k-3)(k-1)k(k-2)\) as \((k-4+\sqrt{8})^2\). Finally, he proves that \(L(q)\geq L(12\dots k)=(k-1)^2\) for so-called layered patterns \(q\) of length \(k\) which supports a conjecture from 1997 stating that \(S_n(q)\geq S_n(12\dots k)\) for such patterns \(q\).