Generating Functions for Parity Restricted 321 Avoiding Permutations

Definitions and mathematical statement

For a positive integer $m$, a permutation $\pi$ of $\{1,\ldots,m\}$ avoids the pattern $321$ if there are no indices $1\leq i<j<k\leq m$ with $\pi(i)>\pi(j)>\pi(k)$.

The supplied record describes $P_{321}(n)$ as counting parity-restricted $321$-avoiding permutations, but does not define the parity restriction, the underlying permutation sets, or their dependence on $n$. Consequently, the sequence $P_{321}(n)$ cannot be reconstructed from this record. Retaining its undefined notation, set formally \[ F(q)=\sum_{n\geq 1}P_{321}(n)q^n. \] Here $q$ is a formal indeterminate; the displayed series has no constant term.

To specify the properties being asked about, let $K$ be a field of characteristic zero containing the intended coefficients and suppose $F\in K[[q]]$. The source does not specify the intended coefficient field. The series $F$ is algebraic over $K(q)$ if there exists a nonzero polynomial $A(q,Y)\in K[q,Y]$ such that $A(q,F(q))=0$. It is D-finite over $K(q)$ if there exist an integer $r\geq 0$ and polynomials $p_0(q),\ldots,p_r(q)\in K[q]$, not all zero, such that \[ \sum_{j=0}^{r}p_j(q)F^{(j)}(q)=0. \] It is D-algebraic over $K(q)$ if there exist an integer $r\geq 0$ and a nonzero polynomial $B(q,Y_0,\ldots,Y_r)\in K[q,Y_0,\ldots,Y_r]$ such that \[ B\left(q,F(q),F'(q),\ldots,F^{(r)}(q)\right)=0. \] All derivatives here are formal derivatives, with $F^{(0)}=F$.

The source asks whether $F$ has each of these three properties and asks for the asymptotic behavior of $P_{321}(n)$ as $n\to\infty$. These questions remain conditional on recovering the definition of $P_{321}(n)$ and specifying the intended coefficient field. The supplied record labels the problem open; this draft does not independently establish that status.

Short English statement

Determine whether the generating function for the intended parity-restricted $321$-avoiding permutations is algebraic, D-finite, or D-algebraic, and determine the asymptotic behavior of its coefficients. The supplied record omits the parity restriction and the definition of $P_{321}(n)$, so the counting problem requires clarification before a complete mathematical statement is possible.

Sources

• Supplied local registry record, permanent UnsolvedMath ID $30005327$, source problem code catalogue entry, titled "Generating Functions for Parity Restricted 321 Avoiding Permutations." The record gives proposed year 2022 and supplies no named 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.
• Supplied literature source labeled "problem-session paper": https://personal.utdallas.edu/~nxw170830/docs/Papers/Misc/Oberwolfach_EC_2022_problem_session.pdf.
• Literature assessment dated exactly 2026-08-22: the supplied curation reports that the algebraicity, D-finiteness, D-algebraicity, and coefficient asymptotics remain unresolved in the identified literature. This is supplied dated curation, not an independently verified assessment; the record explicitly calls for independent verification of time-sensitive status and cited claims.
• The registry labels its statement corrected_verified, explaining that only formula delimiters, notation, grammar, and typography were repaired. That supplied label does not resolve the missing definition or constitute independent mathematical verification in this draft.