pith. sign in

arxiv: 2510.26168 · v2 · submitted 2025-10-30 · 🧮 math.CO

Enumeration of pattern-avoiding (0,1)-matrices and their symmetry classes

Sen-Peng Eu , Yi-Lin Lee This is my paper

Pith reviewed 2026-05-18 03:39 UTC · model grok-4.3

classification 🧮 math.CO
keywords pattern-avoiding matricesI_k-avoidingplane partitionssymmetry classeslattice pathsdihedral groupenumeration formulas
0
0 comments X

The pith

Maximal I_k-avoiding (0,1)-matrices correspond bijectively to plane partitions of a fixed size via non-intersecting lattice paths.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper interprets maximal I_k-avoiding (0,1)-matrices as families of non-intersecting lattice paths on the square lattice. This perspective produces a bijection that shows these matrices are equinumerous with plane partitions of a certain size. The same view also lets the authors classify all ten symmetry classes of the matrices under the dihedral group of order 8 and prove that each class is counted by a simple product formula.

Core claim

Maximal I_k-avoiding (0,1)-matrices (IAMs) are in bijection with plane partitions of a certain size, and the ten symmetry classes of IAMs under the dihedral group action each admit explicit product enumeration formulas. The same lattice-path approach yields a conceptual formula for maximal I_k-avoiding (0,1)-fillings of skew shapes.

What carries the argument

The representation of IAMs as families of non-intersecting lattice paths on the square lattice, which supplies the bijection to plane partitions.

Load-bearing premise

Maximal I_k-avoiding (0,1)-matrices can be interpreted as families of non-intersecting lattice paths on the square lattice.

What would settle it

Count the maximal I_k-avoiding (0,1)-matrices for a small fixed k such as k=2 or k=3 and verify whether the total equals the number of plane partitions fitting inside a box whose dimensions are determined by the matrix size.

Figures

Figures reproduced from arXiv: 2510.26168 by Sen-Peng Eu, Yi-Lin Lee.

Figure 1
Figure 1. Figure 1: (a) A plane partition π ∈ PP(5, 3, 4). (b) Viewing π as a pile of unit cubes in the 5 × 3 × 4 box. (c) The non-intersecting paths encoding of π. (d) The corresponding non-intersecting lattice paths of π which is obtained from deforming the paths in [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: An illustration of two staircases of size k −1 in a matrix. The “diagonal” entries of staircases are labeled ℓi ’s and ri ’s, and the entries marked ∗ must be filled with 1’s. length is given by m + n − 1. Now, the second longest one connects ℓi2 and ri2 for some i2 ≠ i1, and passes through k − 3 entries2 in both lower left and upper right staircases, respectively. Continuing this argument, we arrive at th… view at source ↗
Figure 3
Figure 3. Figure 3: Two different decompositions of a matrix in M9,7;5 into 4 zigzag paths. Lemma 2.2. The set of maximal Ik-avoiding (0, 1)-matrices of size m × n Mm,n;k is in bijection with the set of zigzag paths p ′ 1 , p′ 2 , . . . , p′ k−1 , where p ′ i starts at the entry ℓi = (m−i+1, k −i) and ends at the entry ri = (k − i, n − i + 1). Proof. From the above discussion and Lemma 2.1, it is clear that a matrix in Mm,n;k… view at source ↗
Figure 4
Figure 4. Figure 4: An example of extending zigzag paths in a decomposition of Z6 (left) to a decomposition of Z7 (right). 2.3 The weighted enumeration of maximal Ik-avoiding (0, 1)-matrices We define two statistics on our matrix below. Let M = [Mi,j ] be a matrix in Mm,n;k. For an entry Mi,j = 0, define v(Mi,j) = ∣{d > 0∣Mi+d,j+d = 1}∣. (2.1) That is, for each Mi,j = 0, the value v(Mi,j) counts the number of 1’s lying strict… view at source ↗
Figure 5
Figure 5. Figure 5: A matrix in M∗ 9,12;5, where ∗ = HS, V S, V HS, QT S, or T S. The 1’s in the four staircases are marked blue. The four zigzag paths are presented in four different colors. This completes the proof of Theorem 1.2. In the work of Ciucu [10], four intriguing product relations for the number of symmetry classes of plane partitions have been discovered. We close this section by pointing out similar product rela… view at source ↗
Figure 6
Figure 6. Figure 6: (a) A maximal I5-avoiding (0, 1)-filling of R¯ 9,12;t , where t = 9−5. (b) The corresponding non-intersecting lattice paths. Note that paths can only stay weakly above the blue line. Proof of Theorem 1.3. We assume t = m−k or m−k +1. Using the idea of the proof of Theorem 1.1 and the discussion at the beginning of this section, the set FR¯m,n;t;k of maximal Ik-avoiding (0, 1)- fillings of R¯m,n;t ; k is in… view at source ↗
read the original abstract

Recently, Brualdi and Cao studied $I_k$-avoiding $(0,1)$-matrices by decomposing them into zigzag paths and proved that the maximum number of $1$'s in such a matrix is given by an exact formula. We further study the structure of maximal $I_k$-avoiding $(0,1)$-matrices (IAMs) by interpreting them as families of non-intersecting lattice paths on the square lattice. Using this perspective, we establish a bijection showing that IAMs are equinumerous with plane partitions of a certain size. Moreover, we classify all ten symmetry classes of IAMs under the action of the dihedral group of order $8$ and show that the enumeration formulas for these classes are given by simple product formulas. Extending this approach to skew shapes, we derive a conceptual formula for enumerating maximal $I_k$-avoiding $(0,1)$-fillings of skew shapes.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper interprets maximal I_k-avoiding (0,1)-matrices (IAMs) as families of non-intersecting lattice paths, establishes a bijection showing they are equinumerous with plane partitions of a certain size, classifies all ten symmetry classes under the dihedral group of order 8 with explicit product formulas for each, and extends the approach to give a conceptual enumeration formula for maximal I_k-avoiding fillings of skew shapes.

Significance. If the bijection and classifications hold, the work supplies closed-form enumerations for IAMs and their orbits, connecting pattern-avoiding matrices to the classical theory of plane partitions and providing a uniform treatment of symmetry classes that may facilitate further study of group actions in combinatorial matrix enumeration.

major comments (1)
  1. [lattice-path interpretation and bijection] The lattice-path model for maximal IAMs (described after the abstract and developed in the main enumeration section): the bijection to plane partitions must explicitly verify that non-intersection and endpoint data simultaneously enforce both I_k-avoidance and maximality; without a direct check that no forbidden submatrix is introduced or omitted by the path encoding, the equinumerosity claim and all ten symmetry-class formulas rest on an unverified correspondence.
minor comments (2)
  1. A summary table listing the ten symmetry classes, their stabilizers, and the corresponding product formulas would improve readability of the classification results.
  2. [skew-shape extension] The extension to skew shapes is stated conceptually; adding a brief example computation for a small skew shape would help confirm the formula applies as claimed.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for the constructive comment on the lattice-path bijection. We address this point below and are happy to revise the paper to make the verification more explicit.

read point-by-point responses

  1. Referee: [lattice-path interpretation and bijection] The lattice-path model for maximal IAMs (described after the abstract and developed in the main enumeration section): the bijection to plane partitions must explicitly verify that non-intersection and endpoint data simultaneously enforce both I_k-avoidance and maximality; without a direct check that no forbidden submatrix is introduced or omitted by the path encoding, the equinumerosity claim and all ten symmetry-class formulas rest on an unverified correspondence.

    Authors: We appreciate the referee's emphasis on a direct verification of the correspondence. The manuscript defines the lattice-path model by mapping a maximal I_k-avoiding (0,1)-matrix to a family of non-intersecting paths whose starting and ending points are fixed by the positions that achieve the maximum number of 1's permitted by I_k-avoidance (as previously determined by Brualdi and Cao). Non-intersection of the paths is shown to be equivalent to the absence of an I_k submatrix, while the endpoint data enforces maximality by construction. Nevertheless, to address the concern directly, we will add a dedicated lemma in the enumeration section that explicitly proves the two directions: (i) every non-intersecting path family with the prescribed endpoints yields a maximal I_k-avoiding matrix, and (ii) every maximal I_k-avoiding matrix arises uniquely from such a path family. This lemma will include a short case analysis confirming that neither forbidden submatrices nor non-maximal configurations can arise from the encoding. With this addition the equinumerosity with plane partitions and the product formulas for all ten symmetry classes rest on a fully verified bijection. We therefore mark this revision as 'yes'. revision: yes

Circularity Check

0 steps flagged

No circularity: bijection and orbit classification are independent combinatorial constructions

full rationale

The paper starts from the prior decomposition of I_k-avoiding matrices into zigzag paths (Brualdi-Cao) and then defines a new lattice-path model for the maximal cases. From this model it constructs an explicit bijection to plane partitions of fixed size and enumerates the ten dihedral orbits by direct orbit-stabilizer counting, yielding product formulas. Neither step is a redefinition of the input, a fitted parameter renamed as a prediction, nor a load-bearing self-citation; the bijection and formulas are derived from the path interpretation and group action without reducing to the original avoidance condition by construction. The derivation is therefore self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard facts about lattice paths and group actions together with the domain assumption that maximal avoiding matrices admit a non-intersecting path decomposition.

axioms (2)
  • standard math The dihedral group of order 8 acts on (0,1)-matrices by rotations and reflections.
    Invoked when classifying the ten symmetry classes.
  • domain assumption Maximal I_k-avoiding (0,1)-matrices admit a decomposition into families of non-intersecting lattice paths.
    This structural claim is the foundation for the bijection to plane partitions.

pith-pipeline@v0.9.0 · 5694 in / 1497 out tokens · 44163 ms · 2026-05-18T03:39:06.115358+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

37 extracted references · 37 canonical work pages · 2 internal anchors

  1. [1]

    Solution directe du probleme r´ esolu par M

    D´ esir´ e Andr´ e. Solution directe du probleme r´ esolu par M. Bertrand. CR Acad. Sci. Paris , 105(1):436–437, 1887. ENUMERATION OF PATTERN-A VOIDING ( 0, 1) -MATRICES AND THEIR SYMMETRY CLASSES 17

    work page

  2. [2]

    George E. Andrews. Macmahon’s conjecture on symmetric p lane partitions. Proceedings of the National Academy of Sciences of the United States of America , 74(2):426–429, 1977

    work page 1977

  3. [3]

    Behrend, Ilse Fischer, and Christoph Koutschan

    Roger E. Behrend, Ilse Fischer, and Christoph Koutschan . Diagonally symmetric alternating sign matrices, 2023. https://arxiv.org/abs/2309.08446

    work page arXiv 2023

  4. [4]

    Discrete Mathematics and its Applications (Boca Raton)

    Mikl´ os B´ ona.Combinatorics of permutations . Discrete Mathematics and its Applications (Boca Raton). C RC Press, Boca Raton, FL, third edition, 2022. With a foreword b y Richard Stanley

    work page 2022

  5. [5]

    Brualdi and Lei Cao

    Richard A. Brualdi and Lei Cao. Pattern-avoiding ( 0, 1) -matrices and bases of permutation matrices. Discrete Appl. Math. , 304:196–211, 2021

    work page 2021

  6. [6]

    William Y. C. Chen, Eva Y. P. Deng, Rosena R. X. Du, Richard P. Stanley, and Catherine H. Yan. Crossings and nestings of matchings and partitions. Trans. Amer. Math. Soc. , 359(4):1555–1575, 2007

    work page 2007

  7. [7]

    Extremal combinatorics of matrices, seq uences and sets of permutations

    Josef Cibulka. Extremal combinatorics of matrices, seq uences and sets of permutations. Doctoral thesis, Charles University in Prague , 2013

    work page 2013

  8. [8]

    Enumeration of perfect matchings in graphs with reflective symmetry

    Mihai Ciucu. Enumeration of perfect matchings in graphs with reflective symmetry. J. Combin. Theory Ser. A , 77(1):67–97, 1997

    work page 1997

  9. [9]

    Symmetry classes of spanning trees of Aztec diamonds and perfect matchings of odd squares with a unit hole

    Mihai Ciucu. Symmetry classes of spanning trees of Aztec diamonds and perfect matchings of odd squares with a unit hole. J. Algebraic Combin. , 27(4):493–538, 2008

    work page 2008

  10. [10]

    Four factorization formulas for plane par titions

    Mihai Ciucu. Four factorization formulas for plane par titions. Proc. Amer. Math. Soc. , 144(5):1841–1856, 2016

    work page 2016

  11. [11]

    k-noncrossing and k-nonnesting graphs and fillings of Ferrers diagrams

    Anna de Mier. k-noncrossing and k-nonnesting graphs and fillings of Ferrers diagrams. Combinatorica, 27(6):699– 720, 2007

    work page 2007

  12. [12]

    Emden R. Gansner. The enumeration of plane partitions v ia the Burge correspondence. Illinois J. Math. , 25(4):533–554, 1981

    work page 1981

  13. [13]

    Emden R. Gansner. The Hillman-Grassl correspondence a nd the enumeration of reverse plane partitions. J. Combin. Theory Ser. A , 30(1):71–89, 1981

    work page 1981

  14. [14]

    Determinants, paths, a nd plane partitions

    Ira Gessel and G´ erard Viennot. Determinants, paths, a nd plane partitions. Preprint, 1989

    work page 1989

  15. [15]

    Binomial determinants , paths, and hook length formulae

    Ira Gessel and G´ erard Viennot. Binomial determinants , paths, and hook length formulae. Adv. in Math. , 58(3):300–321, 1985

    work page 1985

  16. [16]

    Generalized triangulations and diagon al-free subsets of stack polyominoes

    Jakob Jonsson. Generalized triangulations and diagon al-free subsets of stack polyominoes. J. Combin. Theory Ser. A , 112(1):117–142, 2005

    work page 2005

  17. [17]

    Plane partitions with bounded size of parts and biorthogonal polynomials

    Shuhei Kamioka. Plane partitions with bounded size of p arts and biorthogonal polynomials, 2015. https://arxiv.org/abs/1508.01674

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  18. [18]

    A triple product formula for plane part itions derived from biorthogonal polynomials

    Shuhei Kamioka. A triple product formula for plane part itions derived from biorthogonal polynomials. In 28th International Conference on Formal Power Series and Algebr aic Combinatorics (FPSAC 2016) , volume BC of Discrete Math. Theor. Comput. Sci. Proc. , pages 671–682. Assoc. Discrete Math. Theor. Comput. Sci., Nancy,

    work page 2016

  19. [19]

    Forbidden submatrices in 0-1 matrices

    Bal´ azs Keszegh and G´ abor Tardos. Forbidden submatrices in 0-1 matrices. Master’s thesis, E¨ otv¨ os Lor´ and Uni- versity, 2005

    work page 2005

  20. [20]

    Patterns in permutations and words

    Sergey Kitaev. Patterns in permutations and words . Monographs in Theoretical Computer Science. An EATCS Series. Springer, Heidelberg, 2011. With a foreword by Jeffr ey B. Remmel

    work page 2011

  21. [21]

    Advanced determinant calcu lus

    Christian Krattenthaler. Advanced determinant calcu lus. volume 42, pages Art. B42q, 67. 1999. The Andrews Festschrift (Maratea, 1998)

    work page 1999

  22. [22]

    Growth diagrams, and increa sing and decreasing chains in fillings of Ferrers shapes

    Christian Krattenthaler. Growth diagrams, and increa sing and decreasing chains in fillings of Ferrers shapes. Adv. in Appl. Math. , 37(3):404–431, 2006

    work page 2006

  23. [23]

    Lattice path enumeration

    Christian Krattenthaler. Lattice path enumeration. I n Handbook of enumerative combinatorics , Discrete Math. Appl. (Boca Raton), pages 589–678. CRC Press, Boca Raton, FL , 2015

    work page 2015

  24. [24]

    Plane partitions in the work of Richard Stanley and his school

    Christian Krattenthaler. Plane partitions in the work of Richard Stanley and his school. In The mathematical legacy of Richard P. Stanley , pages 231–261. Amer. Math. Soc., Providence, RI, 2016

    work page 2016

  25. [25]

    Germain Kreweras. Sur une classe de problemes de d´ enombrement li´ es au treillis des partitions des entiers.Cahiers du Bureau universitaire de recherche op´ erationnelle S´ erie Recherche, 6:9–107, 1965

    work page 1965

  26. [26]

    On the vector representations of ind uced matroids

    Bernt Lindstr¨ om. On the vector representations of ind uced matroids. Bull. London Math. Soc. , 5:85–90, 1973

    work page 1973

  27. [27]

    Partitions of numbers whose graphs po ssess symmetry

    Percy A MacMahon. Partitions of numbers whose graphs po ssess symmetry. Cambr. Trans. 17, 149-170 (1899)., 1899

    work page

  28. [28]

    Combinatory analysis , volume I and II

    Percy A MacMahon. Combinatory analysis , volume I and II. Cambridge University Press, 1915-1916. re preinted in one volume by Chelsea, New York, 1960

    work page 1915

  29. [29]

    Excluded permutation ma trices and the Stanley-Wilf conjecture

    Adam Marcus and G´ abor Tardos. Excluded permutation ma trices and the Stanley-Wilf conjecture. J. Combin. Theory Ser. A , 107(1):153–160, 2004

    work page 2004

  30. [30]

    Robert A. Proctor. Shifted plane partitions of trapezo idal shape. Proc. Amer. Math. Soc. , 89(3):553–559, 1983

    work page 1983

  31. [31]

    Robert A. Proctor. Bruhat lattices, plane partition ge nerating functions, and minuscule representations. European J. Combin. , 5(4):331–350, 1984

    work page 1984

  32. [32]

    David P. Robbins. The story of 1 , 2, 7, 42, 429, 7436, ⋯. Math. Intelligencer , 13(2):12–19, 1991

    work page 1991

  33. [33]

    David P. Robbins. Symmetry classes of alternating sign matrices, 2000. https://arxiv.org/abs/math/0008045

    work page internal anchor Pith review Pith/arXiv arXiv 2000

  34. [34]

    Richard P. Stanley. Theory and application of plane par titions. I, II. Studies in Appl. Math. , 50:167–188; ibid. 50 (1971), 259–279, 1971

    work page 1971

  35. [35]

    Richard P. Stanley. A baker’s dozen of conjectures conc erning plane partitions. In Combinatoire ´ enum´ erative (Montreal, Que., 1985/Quebec, Que., 1985) , volume 1234 of Lecture Notes in Math. , pages 285–293. Springer, Berlin, 1986

    work page 1985

  36. [36]

    Richard P. Stanley. Symmetries of plane partitions. J. Combin. Theory Ser. A , 43(1):103–113, 1986. 18 SEN-PENG EU AND YI-LIN LEE

    work page 1986

  37. [37]

    Two enumeration problems about the Aztec diamonds

    Bo-Yin Yang. Two enumeration problems about the Aztec diamonds . ProQuest LLC, Ann Arbor, MI, 1991. Thesis (Ph.D.)–Massachusetts Institute of Technology. Department of Mathematics, National Taiw an Normal Univers ity, Taipei, Taiw an Email address : speu@ntnu.edu.tw Department of Mathematics, National Taiw an Normal Univers ity, Taipei, Taiw an Email addr...

    work page 1991