Mirror Variations of Catalan Multijections
Muhammad Adam Dombrowski · 2026
Read Mirror Variations of Catalan Multijections by Muhammad Adam Dombrowski (2026) 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-2608-00431.txt.
Introduction
Dombrowski proposes new Catalan multijections that yield different partitions. A Catalan multijection splits a set of objects into classes of size n plus one. Each class holds exactly one distinct Catalan object. Isaak and Langley had studied when two multijections give the same partitions, in work not yet published. His new constructions part from the ones found before. Readers get fresh cases for comparing multijection partitions.
Catalog record
| CREATOR | Muhammad Adam Dombrowski |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 38 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2608.00431
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Mirror Variations of Catalan Multijections Muhammad Adam Dombrowski Abstract A Catalan multijection is a way to partition a set of ( 2 n n ) \binom{2n}{n} objects into equivalence classes of size n + 1 n+1 , where each equivalence class has exactly one distinct Catalan object. Isaak and Langley investigated when two multijections produced the same partitions in an unpublished manuscript. We propose some new multijections for which we get different partitions from previously discovered multijections. 1 Introduction The Catalan numbers, \{1,1,2,5,14,42...\} , are an integer sequence ( A000108 ) that appears in many places: triangulations of n -gons, binary strings, and lattice paths that stay below the diagonal. We denote the n -th Catalan number by C_{n} . There are multiple formulas for this integer sequence, including recurrence relations, but the most relevant for us will be the following formula given by the Chung-Feller Theorem. C_{n}=\frac{1}{n+1}\binom{2n}{n} Before stating the theorem, we would like to define what we mean by lattice paths. The following rigorous definition comes from Stanley [ 7 ] . Defintion 1.1 (Lattice Paths in \mathbb{Z}^{d} ) . Let S be a subset of \mathbb{Z}^{d} . A lattice path in \mathbb{Z}^{d} of length k with steps in S is a sequence v_{0},v_{1},\dots,v_{k}\in\mathbb{Z}^{d} such that each consecutive difference v_{i}-v_{i-1} lies in S . For the purposes of this paper, we only need to consider lattice paths in \mathbb{Z}^{2} , as well as the consecutive difference v_{i}-v_{i-1} being either (1,0) or (0,1) . Additionally, we will consider lattice paths of the previous form that run from (0,0) to (n,n) . We will adopt the following narrower definition for lattice paths in the context of this paper. Defintion 1.2 . Let n\in\mathbb{N} . A lattice path in \mathbb{Z}^{2} of length 2n is a sequence p_{1}p_{2}\dots p_{n} , where each p_{i}\in\{(1,0),(0,1)\} , or in this specific case, denoted R for right-step (1,0) and U for up-step (0,1) . In general, we call p_{i} the steps of a lattice path. Remark . Let p,q be steps in a lattice paths. Then p and q are equivalent, denoted by p\cong q , if they both correspond to the same type of step; if p,q are both up-steps then p\cong q , and if p is an up-step and q is a down-step, then p\ncong q . There are two common ways to visualize these lattice paths. The first is as we have stated, a lattice path consists of steps (1,0) and (0,1) from the origin to (n,n) . However, we only acknowledge and will make use of an alternative definition which considers steps of (1,1) or (1,-1) , creating a path from (0,0) to (n,0) . The former will be referred as a lattice path in staircase notation and the latter as a lattice path in mountain notation . Remark . A lattice path in staircase notation will be a sequence p_{1}p_{2}\dots p_{n} from (0,0) to (n,n) where each p_{i} is either (1,0) , denoted as a right-step r , or (0,1) , denoted as an up-step u . A lattice path in mountain notation will be a sequence p_{1}p_{2}\dots p_{n} from (0,0) to (n,0) where each p_{i} is either (1,1) , denoted as an up-step u or (1,-1) , denoted as a down-step d . We also define an equivalence of lattice paths. Defintion 1.3 . Let P,Q be lattice paths. Then P and Q are equivalent, denoted by P\cong Q , if P and Q are the same length, say n , and p_{i}\cong q_{i} for i=1,\dots,n . The number of lattice paths from (0,0) to (n,n) is not counted by the Catalan numbers. However, if we impose a certain condition on these lattice paths however, then we get something that is counted by C_{n} . Defintion 1.4 . Let P be a lattice path in staircase notation. Then, P is a Dyck path if it stays below the diagonal y=x . If a lattice path is in mountain notation, then a Dyck path will be a lattice path which does not go below the x -axis. This follows a bit less intuitively from the given definition in staircase notation, but the reason for this note is to align our setup with a certain proof which defined the Dyck path with respect to this parameter. The reader can see that this labeling of “above” the x -axis, “below” the diagonal, and its corresponding labeling of the diagonal is arbitrary; the important part is consistently choosing this labeling in order to properly define Dyck paths in context. Figure 1.1 : Staircase notation (left) and mountain notation (right). Notice how the lattice path drawn in Figure 1.1 does not cross the diagonal. The lattice path drawn in Figure 1.2 is not an example of a Dyck path. Figure 1.2 : This lattice path is not a Dyck path. Now, we are ready to give the Chung-Feller Theorem. Originally proved by Chung and Feller in a slightly different form in [ 3 ] , the following statement is still equivalent. Theorem 1.5 (Chung-Feller Theorem) . The number of lattice paths consisting of n up-steps and n right-steps which stay below the diagonal, or Dyck paths with n up-steps and n right-steps is \frac{1}{n+1}\binom{2n}{n} . There are many proofs of the Chung-Feller Theorem, ranging from analytic to combinatorial. The \frac{1}{n+1} in the theorem suggests that one way to prove this is to show that a larger set of objects of size \binom{2n}{n} can be divided into subsets of n+1 subsets of equal size, with each subset containing a Catalan object. For example, in the case of general lattice paths from (0,0) to (n,n) , there are 2n total steps, and all that is requires is to choose where the n right-steps will go. Then, by the Chung-Feller Theorem, then n+1 divides our total number of lattice paths to give us the total number of Dyck paths. Another perspective of this mapping is that we can divide into subsets of size n+1 , but have one Dyck path per subset. For now, we can loosely call these subsets “Catalan partitions”. While this labeling may sound novel, plenty of combinatorial Chung-Feller proofs induce this partitioning. Finally, we can start to ask when two of these kind of proofs are equivalent. 2 Defining Multijections Isaak and Langley provided a framework that characterizes this approach with the following two definitions. The following two defintions are attributed to Isaak from [ 5 ] . Defintion 2.1 (Multijection) . Assume that A and \mathcal{A} are finite sets. We will say that a map \alpha from A to \mathcal{A} is a t -uniform multijection if the preimages \alpha^{-1}(a) for a\in\mathcal{A} all have size t . For a given function, the relation xRy if f(x)=f(y) is trivially an equivalence relation so the preimages partition the domain A . Then, since all have the same size, t . we get |\mathcal{A}|=\frac{1}{t}|A| for a t -uniform multijection. One can see the resemblance of a combinatorial Chung-Feller proof under this broader notion of a multijection. From here on, we will use the term “multijection” when describing other combinatorial Chung-Feller proofs. Within the context of lattice paths, we can imagine that A is our set