Alternative Approaches for Counting Weakly Increasing Matrices
Leo Yicheng Yang · 2025
Read Alternative Approaches for Counting Weakly Increasing Matrices by Leo Yicheng Yang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-15779.txt.
Introduction
Leo Yicheng Yang presents two new ways to count grids of numbers that never decrease along rows and columns. The grids have two rows, with entries chosen from one up to a set limit. Counting such grids exactly is a classic problem in combinatorics, the study of counting patterns.
The first method matches each grid with a chemical pattern: the bond layouts of certain ring-shaped molecules built from hexagons. The second method turns the count into a count of pairs of stair-like paths that never cross. Each match lets known results from one field solve the other. Yang's paper shows how problems that look unrelated can share the same hidden structure.
Catalog record
| CREATOR | Leo Yicheng Yang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 31 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-15779
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Alternative Approaches for Counting Weakly Increasing Matrices Leo Yicheng Yang Abstract . This paper presents two alternative approaches for counting the number of two-row weakly increasing matrices, which are 2 × n 2\times n matrices whose entries are integers from 1 1 to k k and are weakly increasing along all rows and columns, for any positive integers n n and k k . The first approach establishes a bijection between the set of such matrices and the set of Kekulé structures for certain hexagonal benzenoids. The second approach reduces the problem to counting the number of pairs of non-intersecting lattice paths. These approaches reveal interesting connections between combinatorial problems that arise in different domains. 1. Problem Introduction An m\times n matrix A=\{a_{i,j}\} is weakly increasing if its entries increase weakly along each row and down each column, i.e., a_{i,j}\leq a_{i^{\prime},j^{\prime}} for any 1\leq i\leq i^{\prime}\leq m and 1\leq j\leq j^{\prime}\leq n . Given natural numbers n and k , let \mathfrak{M}_{n,k} denote the set of 2\times n weakly increasing matrices with entries in \{1,\ldots,k\} . We are interested in |\mathfrak{M}_{n,k}| as a function of n and k , which was posed as Problem #12497 in the American Mathematical Monthly . For example, there are six matrices in \mathfrak{M}_{2,2} : \left[\begin{array}[]{cc}1&1\\ 1&1\end{array}\right]\quad\left[\begin{array}[]{cc}1&1\\ 1&2\end{array}\right]\quad\left[\begin{array}[]{cc}1&1\\ 2&2\end{array}\right]\quad\left[\begin{array}[]{cc}1&2\\ 1&2\end{array}\right]\quad\left[\begin{array}[]{cc}1&2\\ 2&2\end{array}\right]\quad\left[\begin{array}[]{cc}2&2\\ 2&2\end{array}\right] As another example, here is a matrix in \mathfrak{M}_{6,7} : (1.1) \displaystyle W=\begin{bmatrix}1&1&2&3&6&6\\ 1&1&2&4&6&7\end{bmatrix} From Chen et al. [ 1 ] , the formula for |\mathfrak{M}_{n,k}| is: (1.2) \displaystyle|\mathfrak{M}_{n,k}|=\frac{{n+k-1\choose k-1}{n+k\choose k-1}}{k} The authors derived this formula from Macmahon’s formula for counting the number of plane partitions [ 4 ] within a 2\times n\times k grid, by establishing a bijection between \mathfrak{M}_{n,k} and the set of plane partitions. This paper presents two alternative approaches for deriving |\mathfrak{M}_{n,k}| . To the best of our knowledge, these approaches are novel. We believe that they reveal interesting connections between combinatorial problems that arise in different domains. The first approach ( Section 2 ) draws a bijection between \mathfrak{M}_{n,k} and the set of Kekulé structures of hexagonal benzenoids, whose count has been established by Cyvin in 1986 [ 2 ] (see also [ 3 ] ). A hexagonal benzenoid is made up of regular hexagonal benzene rings arranged in a hexagonal structure, and a Kekulé structure is a selection of edges in this structure such that every vertex is paired with exactly one other vertex. We observe that the positions of vertically oriented edges among the selected edges follow certain patterns and uniquely identify each Kekulé structure. Furthermore, there is a bijection between these sets of positions and \mathfrak{M}_{n,k} . The second approach ( Section 3 ) draws a bijection between \mathfrak{M}_{n,k} and the set of pairs of non-intersecting paths in a two-dimensional rectangular lattice, where edges only point upward and rightward. The locations of upward edges in each path determine which entries in a row see strict increases and by how much. The Lindström-Gessel-Viennot Lemma, which counts the number of non-intersecting paths in a directed graph, can be applied to produce the formula in Equation 1.2 . Finally, in Section 4 , we comment on how these approaches can be naturally extended to solve the more general problem of counting the number of weakly increasing matrices of dimension m\times n . 2. Connection to Kekulé Structures for Hexagonal Benzenoids A hexagonal benzenoid O\{p,q,r\} consists of (p+1)(q+r-1)-2 regular hexagonal benzene rings (units) arranged in a hexagonal structure, as illustrated in Figure 1 . A Kekulé structure is a perfect matching of O , i.e., a subset of edges such that every vertex is paired with exactly one other vertex. We will refer to edges in this subset as selected edges. Figure 1 . Hexagonal benzenoid O\{p,q,r\} with dimensions p=6 , q=2 , and r=6 , with a particular Kekulé structure whose selected edges are shown as triple lines. The v-bars (selected edges that are vertical) in the Kekulé structure are further marked with their positions. Each selected edge in the Kekulé structure represents a double bond between two carbon atoms in a benzene ring (C6H6). Let \mathfrak{K}_{p,q,r} denote the set of Kekulé structures for a hexagonal benzenoid with dimensions (p,q,r) . An explicit combinatorial formula for |\mathfrak{K}_{p,q,r}| already exists, having been derived by Cyvin in 1986 [ 2 ] (see also [ 3 ] ): (2.1) \displaystyle|\mathfrak{K}_{p,q,r}|=\prod_{i=0}^{q-1}\frac{{p+r+i\choose r}}{{r+i\choose r}} Notice that plugging in q=2 yields: \displaystyle|\mathfrak{K}_{p,2,r}|=\frac{{p+r\choose r}{p+r+1\choose r}}{{r\choose r}{r+1\choose r}}=\frac{{p+r\choose r}{p+r+1\choose r}}{r+1} which is precisely the formula for |\mathfrak{M}_{n,k}| in Equation 1.2 after substituting r+1 for k and p for n . Hence, to show Equation 1.2 , it suffices to establish the following: Theorem 2.1 . There exists a bijection between \mathfrak{M}_{n,k} and \mathfrak{K}_{n,2,k-1} . We outline the proof in the remainder of this section. For detailed proofs of all theorems and lemmas, see Appendix A . 2.1. Analysis of Kekulé Structures Unless otherwise noted, K in this subsection refers to any Kekulé structure in \mathfrak{K}_{n,2,k-1} . Define a v-bar as a selected vertical edge in K . To denote the location of a vertical edge (and potential v-bar) in K , we use (i,j) , where i\in[0,r] identifies the row containing the vertical edge (beginning with 0 for the top row of units), and j\in[0,n+1] is the number of vertical edges in the same row strictly to its left. Note that for i=0 and i=r (top and bottom rows), j\leq n , because these two rows contain n units each instead of n+1 units. A key insight is that the set of v-bars uniquely identifies a Kekulé structure, and must follow certain constraints. To aid in our analysis, we define several useful substructures of K . Figure 2 . Substructures of K , willows and caterpillars, highlighted in gray. “Leftover” edges outlined in Lemma 2.7 are not colored. A willow , anchored by v-bar (i,j) and spanning [j_{1},j_{2}] (where j\in[j_{1},j_{2}] ), is an assignment of an edge subset to either “selected” or “unselected” defined as follows, illustrated in Figure 2 : • It contains all vertical edges in row i from (i,j_{1}) to (i,j_{2}) , inclusive; all are unselected except the anchor (i,j) , which is selected. • It contains the shortest path from the top of (i,j) to the top of (i,j_{1}) , and the shortest path from the top of (i,j) to the top of (i,j_{2}) ; the edges of each path alternate between unselected and selected, starting from the edges incident to (i,j) , which are unselected. • It contains the two edges incident to the bottom of (i,j) ; both are unselected. A caterpillar , anchored by v-bar (i-1,j) where i\in[1,r] , is defined as follows, illustrated in Figure 2 : • It is anchored by a v-bar at (i-1,j) . • It contains all vertical edges in row i from (i,0) to (i,j-1) , inclusive; all are unselected. • It contains the shortest path from the bottom of (i-1,0) to the top of (i,j-1) ; edges in each path start as selected and alternate between unselected and selected. We say that K contains a willow or caterpillar if K agrees with the substructure in the selection of edges. Starting from the top, we show that K must contain exactly one v-bar