Counting permutations avoiding two flat partially ordered patterns

Imagine you are a master chef trying to create a perfect sequence of dishes for a banquet. In the world of mathematics, these "dishes" are permutations—just different ways of arranging a list of numbers (like 1, 2, 3, 4, 5).

Usually, mathematicians study "forbidden patterns." It's like saying, "No matter how you arrange your dishes, you cannot have a sequence where the appetizer is bigger than the main course, which is bigger than the dessert." If you follow this rule, you are "avoiding" a specific pattern.

This paper is about a much stricter challenge: avoiding two forbidden patterns at the same time.

Here is a simple breakdown of what the authors did, using some everyday analogies:

1. The Rules of the Game (The "Flat" Patterns)

The authors are looking at two specific types of forbidden patterns called Flat POPs (Partially Ordered Patterns).

Think of a pattern as a specific "shape" or "mood" that a sequence of numbers can take.
One pattern ( $P_j$ ) is like a rule that says: "You can't have a big number followed by a bunch of smaller numbers in a specific order."
The other pattern ( $\tilde{P}_\ell$ ) is the mirror image: "You can't have a small number followed by a bunch of bigger numbers in a specific order."

The goal is to count how many ways you can arrange a list of numbers (say, 1 to $n$ ) so that neither of these bad shapes appears anywhere in your list.

2. The "Fibonacci" Connection (The Magic Count)

In the first part of the paper, the authors discovered a surprising link to the Fibonacci numbers (the famous sequence: 0, 1, 1, 2, 3, 5, 8, 13...).

The Analogy: Imagine you are climbing a staircase. You can take 1 step or 2 steps at a time. The number of ways to reach the top is a Fibonacci number.
The authors found that if you are avoiding just one of these specific patterns (and its mirror), the number of valid arrangements follows a generalized version of this staircase rule (called k-Fibonacci numbers). It's like you have more options for your steps, but the logic remains the same.

3. The "Restricted" Permutations (The Hallway Analogy)

To solve the harder problem of avoiding both patterns, the authors used a clever trick. They realized that avoiding these two patterns is mathematically the same as arranging people in a hallway with strict rules about how far they can stand from their assigned spot.

The Analogy: Imagine $n$ people are assigned seats numbered 1 to $n$ .
The Rule: Person number $i$ is only allowed to sit in a seat that is within a certain distance of their assigned number. They can't sit too far to the left or too far to the right.
The authors proved that counting the "safe" arrangements for the patterns is exactly the same as counting the "safe" arrangements in this hallway. This allowed them to use existing mathematical tools (developed by a researcher named Baltić) to solve the puzzle.

4. The "Separable" Permutations (The Lego Blocks)

The paper focuses on a special group of permutations called Separable Permutations.

The Analogy: Think of these as structures built entirely out of Lego blocks. You can only build them by stacking two smaller blocks on top of each other (Direct Sum) or placing them side-by-side (Skew Sum). You cannot build them by twisting or interlocking them in complex ways.
The authors wanted to know: "If we build our Lego tower using only these specific blocks, and we also follow the 'no bad patterns' rule, how many different towers can we make?"

5. The Result: A Giant Recipe Book (Generating Functions)

The main achievement of the paper is creating a "recipe" (called a Generating Function) that tells you exactly how many valid arrangements exist for any length of the list.

The Complexity: When the forbidden patterns are short (length 3 or 4), the recipe is relatively simple, like a standard cake recipe.
The Explosion: When the patterns get longer (length 5), the recipe becomes incredibly complex. The authors found that for the longest patterns they studied, the "recipe" (a mathematical fraction) has a numerator (the top part) with 293 different ingredients (monomials) and a denominator (the bottom part) with 17 ingredients.
Why it matters: Even though the formula looks like a mess of numbers and letters, it is a precise, rational function. This means it's not random chaos; it's a highly structured, solvable equation that describes a very complex system.

Summary

The authors took a difficult problem (counting arrangements that avoid two complex rules), found a way to translate it into a simpler problem (people in a hallway), and then used that to build a massive, detailed mathematical map (generating functions) for a specific type of arrangement (separable permutations).

They showed that while the rules get stricter and the math gets messier as the patterns get longer, there is still a beautiful, logical structure underneath the complexity, connecting it all back to the famous Fibonacci numbers.

Here is a detailed technical summary of the paper "Counting permutations avoiding two flat partially ordered patterns."

1. Problem Statement

The paper addresses the combinatorial enumeration of permutations that simultaneously avoid two specific types of Partially Ordered Patterns (POPs).

Context: While the enumeration of permutations avoiding a single POP is well-studied (notably by Gao and Kitaev for lengths 4 and 5), the simultaneous avoidance of two POPs is a more complex, less explored problem.
Specific Patterns: The authors focus on flat POPs, denoted as $P_j$ and $\tilde{P}_\ell$ (where $j, \ell \ge 2$ ). These patterns are defined by specific poset structures (visualized in Figure 1 of the paper) where elements form a chain with specific ordering constraints.
Scope: The study focuses on:
1. General permutations in $S_n$ avoiding both $P_j$ and $\tilde{P}_\ell$ .
2. Separable permutations (those avoiding the classical patterns 2413 and 3142) that simultaneously avoid $P_j$ and $\tilde{P}_\ell$ .
Goal: To derive generating functions (g.f.) for these sets, establish connections to known combinatorial sequences (like $k$ -Fibonacci numbers), and analyze the joint distribution of six specific statistics: ascents, descents, left/right-to-right maxima/minima.

2. Methodology

The authors employ a multi-faceted approach combining structural decomposition, bijection, and functional equations.

Structural Decomposition (Stankova's Decomposition):
For separable permutations, the authors utilize Stankova's decomposition (Figure 2), which represents a permutation $\pi$ as a sequence of blocks $L_1 \dots L_m \ominus R_m \dots R_1$ . This recursive structure allows the authors to build permutations from smaller components while tracking the avoidance of the forbidden patterns.
Connection to Restricted Permutations:
Theorem 3.1 establishes a crucial bijection: A permutation $\pi$ avoids $P_j$ and $\tilde{P}_\ell$ if and only if it is a restricted permutation satisfying the condition:
$-\ell + 2 \le \pi_i - i \le j - 2$
This links the problem to the enumeration of restricted permutations $N(n, a, b)$ , a problem previously addressed by Kløve and Baltić.
Connection to $k$ -Fibonacci Numbers:
In Section 2, the authors prove that for the specific case of avoiding $P_j$ and $\tilde{P}_3$ (or $P_3$ and $\tilde{P}_j$ ), the number of such permutations corresponds to the $(j-1)$ -Fibonacci numbers ( $F^{(j-1)}_{n+1}$ ). This generalizes the classical Fibonacci result for avoiding 231, 312, and 321.
System of Functional Equations:
To handle the joint distribution of statistics (ascents, descents, etc.) for separable permutations, the authors derive a system of functional equations (Theorem 4.2).
- They define auxiliary generating functions $f_{j,\ell,i}$ and $g_{j,\ell,i}$ based on the position of the element $n$ and $n-1$ relative to the decomposition blocks.
- By analyzing the cases where $n-1$ is to the left or right of $n$ , they construct recursive relations involving coefficients $U_n, V_n, W_n, Y_n, Z_n$ derived from simpler generating functions.
- This system is solved explicitly for small values of $j$ and $\ell$ (specifically $3 \le j, \ell \le 5$).

3. Key Contributions and Results

A. General Permutations

Theorem 2.1: Proves that $|S_n(P_j, \tilde{P}_3)| = F^{(j-1)}_{n+1}$ . This connects the avoidance of these specific flat POPs directly to the $k$ -Fibonacci sequence.
Theorem 3.1: Provides the necessary and sufficient condition for a permutation to avoid $P_j$ and $\tilde{P}_\ell$ in terms of the displacement of elements ( $\pi_i - i$ ), linking the problem to restricted permutations.

B. Separable Permutations and Generating Functions

The paper provides explicit rational generating functions for separable permutations avoiding pairs of patterns $(P_j, \tilde{P}_\ell)$ for $3 \le j, \ell \le 5 $. The generating function$ F_{j,\ell}$ tracks six statistics simultaneously.

Case $j=\ell=3$ : The generating function is rational. The count of such permutations follows the standard Fibonacci sequence ($1, 1, 2, 3, 5, \dots$).
Case $j=3, \ell=4$ : The count follows a sequence defined by $1/(1-x-x^2-x^3)$.
Case $j=3, \ell=5$ : The count follows $1/(1-x-x^2-x^3-x^4)$.
Complex Cases ( $j, \ell \ge 4$ ):
- $j=\ell=4$ : The generating function is a rational function with a numerator containing 49 monomials and a denominator with 7 monomials.
- $j=4, \ell=5$ : The numerator has 93 monomials; the denominator has 10.
- $j=\ell=5$ : The complexity peaks here. The generating function is a rational function where the numerator contains 293 monomials and the denominator contains 17 monomials.

C. Statistical Distribution

The authors extend previous work by Gao et al. by providing the joint distribution of six statistics:

$\text{asc}(\pi)$ : Number of ascents.
$\text{des}(\pi)$ : Number of descents.
$\text{lmax}(\pi)$ : Left-to-right maxima.
$\text{rmax}(\pi)$ : Right-to-left maxima.
$\text{lmin}(\pi)$ : Left-to-right minima.
$\text{rmin}(\pi)$ : Right-to-left minima.

The symmetry $F_{j,\ell}(x, p, q, u, v, s, t) = F_{\ell,j}(x, p, q, t, s, v, u)$ is established, reflecting the duality between reverse and complement operations.

4. Significance and Conclusion

Extension of Literature: This work significantly extends the known results on POP-avoiding permutations from single patterns to pairs of flat POPs, specifically within the class of separable permutations.
Complexity Analysis: The paper highlights a sharp increase in complexity when moving from length 3 to length 4 and 5 patterns. The explosion in the number of monomials in the generating functions (from a few to nearly 300) illustrates the difficulty of generalizing these results to arbitrary $j$ and $\ell$ .
Open Problems: The authors note that while they solved the problem for $j, \ell \le 5$ , a general system of equations for arbitrary $j, \ell \ge 4$ remains an open problem. They suggest that the increasing number of cases in the structural decomposition makes a general solution computationally challenging.
Methodological Impact: The successful application of Stankova's decomposition combined with the method of restricted permutations (Baltić's approach) provides a robust framework for future studies on multi-pattern avoidance in permutation classes.

In summary, the paper provides a comprehensive enumeration of permutations avoiding two specific flat POPs, establishing deep connections to $k$ -Fibonacci numbers and restricted permutations, while delivering explicit, albeit complex, generating functions for the joint distribution of key permutation statistics.