Mixed Dimer Models for Euler and Catalan Numbers

Andrew Claussen, Nicholas Ovenhouse · 2025

Read Mixed Dimer Models for Euler and Catalan Numbers by Andrew Claussen, Nicholas Ovenhouse (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-2503-11936.txt.

Introduction

Andrew Claussen and Nicholas Ovenhouse count in 2025 mixed dimer covers on ribbon-shaped Young diagrams. The two extreme shapes, straight and zigzag, form the test cases. Cover counts for those shapes land on famous number families.

Straight shapes yield the Euler numbers, while zigzag shapes yield the Catalan numbers. Rank counts over the cover orders match the matching q-versions of both families. An order isomorphism between covers and certain permutations drives that match. The result ties tiling counts to two classic sequences at once. Permutation orders supply the bridge for the q-count match.

Catalog record

CREATORAndrew Claussen, Nicholas Ovenhouse
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE94 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-11936

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Mixed Dimer Models for Euler and Catalan Numbers Andrew Claussen, Nicholas Ovenhouse Abstract We study the enumeration of mixed dimer covers on skew Young diagrams of ribbon shape (also called border strips or snake graphs). For the two extreme cases of straight and zigzag shapes, we show that the number of mixed dimer covers are given by the Euler and Catalan numbers. We also give q q -analogs by showing that the rank generating functions of the partial orders on mixed dimer covers agree with certain q q -Euler and q q -Catalan numbers. These q q -analogs are a consequence of an isomorphism between the partial order on mixed dimer covers and the so-called middle order on certain classes of permutations. 1 Introduction and Main Results The Catalan numbers and Euler numbers are two very classical combinatorial sequences. The Catalan numbers C_{n}=\frac{1}{n+1}\binom{2n}{n} count lattice paths, trees, triangulations of polygons, and much more [ Sta15 ] . The Euler numbers E_{n} count alternating permutations, labeled trees, standard Young tableaux of certain skew shapes, and other things [ Sta10 ] . Our main results are new interpretations of the Euler and Catalan numbers as the number of mixed dimer covers of certain planar graphs. A mixed dimer cover is a generalization of a perfect matching (perfect matchings are also called dimer covers ). Given non-negative integers assigned to the vertices of a graph, a mixed dimer cover is a multiset of edges so that every vertex has the prescribed degree. If this degree is the same integer n at all vertices, then we call the configurations n -dimer covers . It is similar to the notion of \mathbf{d} -factor from [ Pro02 ] , the difference being that we have multisets of edges, allowing each edge to be taken with some multiplicity. We consider certain skew Young diagrams called border strips or ribbons . They are also frequently called snake graphs (especially in the cluster algebra literature). The weighted enumeration of perfect matchings on snake graphs is related to many interesting parts of mathematics, including cluster algebras [ Pro20 ] [ MS09 ] [ MSW13 ] , continued fractions [ ÇS18 ] , Jones polynomials [ LS19 ] , Teichmüller theory [ MW13 ] , and q -deformed rational numbers [ MGO20 ] . There has recently been some interest in studying higher dimer covers on snake graphs. In [ MOZ22 ] it was shown that the coordinates on the higher Teichmüller space for the orthosymplectic supergroup \mathrm{OSp}(2|1) can be expressed as weighted sums of double dimer covers on snake graphs. Then [ MOSZ23 ] found enumerative formulas for n -dimer covers on snake graphs for any n\geq 1 . Also in [ WM20 ] , type D cluster variables were expressed in terms of mixed dimer covers on graphs which are similar to snake graphs. In some sense, this paper is a continuation and generalization of [ MOSZ23 ] and [ BOSZ24 ] to the case of mixed dimer covers. In the early sections of this paper, we will focus on the two simplest families of snake graphs. The first family we consider are the straight snake graphs \mathcal{G}_{n}^{s} (see Figure 1 (left)), which are 2\times(n+1) grid graphs, formed by n squares attached horizontally in a row. The second family are the zig-zag snake graphs \mathcal{G}_{n}^{z} , whose squares are attached in a sequence going up, right, up, right, etc (see Figure 1 (right)). 1 2 3 4 5 1 2 3 4 5 1 1 2 2 3 3 4 4 5 5 6 6 Figure 1: Examples of graphs \mathcal{G}_{4}^{s} (left) and \mathcal{G}_{5}^{z} (right), with their standard vertex labelings. These graphs have very simple and well-known formulas for their number of perfect matchings. The number of matchings of \mathcal{G}_{n}^{s} are the Fibonacci numbers, and the number of matchings of the zig-zag \mathcal{G}_{n}^{z} is n+1 . Our main results are that with their standard labelings (the vertex labels in Figure 1 ), the number of mixed dimer covers on these graphs are precisely the Euler and Catalan numbers. Theorem A . Let \mathcal{G}_{n}^{s} and \mathcal{G}_{n}^{z} have the vertex labelings as depicted in Figure 1 . Then (a) The number of mixed dimer covers of \mathcal{G}_{n}^{s} is equal to the Euler number E_{n+2} . (b) The number of mixed dimer covers of \mathcal{G}_{n}^{z} is equal to the Catalan number C_{n+1} . Not only do we have these counting formulas, but we give explicit bijections between mixed dimer covers and certain families of permutations counted by the Euler and Catalan numbers (namely alternating and 132-avoiding permutations). These bijections actually restrict to certain refinements of the Euler and Catalan numbers. The Entringer numbers E_{n,k} count alternating permutations \sigma\in S_{n} with \sigma(1)=k . One of the many things counted by the Catalan numbers are 132 -avoiding permutations. The generalized Catalan numbers (also called ballot numbers ) C_{n,k} count the 132 -avoiding permutations \sigma\in S_{n} with \sigma(1)=k . We then have the following more refined version of Theorem A: Theorem B . Let \mathcal{G}_{n}^{s} and \mathcal{G}_{n}^{z} have the vertex labelings as depicted in Figure 1 . Then (a) The number of mixed dimer covers of \mathcal{G}_{n}^{s} with k dimers on the right-most vertical edge is equal to the Entringer number E_{n+2,k+1} . (b) The number of mixed dimer covers of \mathcal{G}_{n}^{z} with k dimers on the final edge 1 1 1 See section 3 for the definition of final edge . is equal to the ballot number C_{n+1,k+1} . The strategy of the proofs of Theorem A and Theorem B are to encode certain recurrences for the Euler/Entringer and and Catalan/ballot numbers using matrix multiplication, and then to show that the corresponding subsets of mixed dimer covers satisfy the same recurrences. We then use the recurrences to give explicit bijections. Under these bijections, one can read off the inversions of the associated permutation from certain edge multiplicities in the mixed dimer covers. We then consider a natural partial order on mixed dimer covers, and the associated rank generating functions, to obtain q -analogs of the above results. In [ Pro02 ] , Propp gave a partial order on the set of perfect matchings (more generally \mathbf{d} -factors) of a planar graph. It is easy to see that this partial order also makes sense for mixed dimer covers. We show that the rank generating functions agree with well-known q -analogs of the Euler and Catalan numbers. Said in another way, the bijections from Theorem A and Theorem B are order-preserving with respect to certain partial orders on the permutations counted by Euler and Catalan numbers. Theorem C . Let \mathcal{G}_{n}^{s} and \mathcal{G}_{n}^{z} be as before. (a) The bijection from mixed dimer covers of \mathcal{G}_{n}^{s} to alternating permutations in S_{n+2} is order-preserving with respect to the Bruhat order. (b) The bijection from mixed dimer covers of \mathcal{G}_{n}^{z} to 132 -avoiding permutations is order-preserving with respect to the Bruhat order. More specifically, the bijections in Theorem C are poset isomorphims, with respect to the middle order on permutations [ BFT25 ] , which is a coarsening of the Bruhat order. In the later sections of the paper, we discuss more general graphs (of which the straight and

Read the complete text