🔢 mathematics

Partitions with parity restrictions: a bijective approach

This paper demonstrates that several identities concerning integer partitions with parity restrictions, which are typically proven using algebraic generating functions, can be established more simply through bijective methods.

Original authors: William Keith, Bruce E. Sagan

Published 2026-07-07

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: William Keith, Bruce E. Sagan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant box of LEGO bricks. In the world of mathematics, a "partition" is simply a way of stacking these bricks to build a tower of a specific height. The rules are simple: you can only stack them in rows, and each row must be the same length or shorter than the one above it.

This paper is a collection of clever tricks (called "bijections") invented by mathematicians William Keith and Bruce Sagan. Their goal? To prove that two different ways of building these LEGO towers result in the exact same number of possible towers, without doing any heavy math calculations. Instead of using complex formulas, they show you how to physically transform one tower into another, proving they are just two sides of the same coin.

Here is a breakdown of their main ideas using everyday analogies:

1. The "Odd and Even" Separation

Imagine you have a pile of LEGO bricks where some are "Odd" (1, 3, 5...) and some are "Even" (2, 4, 6...).

The Problem: The authors look at towers where all the Even bricks are smaller than all the Odd bricks (or vice versa).
The Trick: They show that if you have a tower with this specific rule, you can perform a simple "magic trick" to turn it into a tower made entirely of Even bricks, with just a few single "1" bricks added to the bottom.
The Result: This proves that counting these specific "separated" towers is exactly the same as counting towers made of only Even bricks and 1s. It's like showing that a box of mixed red and blue marbles, sorted by size, contains the same number of items as a box of just blue marbles and a few tiny red ones.

2. The "Lattice Path" Walk

To solve harder puzzles, the authors imagine the LEGO tower not as a stack, but as a walking path on a grid.

The Analogy: Imagine walking from the bottom-left to the top-right of a park. You can only take steps North (up) or East (right). The shape of your path traces the outline of the LEGO tower.
The Discovery: They found that certain rules about the LEGO bricks (like "odd parts must appear an even number of times") translate into very specific patterns in your walking path. For example, a rule about the bricks might mean your path must have a specific number of "North" steps before you turn "East."
The Result: By watching the walker, they can prove that the number of valid towers is either even or odd, depending on the total size of the tower. It's like realizing that if you walk a certain pattern, you will always end up with an even number of steps.

3. The "Two-Color" Party

The paper also looks at "Overpartitions," which are like LEGO towers where the very first brick of any color can be "overlined" (marked with a special hat).

The Analogy: Imagine a party where guests wear either Red or Blue shirts.
The Trick: The authors create a game where they take a group of guests with specific shirt rules (Overpartitions) and transform them into a group of guests with different shirt rules (Two-colored partitions).
The Result: They prove that the number of ways to arrange the "Overlined" guests is mathematically identical to the number of ways to arrange the "Red and Blue" guests, provided you follow their specific transformation rules.

4. The "Mirror" Effect (Self-Conjugate Towers)

Some towers look the same if you hold them up to a mirror (called "self-conjugate").

The Analogy: Imagine a snowflake. If you fold it in half, the left side matches the right side perfectly.
The Trick: The authors use a "swapping" game. If you have a tower that isn't a perfect mirror image, you can swap it with another tower that is a mirror image.
The Result: This helps them count how many towers have a specific property. If you can pair up every non-mirror tower with another non-mirror tower, the total count is even. If one is left over, the count is odd.

5. The "Mock Theta" Mystery

There is a famous mathematical object called a "Mock Theta Function." It's like a ghost of a pattern that almost behaves like a normal rhythm but has a glitch.

The Analogy: Imagine a song that sounds like it's in 4/4 time, but every now and then, the drummer hits a snare drum at a weird spot.
The Discovery: The authors show that the "glitchy" numbers in this song actually count specific types of LEGO towers (where even bricks are distinct and odd bricks follow a rule).
The Result: They built a bridge between this abstract musical glitch and the physical LEGO towers, showing that the "glitch" is actually just a different way of counting the same towers.

6. The "Triple" Puzzle

Finally, they look at groups of three towers (Triples).

The Analogy: Imagine three friends trying to build towers together.
The Trick: They use a "rotation" game. If you have a group of three towers that add up to an odd number, you can swap the first two friends' towers.
The Result: Because you can always swap them in pairs, the total number of ways to build these triplets is always an even number. It's like a dance where everyone finds a partner, so no one is left alone.

Summary

The paper is essentially a collection of mathematical magic tricks. Instead of using a calculator to prove that two groups of things are the same size, the authors show you how to turn one group into the other, step-by-step. They use LEGO towers, walking paths, and mirror images to make complex number theory feel like a set of logical puzzles you can solve with your hands.

What they did NOT do:

They did not apply these findings to medicine, engineering, or climate change.
They did not predict future trends.
They strictly stuck to proving that these specific counting problems are equal to each other using visual and logical transformations.

Title: Partitions with parity restrictions: a bijective approach
Authors: William Keith and Bruce E. Sagan

Problem Statement

The paper addresses the combinatorial study of integer partitions subject to specific parity restrictions on their parts. While numerous identities regarding such partitions (e.g., partitions where all odd parts are distinct, or where even parts are smaller than odd parts) have been established in the literature, they are frequently proven using algebraic manipulations of generating functions. The authors identify a gap in the literature regarding direct, combinatorial proofs for these identities. The central problem is to demonstrate that a significant number of these results can be proved bijectively, often providing simpler or more transparent explanations than their algebraic counterparts.

Methodology

The primary methodology employed throughout the paper is the construction of explicit bijections (one-to-one correspondences) between sets of partitions or related combinatorial objects. The authors utilize several specific tools and frameworks:

Direct Mapping: Constructing functions that transform partitions from one set to another by manipulating parts (e.g., subtracting 1 from odd parts, adding 1 to even parts) or rearranging multiplicities.
Lattice Path Models: Representing partitions as lattice paths in the plane (using East and North steps) to analyze properties like run lengths and conjugation. This includes the use of "double rectangles" and "double hooks" to define involutions on self-conjugate partitions.
Involution Principles: Defining involutions (maps that are their own inverse) on sets of partitions to prove parity results (e.g., showing a set has even cardinality by pairing elements, or identifying fixed points to count modulo 2).
Tableau Transformations: Utilizing Standard Young Tableaux (SYT) and the Robinson-Schensted correspondence to relate lattice paths (Dyck, Motzkin, Riordan) to partition shapes with restricted row lengths.
Overpartitions and Two-Colored Partitions: Extending bijections to overpartitions (where the first occurrence of a part may be overlined) and two-colored partitions to establish identities involving these structures.

Key Contributions and Results

The paper is structured into eight main sections, each addressing specific families of partition identities:

Parity-Separated Parts (Section 2):
- The authors provide bijective proofs for identities relating partitions where even parts are smaller than odd parts ( $P^o_e$ ) to partitions with parts restricted to even numbers or 1 ( $P_{e,1}$ ), and to "palindromic" partitions ( $P_p$ ).
- They prove a theorem by Andrews relating partitions with odd parts smaller than even parts (excluding 1s) to the difference between partitions into all odd parts and all even parts.
Multiplicity Restrictions (Section 3):
- A bijective proof is given for a result by Chern concerning partitions where odd parts have even multiplicity and even parts have specific multiplicity constraints. The authors prove that for $n \equiv 2 \pmod 4$ , the number of such partitions with the largest even part congruent to 0 mod 4 equals those congruent to 2 mod 4.
- They provide a combinatorial proof for the parity of the total count of such partitions, identifying fixed points of an involution related to specific self-conjugate partitions ( $\phi_k$ and $\tilde{\phi}_k$ ).
- Analogous results for overpartitions are also established.
Restricted Overpartitions (Section 4):
- The paper proves an identity by Banerjee, Bringmann, and Dixit relating a set of restricted overpartitions to two-colored partitions. The bijection maps these structures to a union of standard partitions and partitions with a zero appended.
Third Order Mock Theta Function (Section 5):
- The authors provide combinatorial proofs connecting the coefficients of the third-order mock theta function $\nu(q)$ $ν (q)$ to three distinct sets of objects:
  - Partitions with distinct even parts and specific odd part constraints (Set $A$ ).
  - Odd Ferrers graphs of self-conjugate partitions (Set $B$ ).
  - Self-conjugate partitions with all odd parts (Set $C$ ).
- Explicit bijections are constructed between these sets.
Distinct vs. Repeated Parts (Section 6):
- A combinatorial proof is offered for an identity by Bringmann and Jennings-Shaffer comparing partitions with distinct even parts and unrestricted odd parts against other parity-restricted classes.
Partition Triples (Section 7):
- The authors generalize a congruence result by Guadalupe regarding partition triples. They prove that the number of such triples summing to an odd integer is even, using a simple involution that swaps the first two components. This is extended to any prime modulus using cyclic group actions.
Parity-Rstricted Tableau Shapes (Section 8):
- The paper connects lattice paths (Dyck, Motzkin, Riordan) to Standard Young Tableaux with restricted shapes.
- Bijective proofs are provided for results by Matsakis and Vendervelde (relating Motzkin paths to SYTs with at most 3 rows) and Hemmer, Straub, and Westrem (relating Riordan paths to SYTs with parity-restricted row lengths).

Significance and Claims

The paper claims that its primary significance lies in shifting the proof paradigm for partition identities from algebraic manipulation to bijective combinatorics. The authors argue that these bijective proofs are often "simpler" and offer deeper structural insight into why the identities hold.

Specifically, the paper:

Answers open questions: It provides combinatorial proofs for results by Chern, Banerjee et al., and Bringmann et al., which were previously derived via generating functions.
Generalizes results: It extends a congruence result by Guadalupe to any prime modulus using group actions.
Identifies open problems: The authors explicitly state in Section 9 that they were unable to find bijective proofs for certain identities, specifically:
- A simpler injection for the inequality $v^o_e(n, 0) \ge v^o_e(n, 2)$ when $n \equiv 0 \pmod 4$ .
- A direct bijection between the fourth class of partitions ( $D(n)$ ) counted by the mock theta function and the other classes ( $A, B, C$ ).
- Bijective proofs for the remaining inequalities in the asymptotic ordering of partition sets with distinct/repeated parts.

The paper concludes by presenting these open problems as challenges for the reader, maintaining a modest tone regarding the completeness of the bijective approach for all known identities in this domain.