Complexity in Enumerative Combinatorics — Problem 10

Definitions and mathematical statement

The supplied statement is corrupted, so a complete mathematical problem cannot be recovered reliably.

For a conventional interpretation of the surviving permutation notation, let $S_m$ denote the permutations of $\{1,\ldots,m\}$, for a positive integer $m$. Given $\pi\in S_k$ and $\sigma\in S_n$, say that $\sigma$ contains $\pi$ if there exist indices $1\le i_1<\cdots<i_k\le n$ such that, for every $a,b\in\{1,\ldots,k\}$, \[ \sigma(i_a)<\sigma(i_b)\quad\Longleftrightarrow\quad\pi(a)<\pi(b). \] Otherwise, $\sigma$ avoids $\pi$. Define \[ A_n(\pi)=\left|\{\sigma\in S_n:\sigma\text{ avoids }\pi\}\right|. \] Here $1324\in S_4$ denotes the permutation with successive values $1,3,2,4$. These definitions supply the standard pattern-avoidance interpretation suggested by the surviving notation; the supplied excerpt does not itself retain a definition of $A_n(\pi)$.

Under this interpretation, the recoverable subject is the computational complexity of obtaining $A_n(1324)$, followed by a more general question concerning the existence of a single fixed permutation $\pi$ with a specified computational property of $A_n(\pi)$. A final question concerns computational difficulty for random $\pi\in S_k$. The time bounds, essential predicates, and the comparison preceding "or harder" are missing. Thus neither a precise complexity assertion nor the intended quantifiers concerning random patterns can be stated from the supplied text. In particular, no polynomial, exponential, or other time bound is asserted here. The source also does not specify the input encoding, computational model, or probability distribution intended in the random-pattern question.

Short English statement

The damaged source asks about computing permutation-pattern avoidance counts, first for $1324$, then for a fixed general pattern, and finally for random patterns. Its essential complexity bounds and comparison terms are missing, so the intended problem cannot be stated precisely. The supplied registry labels it open; this draft does not independently verify that status.

Sources

• Local UnsolvedMath registry, permanent ID $800326$, source problem code catalogue entry, title "Complexity in Enumerative Combinatorics --- Problem 10." The supplied record attributes the problem to Pak, gives proposed year 2018, and labels its status open.
• Pak, Complexity Problems in Enumerative Combinatorics (2018), Problem 10. Supplied source URL: https://arxiv.org/abs/1803.06636. The record reports access on 2026-10-16 and extraction by arxiv_latex; these are supplied provenance details, not independently verified access or source inspection.
• The supplied excerpt includes an incomplete historical parenthesis attributing doubts to Doron Zeilberger in 2005 concerning $A_{1000}(1324)$. The assertion about that quantity is missing. It further reports criticism on mathematical and theological grounds and cites the label [Ste], for which no bibliographic details or URL are supplied.