Parity patterns meet Genocchi numbers, I: four labelings and three bijections

Basic Information

• Paper ID: 2510.13258
• Title: Parity patterns meet Genocchi numbers, I: four labelings and three bijections
• Authors: Quan Yuan, Qi Fang, Shishuo Fu, Haijun Li
• Classification: math.CO (Combinatorics), cs.DM (Discrete Mathematics)
• Publication Date: October 15, 2025
• Paper Link: https://arxiv.org/abs/2510.13258

Abstract

This paper investigates the deep connections between parity patterns and Genocchi numbers. Building upon the homogenized Linial arrangement introduced by Hetyei in 2019 and the hyperplane arrangement related to Ferrers diagrams proposed by Lazar-Wachs, the authors establish bijective labelings of regions in hyperplane arrangements through permutation models with parity restrictions. This not only establishes the equivalence of enumeration results by Hetyei and Lazar-Wachs, but also derives and studies a Seidel-type triangle intertwining two types of Genocchi numbers.

Research Background and Motivation

Problem Background

1. Significance of Genocchi Numbers: Genocchi numbers $\{g_n\}_{n≥1} = \{1,1,3,17,155,2073,38227,...\}$ and median Genocchi numbers $\{h_n\}_{n≥0} = \{1,2,8,56,608,9440,...\}$ are important in number theory, combinatorics, and geometry.
2. Geometric Development: Hetyei (2019) proved via finite field methods that the number of regions of the homogenized Linial arrangement is counted by median Genocchi numbers. Lazar and Wachs introduced a hyperplane arrangement related to Ferrers diagrams to provide an alternative proof.
3. Need for Combinatorial Interpretation: Although multiple combinatorial interpretations of Genocchi numbers exist, there is a lack of unified bijective methods to establish connections between different results.

Research Motivation

• Establish bijective equivalence between Hetyei and Lazar-Wachs results
• Discover new permutation models through parity pattern restrictions
• Construct Seidel-type triangles to deepen understanding of Genocchi number structure

Core Contributions

1. Four Permutation Labelings: Construct four distinct bijective labelings of regions in hyperplane arrangement $K_{2n}$, using four classes of parity patterns avoiding permutations.
2. Seidel-type Triangle: Derive a new triangular array intertwining two types of Genocchi numbers and prove related recurrence relations.
3. Three Bijective Maps: Establish bijective relationships between new permutation models and known models (Dumont type III permutations, folded permutations).
4. Theoretical Unification: Prove that the two superficially different enumeration results of Hetyei and Lazar-Wachs are essentially equivalent.

Methodology Details

Core Definitions

Definition 1 (Parity Patterns): For consecutive pairs $(\pi_i, \pi_{i+1})$ in a permutation, define eight parity patterns:

• eE, eO, oE, oO (ascending patterns)
• Ee, Eo, Oe, Oo (descending patterns)

where e denotes even, o denotes odd, and E/O denotes larger even/odd.

Definition 2 ($G^I_{2n}$): $G^I_{2n} := \{\pi \in S_{2n} : \pi \text{ avoids parity patterns } eE, eO, oO\}$

Equivalently, $\pi \in G^I_{2n}$ if and only if every ascent $\pi_i < \pi_{i+1}$ satisfies $\pi_i$ is odd and $\pi_{i+1}$ is even.

Hyperplane Arrangement

$K_{2n}$ Arrangement: $K_{2n} := \{x_{2i-1} - x_{2j} = 0 : 1 ≤ i ≤ j ≤ n\}$

This is a hyperplane arrangement in $\mathbb{R}^{2n+1}$ whose number of regions equals the median Genocchi number $h_n$.

Insertion Algorithm

Algorithm IA-I: Core algorithm for constructing bijection $\Lambda^I : R(K_{2n}) \to G^I_{2n}$

1. Bad Pair Identification: For an odd pair $(i,j)$, if $i$ precedes $j$ but $x_j < x_{2n+2} < x_i$, it is called a bad pair.
2. Correction Steps:
   • Find the rightmost endpoint $j$ of bad pairs
   • Remove all starting points of bad pairs ending at $j$
   • Insert removed elements to the right of $j$
3. Insertion of New Elements: Decide insertion method based on the size relationship between $x_{2n+1}$ and $x_{2n+2}$.

Other Three Models

$G^{II}_{2n}$: Avoids Ee, eO, oO, but allows special initial Oe patterns.

$G^{III}_{2n}$: Avoids Oo, eE and generalized eO patterns (eO patterns at distance d≥0).

$G^{IV}_{2n}$: Avoids eO and generalized Oo_d, Ee_d patterns.

Theoretical Results

Main Theorems

Theorem 1.4: For any $n ≥ 1$, the regions of hyperplane arrangement $K_{2n}$ can be bijectively labeled with permutations in $G^I_{2n}$ via mapping $\Lambda^I$.

Theorem 1.5: Recurrence relations for the Seidel-type triangle

• $G^I_{2n,1} = G^I_{2n,2}$
• $G^I_{2n,3} = 2(G^I_{2n,1} + G^I_{2n-2,1})$
• $G^I_{2n,2n} = G^I_{2n-2}$
• $G^I_{2n,2k} = S_{2n,n+1-k}$ (connection with classical Seidel triangle)

Theorem 1.6: For $n ≥ 2, n > k ≥ 0$: $G^I_{2n,2k+2} = G^I_{2n,2k} + \sum_{i=k}^{n-1} G^I_{2n-2,2i}$

Seidel-type Triangle

The constructed triangular array satisfies generation rules similar to the classical Seidel triangle but with new combinatorial significance:

Bijective Constructions

First Bijection: $\Phi: G^I_{2n,2k} \to D^{III}_{2n,2k}$

Constructed recursively using two auxiliary bijections:

• $\phi$: Realizes the recurrence relation in Theorem 1.6
• $\varphi$: Realizes the recurrence relation of the Seidel triangle

Second Bijection: $\theta: CO_{2n+2} \to D_{2n}$

Folded Permutations to D-permutations: $\theta(\pi) = \sigma, \text{ where } \sigma_{2i-1} := \pi_{n+i+1} - 1, \sigma_{2i} := \pi_{i+1} - 1$

Third Bijection: $\vartheta: G^I_{2n} \to D_{2n}$

Two-step Construction:

1. Partition into cycles by left-to-right minima and reverse
2. Right-shift even cycle double-ascent elements within each cycle

Experimental Verification

Small-scale Verification

• $G^I_2 = \{12, 21\}$, $|G^I_2| = 2 = h_1$
• $G^I_4 = \{1432, 2143, 3142, 3214, 3412, 3421, 4312, 4321\}$, $|G^I_4| = 8 = h_2$

Recurrence Relation Verification

Verified the generation rules of the Seidel-type triangle and its connection with the classical Seidel triangle through computation.

Related Work

Historical Development

1. Dumont (1974): First combinatorial interpretation of Genocchi numbers
2. Hetyei (2019): Introduction of homogenized Linial arrangement
3. Lazar-Wachs (2023): Proposal of even-odd drop condition

Related Models

• Dumont permutations (four types)
• D-permutations and E-permutations
• Folded permutations
• X-permutations

Conclusions and Discussion

Main Conclusions

1. Successfully establish four distinct permutation models for labeling hyperplane arrangement regions
2. Prove equivalence of Hetyei and Lazar-Wachs results
3. Construct new Seidel-type triangle revealing deep structure of Genocchi numbers
4. Establish bijective relationships with known permutation models

Limitations

1. Definitions of some permutation models ($G^{II}, G^{III}, G^{IV}$) are relatively complex
2. Implementation of insertion algorithm requires careful handling of multiple cases
3. Theoretical analysis primarily focuses on existence proofs with limited computational complexity analysis

Future Directions

1. Subsequent Work: Authors mention investigating another three Seidel-type triangles in follow-up work
2. Normalization Research: Explore combinatorial interpretations of median Genocchi numbers divisible by $2^n$
3. Generalization Applications: Extend methods to other hyperplane arrangements and sequences

In-depth Evaluation

Strengths

1. Theoretical Depth: Establishes profound connections between hyperplane arrangement geometry and permutation combinatorics
2. Methodological Innovation: Introduction of parity patterns provides new perspective for studying permutations
3. Result Unification: Elegantly unifies superficially different enumeration results
4. Constructive Proofs: All bijections are given explicit algorithmic descriptions

Weaknesses

1. Technical Complexity: Some definitions and algorithms are relatively complex, potentially affecting accessibility
2. Application Scope: Primarily theoretical results with limited practical applications
3. Computational Efficiency: Algorithm computational complexity not discussed

Impact

1. Academic Value: Provides new combinatorial tools for Genocchi number research
2. Methodological Contribution: Parity pattern method may apply to research on other sequences
3. Follow-up Research: Establishes foundation for further study of normalized Genocchi numbers

Applicable Scenarios

• Enumeration problems in combinatorics
• Region counting in hyperplane arrangements
• Permutation pattern avoidance problems
• Combinatorial interpretations of special sequences

References

Main references include:

1. Hetyei (2019): Original work on homogenized Linial arrangement
2. Lazar & Wachs (2023): Even-odd drop condition and related conjectures
3. Dumont (1974): Classical combinatorial interpretation of Genocchi numbers
4. Related literature on permutation patterns and hyperplane arrangements

Overall Assessment: This is a high-quality theoretical paper in combinatorics that establishes profound connections between hyperplane arrangements and permutation combinatorics through the introduction of parity patterns, providing new tools and perspectives for Genocchi number research. While technical details are relatively complex, the theoretical contributions are significant and lay important foundations for further research in related fields.