Stanley–Wilf limit for the permutation pattern 1324

Description of constant

Let $\mathrm{Av}_n(1324)$ be the set of permutations of ${1,2,\dots,n}$ that avoid the permutation pattern $1324$, and let

[CJS12-def-Sn]

The Stanley–Wilf limit (growth constant) for the pattern $1324$ is

[CJS12-def-Ltau]

Equivalently, $C_{30} = \mathrm{gr}(\mathrm{Av}(1324))$, the growth rate of the permutation class avoiding $1324$.

[BBEPP2017-def-gr]

This limit is known to exist (and to be finite) for every fixed pattern, as a consequence of Marcus–Tardos and Arratia.

[CJS12-mt-expbound] [CJS12-arratia-exists]

Known upper bounds

Known lower bounds

Additional comments and links

• Determining the exact value of $C_{30}$ remains open. [BBEPP2017-open]

• The best current rigorous bounds are $10.27 \le C_{30} \le 13.5$. [BBEPP2017-t1-thiswork]

• Claesson, Jelínek and Steingrímsson conjectured a statement about $1324$-avoiding permutations with a fixed number of inversions, which (if true) would imply the improved upper bound \(C_{30} \le e^{\pi \sqrt{2/3}} \approx 13.001954;\) see [CJS12] (and [BBEPP2017] for a brief summary). [CJS12-cond-ub] [BBEPP2017-cond-ub]

• Conway, Guttmann and Zinn-Justin have analysed the series for the number of $1324$-avoiding permutations in $S_n$ and give a numerical estimate for $C_{30}$ of $11.600 \pm 0.003$. They also conjecture that $|\mathrm{Av}_n(1324)|$ behaves asymptotically as \(A\cdot \mu^n \cdot \lambda^{\sqrt{n}} \cdot n^\alpha \qquad (n\to\infty)\) for certain estimated constants $A,\lambda,\alpha$; see [BBEPP2017] for a summary. [BBEPP2017-estimate] [BBEPP2017-asymptotic]

References

• [BBEPP2017] Bevan, David; Brignall, Robert; Elvey Price, Andrew; Pantone, Jay. A structural characterisation of Av(1324) and new bounds on its growth rate. Preprint (2017), last revised 2019. Google Scholar. arXiv PDF. Publisher entry
  • [BBEPP2017-open] loc: arXiv v3 PDF p.1, Section 1 (Introduction). quote: “In contrast, even the exponential growth rate of $\mathrm{Av}(1324)$ remains to be determined exactly.”
  • [BBEPP2017-def-gr] loc: arXiv v3 PDF p.2, Section 1 (Introduction). quote: “The exponential growth rate of the class $\mathrm{Av}(\pi)$ is $\mathrm{gr}(\mathrm{Av}(\pi)) = \limsup_{n\to\infty} |\mathrm{Av}_n(\pi)|^{1/n}$, where $\mathrm{Av}_n(\pi)$ denotes the set of permutations of length $n$ that avoid $\pi$. This limit is known to exist as a consequence of the resolution of the Stanley-Wilf conjecture by Marcus and Tardos [26].”
  • [BBEPP2017-t1-ub-288] loc: arXiv v3 PDF p.2, Section 1 (Introduction), Table 1. quote: “Lower Upper 2004: Bóna [5] $288$ Table 1: A chronology of lower and upper bounds for $\mathrm{gr}(\mathrm{Av}(1324))$”
  • [BBEPP2017-t1-lb-9] loc: arXiv v3 PDF p.2, Section 1 (Introduction), Table 1. quote: “Lower Upper 2005: Bóna [6] $9$ Table 1: A chronology of lower and upper bounds for $\mathrm{gr}(\mathrm{Av}(1324))$”
  • [BBEPP2017-t1-lb-9.47] loc: arXiv v3 PDF p.2, Section 1 (Introduction), Table 1. quote: “Lower Upper 2006: Albert et al. [1] $9.47$ Table 1: A chronology of lower and upper bounds for $\mathrm{gr}(\mathrm{Av}(1324))$”
  • [BBEPP2017-t1-ub-16] loc: arXiv v3 PDF p.2, Section 1 (Introduction), Table 1. quote: “Lower Upper 2012: Claesson, Jelínek and Steingrímsson [13] $16$ Table 1: A chronology of lower and upper bounds for $\mathrm{gr}(\mathrm{Av}(1324))$”
  • [BBEPP2017-t1-ub-13.93] loc: arXiv v3 PDF p.2, Section 1 (Introduction), Table 1. quote: “Lower Upper 2014: Bóna [8] $13.93$ Table 1: A chronology of lower and upper bounds for $\mathrm{gr}(\mathrm{Av}(1324))$”
  • [BBEPP2017-t1-lb-9.81] loc: arXiv v3 PDF p.2, Section 1 (Introduction), Table 1. quote: “Lower Upper 2015: Bevan [3] $9.81$ Table 1: A chronology of lower and upper bounds for $\mathrm{gr}(\mathrm{Av}(1324))$”
  • [BBEPP2017-t1-ub-13.74] loc: arXiv v3 PDF p.2, Section 1 (Introduction), Table 1. quote: “Lower Upper 2015: Bóna [9] $13.74$ Table 1: A chronology of lower and upper bounds for $\mathrm{gr}(\mathrm{Av}(1324))$”
  • [BBEPP2017-t1-thiswork] loc: arXiv v3 PDF p.2, Section 1 (Introduction), Table 1. quote: “Lower Upper This work $10.27$ $13.5$ Table 1: A chronology of lower and upper bounds for $\mathrm{gr}(\mathrm{Av}(1324))$”
  • [BBEPP2017-cond-ub] loc: arXiv v3 PDF p.2, Section 1 (Introduction). quote: “In addition to these, Claesson, Jelínek and Steingrímsson [13] make a conjecture regarding the number of $1324$-avoiders of each length that have a fixed number of inversions, which if proven would yield an improved upper bound of $e^{\pi\sqrt{2/3}} \approx 13.002$.”
  • [BBEPP2017-estimate] loc: arXiv v3 PDF p.2, Section 1 (Introduction). quote: “Conway, Guttmann and Zinn-Justin [14, 15] have analysed the numbers and give a numerical estimate for $\mathrm{gr}(\mathrm{Av}(1324))$ of $\mu \approx 11.600 \pm 0.003$.”
  • [BBEPP2017-asymptotic] loc: arXiv v3 PDF p.2, Section 1 (Introduction). quote: “They also conjecture that $|\mathrm{Av}_n(1324)|$ behaves asymptotically as $A\cdot \mu^n \cdot \lambda^{\sqrt{n}} \cdot n^\alpha$, for certain estimated constants $A$, $\lambda$ and $\alpha$.”

• [B04] Bóna, Miklós. A simple proof for the exponential upper bound for some tenacious patterns. Advances in Applied Mathematics 33 (2004), no. 1, 192–198. DOI: 10.1016/j.aam.2003.07.003. Google Scholar

• [B05] Bóna, Miklós. The limit of a Stanley–Wilf sequence is not always rational, and layered patterns beat monotone patterns. J. Combin. Theory Ser. A 110 (2005), no. 2, 223–235. DOI: 10.1016/j.jcta.2004.07.014. Google Scholar. arXiv PDF

• [AERWZ] Albert, M. H.; Elder, M.; Rechnitzer, A.; Westcott, P.; Zabrocki, M. On the Stanley–Wilf limit of 4231-avoiding permutations and a conjecture of Arratia. Adv. Appl. Math. 36 (2006), no. 2, 96–105. DOI: 10.1016/j.aam.2005.05.007. Google Scholar. arXiv PDF

• [CJS12] Claesson, A.; Jelínek, V.; Steingrímsson, E. Upper bounds for the Stanley–Wilf limit of 1324 and other layered patterns. J. Combin. Theory Ser. A 119 (2012), no. 8, 1680–1691. DOI: 10.1016/j.jcta.2012.05.006. Google Scholar. arXiv PDF
  • [CJS12-def-Sn] loc: arXiv v1 PDF p.1, Section 1 (Introduction). quote: “For a permutation pattern $\tau$, let $S_n(\tau)$ be the set of permutations of length $n$ avoiding $\tau$, and let $S_n(\tau)$ be the cardinality of $S_n(\tau)$.”
  • [CJS12-def-Ltau] loc: arXiv v1 PDF p.1, Section 1 (Introduction). quote: “The limit $L(\tau) = \lim_{n\to\infty} S_n(\tau)^{1/n}$ is called the Stanley-Wilf limit for $\tau$.”
  • [CJS12-mt-expbound] loc: arXiv v1 PDF p.1, Section 1 (Introduction). quote: “In 2004, Marcus and Tardos [15] proved the Stanley-Wilf conjecture, stating that, for any pattern $\tau$, $S_n(\tau) < C^n$ for some constant $C$ depending only on $\tau$.”
  • [CJS12-arratia-exists] loc: arXiv v1 PDF p.1, Section 1 (Introduction). quote: “Arratia [3] has shown that this limit exists for any pattern $\tau$.”
  • [CJS12-cond-ub] loc: arXiv v1 PDF p.1, Abstract. quote: “We also conjecture that, for any $k \ge 0$, the set of $1324$-avoiding permutations with $k$ inversions contains at least as many permutations of length $n+1$ as those of length $n$. We show that if this is true then the Stanley-Wilf limit for $1324$ is at most $e^{\pi\sqrt{2/3}} \simeq 13.001954$.”

• [B14a] Bóna, Miklós. A new upper bound for 1324-avoiding permutations. Combinatorics, Probability and Computing 23 (2014), no. 5, 717–724. DOI: 10.1017/S0963548314000091. Google Scholar. arXiv PDF

• [B14b] Bóna, Miklós. A new record for 1324-avoiding permutations. European J. Math. 1 (2015), no. 1, 198–206. DOI: 10.1007/s40879-014-0020-6. Google Scholar. arXiv PDF

• [Bev] Bevan, David. Permutations avoiding 1324 and patterns in Łukasiewicz paths. J. London Math. Soc. 92 (2015), no. 1, 105–122. DOI: 10.1112/jlms/jdv020. Google Scholar. arXiv PDF

Contribution notes

Prepared with assistance from ChatGPT 5.2 Pro.