Let F_n(sigma_1,…,sigma_k) denote Fishburn permutations of length n avoiding each listed pattern, and let (F_n) be the Fibonacci sequence under the paper's indexing convention. Additional enumeration conjectures. The following identities are conjectured: |F_n(321,1243)|=|F_n(321,2134)|=n^2-3n+4 quad(n≥ 2), |F_n(321,1324)|=frac32n^2-frac132n+10 quad(n≥ 3), |F_n(321,3142,2143)|=|F_n(321,1423,2143)|=|F_n(321,2143,3124)|=|F_n(321,2143,4123)|=binomn2+1 quad(n≥ 0), |F_n(321,1423,3124)|=F_n+2 quad(n≥ 4), |F_n(321,1423,4123)|=|F_n(321,3124,4123)|=F_n+1-1 quad(n≥ 1), |F_n(321,14253)|=|F_n(321,21354)|=2^n-binomn2-1 quad(n≥ 1). The source says all these identities were verified for n≤ 20; no general proofs are given.

Additional enumerations for 321-avoiding Fishburn permutations

From papers

Let $F_n(\sigma_1,\ldots,\sigma_k)$ denote Fishburn permutations of length $n$ avoiding each listed pattern, and let $(F_n)$ be the Fibonacci sequence under the paper's indexing convention.

Additional enumeration conjectures. The following identities are conjectured:

|F_n(321,1243)|=|F_n(321,2134)|=n^2-3n+4\quad(n\geq 2),

|F_n(321,1324)|=\frac{3}{2}n^2-\frac{13}{2}n+10\quad(n\geq 3),

|F_n(321,3142,2143)|=|F_n(321,1423,2143)|=|F_n(321,2143,3124)|=|F_n(321,2143,4123)|=\binom{n}{2}+1\quad(n\geq 0),

|F_n(321,1423,3124)|=F_n+2\quad(n\geq 4),

|F_n(321,1423,4123)|=|F_n(321,3124,4123)|=F_{n+1}-1\quad(n\geq 1),

|F_n(321,14253)|=|F_n(321,21354)|=2^n-\binom{n}{2}-1\quad(n\geq 1).

The source says all these identities were verified for $n\leq 20$ ; no general proofs are given.

Progress summary

Solved

A 2023 paper gives general proofs of all the enumerations, so the conjectures are now settled.

Eric S. Egge posed these identities as part of his conjectures on pattern-avoiding Fishburn permutations; the original work reported verification only through $n\leq 20$ .

Known results

Earlier work proved related formulas such as $|F_n(321,1423)|=|F_n(321,3124)|=F_{n+2}-n-1$ and $|F_n(321,2143)|=2^{n-1}$ , while leaving the additional identities conjectural.

March 2023 general proof

Yujie Du and Philip B. Zhang’s paper proves Egge’s Conjectures 10.14 and 10.17. Its theorem sequence establishes the quadratic, $\binom{n}{2}+1$ , Fibonacci, and $2^n-\binom{n}{2}-1$ formulas listed here for all stated ranges, replacing finite verification with general proofs.

Current status (as of August 2026): All identities in the problem are proved by Du and Zhang; no part of this conjectural list remains open.

Sources

Sources & referencesView supporting material

Primary source

Eric S. Egge, “Pattern-Avoiding Fishburn Permutations and Ascent Sequences”, arXiv:2208.01484 (2022).

1 week ago

This conjecture has been proved in later literature.

The identities in this MathDB entry are exactly Conjecture 10.17 of Eric S. Egge:

https://arxiv.org/abs/2208.01484

Yujie Du and Philip B. Zhang prove that conjecture in arXiv:2302.13767v3:

https://arxiv.org/abs/2302.13767v3

The journal version is Yujie Du and Philip B. Zhang, “On enumeration of pattern-avoiding Fishburn permutations,” Discrete Mathematics 347 (2024), Article 113952:

https://doi.org/10.1016/j.disc.2024.113952

The exact correspondence is:

Theorem 2.1 proves the formula for $F_n(321,1243)$ .
Theorem 2.4 proves the formula for $F_n(321,2134)$ .
Theorem 2.6 proves the formula for $F_n(321,1324)$ .
Theorems 3.1, 3.4, 3.5, and 3.7 prove the four formulas equal to $\binom{n}{2}+1$ .
Theorem 3.9 proves the formula $|F_n(321,1423,3124)|=F_n+2$ .
Theorems 3.12 and 3.15 prove the two formulas equal to $F_{n+1}-1$ .
Theorems 4.1 and 4.3 prove the two formulas equal to $2^n-\binom{n}{2}-1$ .

The common structural starting point is Lemma 1.1 of that paper: if $\pi\in F_n(321)$ , then the entry $1$ is in the first or second position. Indeed, suppose it occurs later and write $x=\pi_1$ , $y=\pi_2$ . If $x>y$ , then $x,y,1$ form a 321-pattern. If $x<y$ , then $x-1$ occurs after $y$ , so $x,y,x-1$ form the forbidden Fishburn bivincular pattern. Both alternatives are impossible.

The paper then splits every avoidance class according to whether $\pi_1=1$ or $\pi_2=1$ , classifies the resulting normal forms, and sums their cardinalities. The theorem numbers above give the resulting all- $n$ enumerations.

Thus all twelve enumerative statements, equivalently all identities (38)–(43) of Egge’s Conjecture 10.17, are proved. This MathDB entry should therefore be marked solved.

0 endorsements

Samuel Schlesinger · 4 days ago