Fixed-Occurrence Permutation Pattern Asymptotics

Definitions and mathematical statement

The supplied record does not identify the permutation pattern or specify the convention for an occurrence. Consequently, it does not determine a unique enumeration problem. The following definitions give a conditional interpretation using classical permutation patterns; this interpretation requires confirmation from the cited sources.

Let $k\geq 1$, and let $\tau\in S_k$ be a fixed permutation, where $S_k$ denotes the permutations of $\{1,\ldots,k\}$. Under the classical-pattern interpretation, an occurrence of $\tau$ in $\sigma\in S_n$ is a tuple $1\leq i_1<\cdots<i_k\leq n$ such that \[ \sigma(i_a)<\sigma(i_b)\quad\Longleftrightarrow\quad\tau(a)<\tau(b) \qquad(1\leq a,b\leq k). \] Distinct index tuples are counted separately, including overlapping occurrences. For integers $n,r\geq0$, set \[ \psi_r(n)=\#\{\sigma\in S_n:\sigma\text{ has exactly }r\text{ occurrences of }\tau\}. \] Here $S_0$ contains the empty permutation. Interpreting the generating function as an ordinary generating function gives \[ \Psi_r(x)=\sum_{n\geq0}\psi_r(n)x^n. \] Both the classical-occurrence convention and the ordinary-generating-function convention are explicit provisional interpretations, not definitions recovered unambiguously from the supplied excerpt.

The recoverable asymptotic question is whether, for the intended fixed pattern and each fixed integer $r\geq0$, there exists a constant $C_r>0$, independent of $n$, such that \[ \psi_r(n)\sim C_r n^r\psi_0(n)\qquad(n\to\infty), \] meaning \[ \lim_{n\to\infty}\frac{\psi_r(n)}{C_r n^r\psi_0(n)}=1. \] This ratio requires $\psi_0(n)>0$ for all sufficiently large $n$; the supplied record does not identify the intended pattern or give hypotheses ensuring this. No assertion for every permutation pattern, or uniformly for $r$ growing with $n$, can be extracted reliably from the record.

The source also conjectures an algebraic form for $\Psi_r(x)$. Its damaged display contains the expression \[ P_1(x)-P_2(x)\sqrt{1-4x}, \] with $P_1,P_2\in{\mathbb{Z}}[x]$, and stipulates \[ \begin{aligned} \deg P_1=\deg P_2&=\frac{5r}{2} &&\text{if }r\text{ is even},\\ \deg P_1&=\frac{5r+1}{2},\qquad \deg P_2=\frac{5r-1}{2} &&\text{if }r\text{ is odd}. \end{aligned} \] The polynomials may depend on $r$ and the intended pattern. The prefactor or denominator involving $2$, $x$, and $2r+1$ is not preserved reliably enough to state the full equality. Thus the generating-function conjecture remains incompletely specified.

A further damaged display involves a polynomial $Q_{2r}(n)$ with integer coefficients and degree $2r$, factorials $(2n-r)!$, $(n+2r+1)!$, and $(n-r)!$, and asymptotic factors involving $C_r$, $4^n$, $n$, and $\pi$. Their arrangement cannot be recovered reliably from the supplied text; no exact coefficient formula or additional asymptotic formula is asserted here.

The excerpt further reports that the amplitudes appear computationally to grow exponentially, seemingly like $\lambda^r$ with $\lambda\approx2.67$, but says this increase cannot continue indefinitely because the histogram of $\psi_r(n)$ against $r$ is asymptotically normal and its heights must eventually decrease. These are supplied heuristic qualifications: no limiting regime, normalization, or precise normal-limit statement is given. The additional assertion that only the amplitude changes with $r$ is not reconciled in the record with the displayed factor $n^r$. These remarks do not provide a precise further conjecture without source clarification.

Short English statement

For an unidentified fixed permutation pattern, the record asks whether the number of permutations with exactly $r$ occurrences is asymptotic to $C_r n^r$ times the number avoiding the pattern, for fixed $r$ as $n\to\infty$. It also proposes an algebraic generating function. The intended pattern and occurrence convention are missing, and two displayed formulas are damaged, so the formulation above is conditional and requires mathematical review.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30005319$, title: Fixed-Occurrence Permutation Pattern Asymptotics. Exact source problem code: catalogue entry. The record belongs to the Oberwolfach Reports Open Problems collection and gives proposed year $2022$; it names no proposer.
• Supplied report citation: Enumerative Combinatorics (2023), Oberwolfach Reports, DOI 10.4171/owr/2022/57, pp. 3215--3305. Original OWR report: https://doi.org/10.4171/owr/2022/57. The record describes these reports as documenting mathematical workshops and their open-problem discussions.
• Supplied literature-source label: Conway--Guttmann primary article, https://www.combinatorics.org/ojs/index.php/eljc/article/download/v32i1p3/pdf. The supplied assessment describes this as a $2025$ primary study; no complete article citation is included in the record.
• Literature checked at: 2026-08-22. This is supplied dated curation, not an independently verified assessment. The supplied status is open; the assessment says that the $2025$ primary study still presents the asymptotic formula as a conjecture supported by computation and that no proof was located by that cutoff. The background explicitly requests independent verification of time-sensitive status and cited claims.
• The excerpt attributes the conjectured generating-function form to Fulmek in $2002$, saying it was given previously without comment. No full citation or link for that attribution is supplied.
• The registry labels the statement corrected_verified, explaining that only formula delimiters, notation, grammar, and typography were repaired, with mathematical content and scope preserved. This supplied editorial label does not establish mathematical correctness or resolve the missing information and damaged displays.