On a question about pattern avoidance of cyclic permutations

This paper resolves the open question regarding cyclic permutations that avoid the decreasing pattern $\delta_k$ and the pattern $\tau=1432$ by deriving explicit formulas through an analysis of cycle form structures and the application of Dilworth's theorem.

The Gist

Imagine you are organizing a massive, chaotic dance party where $n$ people are all holding hands in a single, giant circle. In the world of mathematics, this circle is called a cyclic permutation.

Now, imagine you are the strict party planner (the mathematician) with two very specific rules to keep the dance floor orderly:

1. The "No Downhill Slide" Rule (One-line notation): If you look at the dancers in a straight line (breaking the circle at a specific point), you cannot find a group of $k$ people who are standing in a perfect, steep downhill slope (like 5, 4, 3, 2, 1). This is called avoiding the pattern $\delta_k$.
2. The "No Bad Shapes" Rule (Cycle forms): If you look at the circle from any starting point (rotating the circle), you must never see a specific "bad shape" formed by four dancers. The paper focuses on the shape 1432 (a small dancer, a huge one, a medium one, and a slightly smaller one).

The Problem

A few years ago, other researchers figured out how to count these "good" dance circles for two of the three possible "bad shapes" of length 4. But they got stuck on the third shape: 1432. They left it as an open mystery, like a locked door in a hallway.

This paper is the key that finally unlocks that door. The authors, Zuo-Ru Zhang and Hongkuan Zhao, figured out exactly how many valid dance circles exist for any number of people ($n$) and any strictness level ($k$).

How They Solved It (The Metaphors)

To solve this, the authors used two main tools, which we can think of as The Detective's Logic and The Ladder Builder.

1. The Detective's Logic (Pattern Translation)

The authors realized that checking every possible rotation of the circle for the "1432" shape was too hard. So, they acted like detectives and found a shortcut.

They proved a brilliant trick: If the circle doesn't have the "1432" shape in any rotation, it means the circle also doesn't have two other specific shapes (321 and 2143) in its standard starting position.

Think of it like this: Instead of checking every angle of a sculpture to see if it looks like a monster, they realized that if the sculpture doesn't have a "broken nose" or a "twisted ear" when viewed from the front, it definitely won't look like a monster from any angle. This simplified the problem immensely.

2. The Ladder Builder (Dilworth's Theorem)

The second rule was about avoiding the "downhill slide" (the decreasing sequence). To count how many arrangements avoid this, they used a famous mathematical idea called Dilworth's Theorem.

Imagine the dancers are trying to climb a set of ladders.

• A "downhill slide" is like a group of people who cannot climb the same ladder together because they are stepping down.
• Dilworth's Theorem says: If you can organize all the dancers into a small number of "uphill ladders" (chains), then you know for a fact that no one can form a long "downhill slide."

The authors used this to prove that for very strict rules (where $k$ is 5 or higher), the "downhill slide" rule actually becomes redundant! If the circle is arranged nicely enough to avoid the "bad shapes," it automatically avoids the long downhill slides. It's like saying, "If you are wearing a helmet and knee pads, you don't need to worry about the specific rule about not riding your bike on the grass; you're already safe."

The Results: The Final Counts

After doing the heavy lifting, they gave us the exact formulas (the "guest lists") for how many valid dance circles exist:

• Case 1 (Strictness $k=3$): If we just want to avoid a 3-person downhill slide, the number of valid circles follows a specific curve (related to a famous sequence in math called A061925).
• Case 2 (Strictness $k=4$): If we want to avoid a 4-person downhill slide, the number is a mix of powers of 2 and simple subtraction (related to sequence A088921).
• Case 3 (Strictness $k \ge 5$): This was the surprise. Once the rule gets strict enough (avoiding 5-person slides), the answer becomes a clean, simple formula: $2^n + 1 - 2n - \binom{n}{3}$.

Why This Matters

In the world of math, "pattern avoidance" is like solving a giant puzzle where you have to find all the ways to arrange things without breaking a rule. It sounds abstract, but these patterns show up everywhere:

• Computer Science: Sorting data efficiently.
• Biology: Understanding how DNA sequences fold.
• Physics: Modeling particle interactions.

By solving this specific "locked door" (the 1432 case), the authors have added a crucial piece to the puzzle, showing us that even in a chaotic dance of numbers, there is a hidden, beautiful order waiting to be discovered. They didn't just guess; they built a logical bridge using the "Ladder Builder" and the "Detective's Logic" to cross the gap from "unknown" to "solved."

Technical Summary

Here is a detailed technical summary of the paper "On a question about pattern avoidance of cyclic permutations" by Zuo-Ru Zhang and Hongkuan Zhao.

1. Problem Statement

The paper addresses a specific problem in enumerative combinatorics concerning cyclic permutations subject to simultaneous pattern avoidance constraints.

• Context: Let $S_n$ be the symmetric group on $[n]$. A permutation $\pi$ is cyclic if it consists of a single $n$-cycle.
• Constraints: The authors study the set $A^\circ_n(\delta_k; \tau)$ of cyclic permutations $\pi \in S_n$ satisfying two conditions:
  1. One-line notation: The standard linear representation $\pi_1 \pi_2 \dots \pi_n$ avoids the decreasing pattern $\delta_k = k(k-1)\dots 21$.
  2. Cycle forms: All cyclic rotations of the standard cycle form $C(\pi) = (1, c_2, \dots, c_n)$ avoid a specific pattern $\tau$ of length 4.
• Specific Goal: Previous work by Archer et al. had resolved the cases where $\tau \in \{1324, 1342\}$. The case $\tau = 1432$ remained an open question. This paper aims to derive explicit enumeration formulas for $a^\circ_n(\delta_k; 1432)$ for all $k \ge 3$ and $n \ge 5$.

2. Methodology

The authors employ a combination of structural analysis of cycle forms, bijections, and order-theoretic tools.

• Characterization of Cycle Forms (Proposition 2.1):
  The core structural insight is that avoiding the pattern $1432$in *all* cyclic rotations is equivalent to the standard cycle form$C(\pi)$ avoiding the patterns 321 and 2143. This reduces the problem to analyzing permutations where the cycle form avoids these two specific patterns.

• Structural Lemmas (Lemma 2.2):
  The authors derive strict structural conditions for a cycle form $C(\pi) = (1, j, c_3, \dots, c_n)$ to avoid 321 and 2143:

  1. The sequence $2, 3, \dots, j-1$ must appear in increasing order.
  2. Elements greater than $j$ appearing between $j$ and $j-1$ must be increasing.
  3. Elements greater than $j$ appearing after $2$ must be increasing.

• Dilworth's Theorem Application:
  To handle the one-line notation constraint (avoiding $\delta_k$), the authors utilize Dilworth's Theorem. They define a partial order $S_\pi$ on $[n]$ where $i \le_\pi j$ if $i \le j$ and $\pi_i \le \pi_j$.

  • A decreasing subsequence of length $k$ in the one-line notation corresponds to an antichain of size $k$ in $S_\pi$.
  • By showing that the poset $S_\pi$ can be covered by $k-1$ chains, they prove that $\pi$ avoids $\delta_k$.

• Recursive Decomposition and Bijections:
  The enumeration is performed by fixing the second element of the cycle form, $j = c_2$.

  • Case $j=2$: A bijection is established between $A^\circ_{n,2}(\delta_k; 1432)$ and $A^\circ_{n-1}(\delta_k; 1432)$ by removing the element 2 and standardizing.
  • Case $j \ge 3$: The authors analyze specific structural configurations allowed by the avoidance of 321 and 2143, counting the valid permutations for each $j$ and summing them up.

3. Key Contributions and Results

The paper provides explicit closed-form formulas for the number of such permutations, denoted as $a^\circ_n(\delta_k; 1432)$, for $n \ge 5$.

Case 1: $k=3$ (Avoiding $\delta_3 = 321$)

• Result: $a^\circ_n(\delta_3; 1432) = \lfloor \frac{n^2 + 7}{2} \rfloor - 2n$.
• Significance: This sequence corresponds to OEIS A061925. The derivation involves summing contributions from $j=2$ (recursive), $j=3$ (linear growth), and $j \ge 4$ (quadratic growth).

Case 2: $k=4$ (Avoiding $\delta_4 = 4321$)

• Result: $a^\circ_n(\delta_4; 1432) = 2^{n-1} - \lfloor \frac{3n-5}{2} \rfloor$.
• Significance: This result combines exponential growth (from the structural freedom of avoiding 321/2143) with a linear correction term derived from the specific constraints of avoiding 4321.

Case 3: $k \ge 5$ (Avoiding $\delta_k$)

• Result: $a^\circ_n(\delta_k; 1432) = 2^n + 1 - 2n - \binom{n}{3}$.
• Key Insight (Lemma 4.1): The authors prove a crucial theorem: If a cyclic permutation's standard cycle form avoids 321 and 2143, its one-line notation automatically avoids $\delta_5$ (and consequently $\delta_k$ for all $k \ge 5$).
• Significance: This implies that for $k \ge 5$, the one-line restriction is redundant. The count is simply the total number of cyclic permutations whose cycle forms avoid 321 and 2143, a result previously established by Callan and Vella (OEIS A088921).

4. Significance

• Resolution of Open Problems: The paper successfully closes the open case $\tau = 1432$ left by Archer et al., completing the classification for length-4 patterns under these specific cyclic constraints.
• Methodological Advancement: It demonstrates the power of combining cycle form structural analysis with Dilworth's theorem to solve simultaneous pattern avoidance problems. The reduction of the "all rotations" condition to a condition on the "standard form" (avoiding 321 and 2143) is a pivotal simplification.
• Redundancy Discovery: The finding that avoiding $\delta_5$ is automatic for this class of permutations is a non-trivial structural result, simplifying the enumeration for all $k \ge 5$ to a known combinatorial sequence.
• OEIS Connections: The results link these specific permutation classes to established integer sequences (A061925, A088921), facilitating further research and cross-referencing in combinatorics.

In summary, Zhang and Zhao provide a rigorous combinatorial proof that resolves a specific open problem in pattern avoidance, utilizing deep structural properties of cyclic permutations and order theory to derive exact enumeration formulas.