<figure><img src="image_1.png" /></figure>

HAL
open science

# Generating series and matrix models for meandric systems with one shallow side

Motohisa Fukuda, Ion Nechita

► To cite this version:

Motohisa Fukuda, Ion Nechita. Generating series and matrix models for meandric systems with one shallow side. Annales de l'Institut Henri Poincaré (D) Combinatorics, Physics and their Interactions, 2024, 11 (2), pp.299-330. 10.4171/aihpd/183 . hal-04610415

HAL Id: hal-04610415

https://hal.science/hal-04610415

Submitted on 13 Jun 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_1.png" /></figure>

HAL
open science

# Generating series and matrix models for meandric systems with one shallow side

Motohisa Fukuda, Ion Nechita

► To cite this version:

Motohisa Fukuda, Ion Nechita. Generating series and matrix models for meandric systems with one shallow side. Annales de l'Institut Henri Poincaré (D) Combinatorics, Physics and their Interactions, 2024, 11 (2), pp.299-330. 10.4171/aihpd/183 . hal-04610415

HAL Id: hal-04610415

https://hal.science/hal-04610415v1

Submitted on 13 Jun 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Generating series and matrix models for meandric systems with one shallow side

Motohisa Fukuda and Ion Nechita

**Abstract.** In this article, we investigate meandric systems having one shallow side: the arch configuration on that side has depth at most two. This class of meandric systems was introduced and extensively examined by I. P. Goulden, A. Nica, and D. Puder [Int. Math. Res. Not. IMRN 2020 (2020), 983–1034]. Shallow arch configurations are in bijection with the set of interval partitions. We study meandric systems by using moment-cumulant transforms for non-crossing and interval partitions, corresponding to the notions of free and Boolean independence, respectively, in non-commutative probability. We obtain formulas for the generating series of different classes of meandric systems with one shallow side by explicitly enumerating the simpler, irreducible objects. In addition, we propose random matrix models for the corresponding meandric polynomials, which can be described in the language of quantum information theory, in particular that of quantum channels.

## 1. Introduction

Meanders are fundamental combinatorial objects of great complexity, defined by a simple non-crossing closed curve intersecting a reference line at $2n$ points. Their enumeration (as a function of $n$) is an important open problem in combinatorics [1]. There is a large theoretical body of work dealing with the combinatorics of meanders; see [9, 16].

Mathematically, meandric systems are generalizations of meanders consisting of two *arch configurations*, one on top and the other on the bottom of the reference line. An arch configuration corresponds precisely to a non-crossing pairing of the coordinate set $\{1, 2, \dots, 2n\}$. It is this connection to the theory of non-crossing partitions that had been put forward by A. Nica in [19], starting the study of meandric systems with the help of tools from free probability theory [18, 24]. This line of work has been pursued further, with new results about semi-meanders [21], meandric systems with large number of loops [12], and random meandric systems [10].

*Mathematics Subject Classification 2020:* 05A15 (primary); 46L54, 81P45, 94A40 (secondary).

**Keywords:** meander, meandric system, free probability, random matrices, non-commutative probability, free cumulant.
# Generating series and matrix models for meandric systems with one shallow side

Motohisa Fukuda and Ion Nechita

**Abstract.** In this article, we investigate meandric systems having one shallow side: the arch configuration on that side has depth at most two. This class of meandric systems was introduced and extensively examined by I. P. Goulden, A. Nica, and D. Puder [Int. Math. Res. Not. IMRN 2020 (2020), 983–1034]. Shallow arch configurations are in bijection with the set of interval partitions. We study meandric systems by using moment-cumulant transforms for non-crossing and interval partitions, corresponding to the notions of free and Boolean independence, respectively, in non-commutative probability. We obtain formulas for the generating series of different classes of meandric systems with one shallow side by explicitly enumerating the simpler, irreducible objects. In addition, we propose random matrix models for the corresponding meandric polynomials, which can be described in the language of quantum information theory, in particular that of quantum channels.

## 1. Introduction

Meanders are fundamental combinatorial objects of great complexity, defined by a simple non-crossing closed curve intersecting a reference line at $2n$ points. Their enumeration (as a function of $n$) is an important open problem in combinatorics [1]. There is a large theoretical body of work dealing with the combinatorics of meanders; see [9, 16].

Mathematically, meandric systems are generalizations of meanders consisting of two *arch configurations*, one on top and the other on the bottom of the reference line. An arch configuration corresponds precisely to a non-crossing pairing of the coordinate set $\{1, 2, \dots, 2n\}$. It is this connection to the theory of non-crossing partitions that had been put forward by A. Nica in [19], starting the study of meandric systems with the help of tools from free probability theory [18, 24]. This line of work has been pursued further, with new results about semi-meanders [21], meandric systems with large number of loops [12], and random meandric systems [10].

*Mathematics Subject Classification 2020:* 05A15 (primary); 46L54, 81P45, 94A40 (secondary).

**Keywords:** meander, meandric system, free probability, random matrices, non-commutative probability, free cumulant.
An important result was obtained by I. P. Goulden, A. Nica, and D. Puder in [14], where a particular subclass of meandric systems was described combinatorially: the authors studied meandric systems where the arch configurations on top of the reference line correspond to interval partitions; the authors named such meandric systems *shallow top meanders*. Due to the simpler combinatorial structure of the top arch configurations, shallow top meanders are tractable enough to provide interesting lower bounds on the total number of meanders.

Our work drew most of its inspiration from [14] but tackles the enumeration of special classes of meandric systems in a systematic way, employing tools from non-commutative probability theory. Our main insight is to reduce the enumeration of meandric systems to that of a simpler class of objects, sometimes called “irreducible” (see [4] for the general flavor in combinatorics). If the initial class of meandric systems corresponds to the *moments* of some non-commutative distribution, the simpler meandric systems correspond to its *cumulants*. The type of cumulants involved depends on the structure of the initial meandric systems: general non-crossing partitions yield free cumulants, while interval partitions Boolean cumulants. Once the probabilistic machinery is applied, we can then directly enumerate the simpler combinatorial objects and in theory the initial, allowing us to treat several situations in a unified manner. We discuss the case of shallow top meanders in Theorem 5.1, the case of thin meanders in Theorem 4.1, and the case of shallow top semi-meandric systems in Theorem 6.1.

Historically, meandric systems were also studied using methods from random matrix theory. P. Di Francesco and his collaborators developed several such models in [8,9]. Later, an intriguing connection to the theory of quantum information theory was put forward in [13]. We provide at the end of this paper several new matrix models for the various classes of meandric systems we consider, which also fall in the field of quantum information. Indeed, we show that the meandric polynomial is equal to the asymptotic moments of the output state of a tensor product of completely positive maps, acting on the maximally entangled state. The choice of completely positive maps depends on the type of partitions on the bottom side one considers: random Gaussian channels for general non-crossing partitions and a depolarizing channel for interval partitions. These models (presented in Theorems 7.3, 7.6, and 7.7) are conceptually simpler than the past ones and allow us to treat the different subsets of meanders in a unified manner.

Our paper is organized as follows. Section 2 contains the main definitions and tools from the combinatorial theory of permutations and meanders. In Section 3, we recall the basic tools from Boolean and free probability theory used in this work. The following three sections contain the main body of the paper, dealing with three different classes of meandric systems: thin (both shallow top and shallow bottom) meandric systems in Section 4, shallow top meandric systems in Section 5, and shallow-top
An important result was obtained by I. P. Goulden, A. Nica, and D. Puder in [14], where a particular subclass of meandric systems was described combinatorially: the authors studied meandric systems where the arch configurations on top of the reference line correspond to interval partitions; the authors named such meandric systems *shallow top meanders*. Due to the simpler combinatorial structure of the top arch configurations, shallow top meanders are tractable enough to provide interesting lower bounds on the total number of meanders.

Our work drew most of its inspiration from [14] but tackles the enumeration of special classes of meandric systems in a systematic way, employing tools from non-commutative probability theory. Our main insight is to reduce the enumeration of meandric systems to that of a simpler class of objects, sometimes called “irreducible” (see [4] for the general flavor in combinatorics). If the initial class of meandric systems corresponds to the *moments* of some non-commutative distribution, the simpler meandric systems correspond to its *cumulants*. The type of cumulants involved depends on the structure of the initial meandric systems: general non-crossing partitions yield free cumulants, while interval partitions Boolean cumulants. Once the probabilistic machinery is applied, we can then directly enumerate the simpler combinatorial objects and in theory the initial, allowing us to treat several situations in a unified manner. We discuss the case of shallow top meanders in Theorem 5.1, the case of thin meanders in Theorem 4.1, and the case of shallow top semi-meandric systems in Theorem 6.1.

Historically, meandric systems were also studied using methods from random matrix theory. P. Di Francesco and his collaborators developed several such models in [8,9]. Later, an intriguing connection to the theory of quantum information theory was put forward in [13]. We provide at the end of this paper several new matrix models for the various classes of meandric systems we consider, which also fall in the field of quantum information. Indeed, we show that the meandric polynomial is equal to the asymptotic moments of the output state of a tensor product of completely positive maps, acting on the maximally entangled state. The choice of completely positive maps depends on the type of partitions on the bottom side one considers: random Gaussian channels for general non-crossing partitions and a depolarizing channel for interval partitions. These models (presented in Theorems 7.3, 7.6, and 7.7) are conceptually simpler than the past ones and allow us to treat the different subsets of meanders in a unified manner.

Our paper is organized as follows. Section 2 contains the main definitions and tools from the combinatorial theory of permutations and meanders. In Section 3, we recall the basic tools from Boolean and free probability theory used in this work. The following three sections contain the main body of the paper, dealing with three different classes of meandric systems: thin (both shallow top and shallow bottom) meandric systems in Section 4, shallow top meandric systems in Section 5, and shallow-top
semi-meanders in Section 6. Finally, random matrix models are discussed in Section 7.

## 2. Combinatorial aspects of meandric systems

### 2.1. Basics of non-crossing partitions and permutations

This section contains the necessary definitions and properties of the combinatorial objects meandric systems are built on, which are mainly non-crossing and interval partitions. We refer the reader to [5] or [20] for more details.

We denote by $S_n$ the group of permutations of $n$ symbols. For a permutation $\alpha \in S_n$, we denote by $\|\alpha\|$ its length: $\|\alpha\|$ is the minimal number $m$ of transpositions $\tau_1, \dots, \tau_m$ which multiply to $\alpha$:

$$ \|\alpha\| := \min\{m \ge 0 : \exists \tau_1, \dots, \tau_m \in S_n \text{ transpositions s.t. } \alpha = \tau_1 \cdots \tau_m\}. $$

The length $\|\cdot\|$ endows the symmetric group $S_n$ with a metric structure, by defining

$$ d(\alpha, \beta) = \|\alpha^{-1}\beta\|. $$

The following relation between the number of cycles $\#(\alpha)$ of a permutation and its length is crucial to us:

$$ \|\alpha\| + \#(\alpha) = n. $$

Both statistics $\#(\cdot)$ and $\|\cdot\|$ are constant on conjugation classes; hence, the following relations hold:

$$ \|\alpha\| = \|\alpha^{-1}\| \quad \text{and} \quad \|\alpha\beta\| = \|\beta\alpha\|. $$

Let us now introduce the different classes of partitions which will be of interest to us. A partition $B_1 \sqcup B_2 \sqcup \dots \sqcup B_m = \{1, 2, \dots, n\} =: [n]$ is called *non-crossing* if its blocks $B_k$ do not cross: there do not exist distinct blocks $B_i, B_j$ and $a, b \in B_i$ and $c, d \in B_j$ such that $a < c < b < d$. The partition $\{1, 4, 5\} \sqcup \{2, 3\}$ of [5] is non-crossing; see Figure 1. The partition $\{1, 3\} \sqcup \{2, 4, 5\}$ on the other hand is crossing; see Figure 2. The set of non-crossing partitions of $[n]$ is denoted by $\text{NC}(n)$ or $\text{NC}(1, 2, \dots, n)$, if we want to emphasize the underlying set. The subset of non-crossing partitions consisting of *pairings* (i.e., all the blocks have size two) is denoted by $\text{NC}_2(n)$; in this case, $n$ must obviously be even. Finally, the subset of *interval* partitions, denoted by $\text{Int}(n)$, consists of (non-crossing) partitions having blocks made of consecutive integers. We have

$$ |\text{NC}(n)| = |\text{NC}_2(2n)| = \text{Cat}_n = \frac{1}{n+1} \binom{2n}{n} \quad \text{and} \quad |\text{Int}(n)| = 2^{n-1}. $$
semi-meanders in Section 6. Finally, random matrix models are discussed in Section 7.

## 2. Combinatorial aspects of meandric systems

### 2.1. Basics of non-crossing partitions and permutations

This section contains the necessary definitions and properties of the combinatorial objects meandric systems are built on, which are mainly non-crossing and interval partitions. We refer the reader to [5] or [20] for more details.

We denote by $S_n$ the group of permutations of $n$ symbols. For a permutation $\alpha \in S_n$, we denote by $\|\alpha\|$ its length: $\|\alpha\|$ is the minimal number $m$ of transpositions $\tau_1, \dots, \tau_m$ which multiply to $\alpha$:

$$ \|\alpha\| := \min\{m \ge 0 : \exists \tau_1, \dots, \tau_m \in S_n \text{ transpositions s.t. } \alpha = \tau_1 \cdots \tau_m\}. $$

The length $\|\cdot\|$ endows the symmetric group $S_n$ with a metric structure, by defining

$$ d(\alpha, \beta) = \|\alpha^{-1}\beta\|. $$

The following relation between the number of cycles $\#(\alpha)$ of a permutation and its length is crucial to us:

$$ \|\alpha\| + \#(\alpha) = n. $$

Both statistics $\#(\cdot)$ and $\|\cdot\|$ are constant on conjugation classes; hence, the following relations hold:

$$ \|\alpha\| = \|\alpha^{-1}\| \quad \text{and} \quad \|\alpha\beta\| = \|\beta\alpha\|. $$

Let us now introduce the different classes of partitions which will be of interest to us. A partition $B_1 \sqcup B_2 \sqcup \dots \sqcup B_m = \{1, 2, \dots, n\} =: [n]$ is called *non-crossing* if its blocks $B_k$ do not cross: there do not exist distinct blocks $B_i, B_j$ and $a, b \in B_i$ and $c, d \in B_j$ such that $a < c < b < d$. The partition $\{1, 4, 5\} \sqcup \{2, 3\}$ of [5] is non-crossing; see Figure 1. The partition $\{1, 3\} \sqcup \{2, 4, 5\}$ on the other hand is crossing; see Figure 2. The set of non-crossing partitions of $[n]$ is denoted by $\text{NC}(n)$ or $\text{NC}(1, 2, \dots, n)$, if we want to emphasize the underlying set. The subset of non-crossing partitions consisting of *pairings* (i.e., all the blocks have size two) is denoted by $\text{NC}_2(n)$; in this case, $n$ must obviously be even. Finally, the subset of *interval* partitions, denoted by $\text{Int}(n)$, consists of (non-crossing) partitions having blocks made of consecutive integers. We have

$$ |\text{NC}(n)| = |\text{NC}_2(2n)| = \text{Cat}_n = \frac{1}{n+1} \binom{2n}{n} \quad \text{and} \quad |\text{Int}(n)| = 2^{n-1}. $$
<figure><img src="image_3.png" /><figcaption>**Figure 1.** A non-crossing partition.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>**Figure 2.** A crossing partition.</figcaption></figure>

In many cases, it is important to identify non-crossing partitions with a class of permutations, called geodesic permutations. This correspondence, initially observed in [5] (see also [20, Lecture 23]), is key in many areas and used extensively in random matrix theory for example. The bijection is defined as follows: one associates to each block of a non-crossing partition a cycle in a permutation where the elements are ordered increasingly. For example, the non-crossing partition from Figure 1 is identified to the permutation $(1, 4, 5)(2, 3) \in S_5$. Note that the cycles of the permutation are precisely the blocks of the non-crossing partition, with the choice of (cyclically) ordering the elements increasingly.

Importantly, it was shown by Biane [5] that geodesic permutations are characterized using the metric induced by the length function on the symmetric group: $\alpha \in S_n$ is a geodesic permutation if and only if it saturates the triangle inequality

$$ \|\alpha\| + \|\alpha^{-1}\gamma\| = \|\gamma\| = n-1, $$

where $\gamma = (1, 2, \dots, n)$ is the full-cycle permutation. Note that in this case $\alpha$ lies on a geodesic between the identity permutation $id = (1)(2)\cdots(n)$ and $\gamma = (1, 2, \dots, n)$.

In this paper, we will identify geodesic permutations $\alpha \in S_n$ with the corresponding non-crossing partition $\alpha \in \text{NC}(n)$. With this identification, the identity permutation $id$ corresponds to the singleton partition $0_n$, and the full cycle permutation $\gamma$ corresponds to the single-block partition $1_n$. Apart from these two special (extremal) objects, we will use the same notation for geodesic permutations and non-crossing partitions, usually Greek letters $\alpha, \beta, \sigma$, etc.

The set $\text{NC}(n)$ is endowed with a partial order called reversed refinement: $\alpha \le \beta$ if every block of $\alpha$ is contained in a block of $\beta$. Note that this order relation is not total: for example, the partitions $\{1\} \sqcup \{2, 3\}$ and $\{2\} \sqcup \{1, 3\}$ are not comparable. This partial order can be nicely characterized in terms of the associated geodesic
<figure><img src="image_3.png" /><figcaption>**Figure 1.** A non-crossing partition.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>**Figure 2.** A crossing partition.</figcaption></figure>

In many cases, it is important to identify non-crossing partitions with a class of permutations, called geodesic permutations. This correspondence, initially observed in [5] (see also [20, Lecture 23]), is key in many areas and used extensively in random matrix theory for example. The bijection is defined as follows: one associates to each block of a non-crossing partition a cycle in a permutation where the elements are ordered increasingly. For example, the non-crossing partition from Figure 1 is identified to the permutation $(1, 4, 5)(2, 3) \in S_5$. Note that the cycles of the permutation are precisely the blocks of the non-crossing partition, with the choice of (cyclically) ordering the elements increasingly.

Importantly, it was shown by Biane [5] that geodesic permutations are characterized using the metric induced by the length function on the symmetric group: $\alpha \in S_n$ is a geodesic permutation if and only if it saturates the triangle inequality

$$ \|\alpha\| + \|\alpha^{-1}\gamma\| = \|\gamma\| = n-1, $$

where $\gamma = (1, 2, \dots, n)$ is the full-cycle permutation. Note that in this case $\alpha$ lies on a geodesic between the identity permutation $id = (1)(2)\cdots(n)$ and $\gamma = (1, 2, \dots, n)$.

In this paper, we will identify geodesic permutations $\alpha \in S_n$ with the corresponding non-crossing partition $\alpha \in \text{NC}(n)$. With this identification, the identity permutation $id$ corresponds to the singleton partition $0_n$, and the full cycle permutation $\gamma$ corresponds to the single-block partition $1_n$. Apart from these two special (extremal) objects, we will use the same notation for geodesic permutations and non-crossing partitions, usually Greek letters $\alpha, \beta, \sigma$, etc.

The set $\text{NC}(n)$ is endowed with a partial order called reversed refinement: $\alpha \le \beta$ if every block of $\alpha$ is contained in a block of $\beta$. Note that this order relation is not total: for example, the partitions $\{1\} \sqcup \{2, 3\}$ and $\{2\} \sqcup \{1, 3\}$ are not comparable. This partial order can be nicely characterized in terms of the associated geodesic
<figure><img src="image_5.png" /><figcaption>Figure 3. The Kreweras complement of $\alpha = \{1\} \sqcup \{2, 6\} \sqcup \{3, 4\} \sqcup \{5\}$ is $\alpha^{\mathrm{Kr}} = \{1, 6\} \sqcup \{2, 4, 5\} \sqcup \{3\}$.</figcaption></figure>

permutations: $\alpha \le \beta$ is equivalent to $\alpha$ lying on a geodesic between id and $\beta$:

$$ \|\alpha\| + \|\alpha^{-1}\beta\| = \|\beta\|. $$

Let us now discuss the important notion of *Kreweras complement* for non-crossing partitions. The Kreweras complement is an order-reversing map $\alpha \mapsto \alpha^{\mathrm{Kr}}$ of $\mathrm{NC}(n)$, defined in the following way [20, Definition 9.21]. First, double the elements of the basis set to obtain $\{1, \bar{1}, 2, \bar{2}, \dots, n, \bar{n}\}$ and then consider $\alpha^{\mathrm{Kr}} \in \mathrm{NC}(\bar{1}, \bar{2}, \dots, \bar{n}) \cong \mathrm{NC}(n)$ to be the largest non-crossing partition such that $\alpha \sqcup \alpha^{\mathrm{Kr}}$ is still a non-crossing partition on $\{1, \bar{1}, 2, \bar{2}, \dots, n, \bar{n}\}$. This operation is best explained by an example; see Figure 3: for $\alpha = (1)(2, 6)(3, 4)(5)$, we have $\alpha^{\mathrm{Kr}} = (1, 6)(2, 4, 5)(3)$. The extremal elements in $\mathrm{NC}(n)$ are swapped: $\mathrm{id}^{\mathrm{Kr}} = \gamma$ and $\gamma^{\mathrm{Kr}} = \mathrm{id}$. In the language of geodesic permutations, given a geodesic permutation $\mathrm{id} - \alpha - \gamma$, the Kreweras complement of $\alpha$ corresponds to the permutation $\alpha^{\mathrm{Kr}} \in S_n$ defined as

$$ \alpha^{\mathrm{Kr}} = \alpha^{-1}\gamma; \qquad (1) $$

see [20, Remark 23.24] for details. Importantly, for $\alpha \in \mathrm{NC}(n)$, we have

$$ \|\alpha\| + \|\alpha^{\mathrm{Kr}}\| = n - 1. \qquad (2) $$

Finally, let us discuss the bijection between $\mathrm{NC}(n)$ and $\mathrm{NC}_2(2n)$, called *fattening* (Note that both sets are counted by the Catalan numbers.) For a given non-crossing partition $\alpha \in \mathrm{NC}(n)$, we consider two points $i_-$ and $i_+$ for both sides of each $i \in \{1, \dots, n\}$, left and right, respectively, doubling in this way the index set. We associate to $\alpha$ the following pairing: connect $i_+$ and $j_-$ if $\alpha(i) = j$, where $\alpha$ is seen now as a permutation. It can be shown that the pair partition obtained in this way is non-crossing; see [20, Lecture 9] for the details.

## 2.2. Loops in meandric systems

As discussed in the introduction, there has been a lot of interest in counting meandric systems with respect to their number of connected components, which we call *loops*.
<figure><img src="image_5.png" /><figcaption>Figure 3. The Kreweras complement of $\alpha = \{1\} \sqcup \{2, 6\} \sqcup \{3, 4\} \sqcup \{5\}$ is $\alpha^{\mathrm{Kr}} = \{1, 6\} \sqcup \{2, 4, 5\} \sqcup \{3\}$.</figcaption></figure>

permutations: $\alpha \le \beta$ is equivalent to $\alpha$ lying on a geodesic between id and $\beta$:

$$ \|\alpha\| + \|\alpha^{-1}\beta\| = \|\beta\|. $$

Let us now discuss the important notion of *Kreweras complement* for non-crossing partitions. The Kreweras complement is an order-reversing map $\alpha \mapsto \alpha^{\mathrm{Kr}}$ of $\mathrm{NC}(n)$, defined in the following way [20, Definition 9.21]. First, double the elements of the basis set to obtain $\{1, \bar{1}, 2, \bar{2}, \dots, n, \bar{n}\}$ and then consider $\alpha^{\mathrm{Kr}} \in \mathrm{NC}(\bar{1}, \bar{2}, \dots, \bar{n}) \cong \mathrm{NC}(n)$ to be the largest non-crossing partition such that $\alpha \sqcup \alpha^{\mathrm{Kr}}$ is still a non-crossing partition on $\{1, \bar{1}, 2, \bar{2}, \dots, n, \bar{n}\}$. This operation is best explained by an example; see Figure 3: for $\alpha = (1)(2, 6)(3, 4)(5)$, we have $\alpha^{\mathrm{Kr}} = (1, 6)(2, 4, 5)(3)$. The extremal elements in $\mathrm{NC}(n)$ are swapped: $\mathrm{id}^{\mathrm{Kr}} = \gamma$ and $\gamma^{\mathrm{Kr}} = \mathrm{id}$. In the language of geodesic permutations, given a geodesic permutation id $-\alpha - \gamma$, the Kreweras complement of $\alpha$ corresponds to the permutation $\alpha^{\mathrm{Kr}} \in S_n$ defined as

$$ \alpha^{\mathrm{Kr}} = \alpha^{-1}\gamma; \qquad (1) $$

see [20, Remark 23.24] for details. Importantly, for $\alpha \in \mathrm{NC}(n)$, we have

$$ \|\alpha\| + \|\alpha^{\mathrm{Kr}}\| = n - 1. \qquad (2) $$

Finally, let us discuss the bijection between $\mathrm{NC}(n)$ and $\mathrm{NC}_2(2n)$, called *fattening* (Note that both sets are counted by the Catalan numbers.) For a given non-crossing partition $\alpha \in \mathrm{NC}(n)$, we consider two points $i_-$ and $i_+$ for both sides of each $i \in \{1, \dots, n\}$, left and right, respectively, doubling in this way the index set. We associate to $\alpha$ the following pairing: connect $i_+$ and $j_-$ if $\alpha(i) = j$, where $\alpha$ is seen now as a permutation. It can be shown that the pair partition obtained in this way is non-crossing; see [20, Lecture 9] for the details.

## 2.2. Loops in meandric systems

As discussed in the introduction, there has been a lot of interest in counting meandric systems with respect to their number of connected components, which we call *loops*.
<figure><img src="image_6.png" /><figcaption>**Figure 4.** A meandric system generated by the geodesic permutations (in black) $\alpha = (1, 2)(3, 4, 5)$ and $\beta = (1, 2, 4)(3)(5)$. The two loops (blue and red together) with arrows are formed by the action of $\alpha^{-1}\beta$.</figcaption></figure>

In this paper, we will regard meandric systems as pairs of non-crossing partitions (or geodesic permutations). This point of view is best explained with an example; see Figure 4. In this figure, the meandric system is made of the blue and red arches, connecting the points $\{i_{\pm}\}_{i \in [5]}$. The blue (resp., red) arches on top (resp., bottom) on the reference line are associated to non-crossing pairings (called arch configurations in [9]), which, in turn, are in bijection to the non-crossing partitions connecting the points $\{i\}_{i \in [5]}$ displayed in black. In the figure, the black lines above and below the reference line correspond to non-crossing partitions $\alpha = (1, 2)(3, 4, 5)$ and $\beta = (1, 2, 4)(3)(5)$, respectively. The blue and red lines are fattenings of those permutations, which are non-crossing pairings generating the meandric system. In this example, the number of loops in this meandric system is 2. Remarkably, it can be calculated by

$$ \#(\alpha^{-1}\beta) = \#((1, 2)(5, 4, 3) \circ (1, 2, 4)(3)(5)) = \#((1)(2, 3, 5, 4)) = 2. $$

To see this, one can follow the arrows in the figure to count the number of loops. In addition, note that in this example the top side is shallow while the bottom is not.

In short, graphically, two permutations over and under the straight lines give structural lines. “Fattening” them (or drawing new lines on both sides of those lines) gives loops of the meandric system. We state this property in general in the following proposition. One can refer to [19, Section 3] or [12, Proposition 3.1] for the proof.

**Proposition 2.1.** Suppose that a meandric system on $2n$ points is generated by $\alpha, \beta \in \text{NC}(n)$. Then, the number of loops of the meandric system is $\#(\alpha^{-1}\beta)$, the number of cycles of the permutation $\alpha^{-1}\beta$.

The result above is crucial to our work, since it allows us to relate the problem of counting loops of meandric systems to a combinatorial problem on (special subsets of) the symmetric group. We will also need the following lemma, showing that the Kreweras complement operation does not change the statistics of the systems.
<figure><img src="image_6.png" /><figcaption>**Figure 4.** A meandric system generated by the geodesic permutations (in black) $\alpha = (1, 2)(3, 4, 5)$ and $\beta = (1, 2, 4)(3)(5)$. The two loops (blue and red together) with arrows are formed by the action of $\alpha^{-1}\beta$.</figcaption></figure>

In this paper, we will regard meandric systems as pairs of non-crossing partitions (or geodesic permutations). This point of view is best explained with an example; see Figure 4. In this figure, the meandric system is made of the blue and red arches, connecting the points $\{i_{\pm}\}_{i \in [5]}$. The blue (resp., red) arches on top (resp., bottom) on the reference line are associated to non-crossing pairings (called arch configurations in [9]), which, in turn, are in bijection to the non-crossing partitions connecting the points $\{i\}_{i \in [5]}$ displayed in black. In the figure, the black lines above and below the reference line correspond to non-crossing partitions $\alpha = (1, 2)(3, 4, 5)$ and $\beta = (1, 2, 4)(3)(5)$, respectively. The blue and red lines are fattenings of those permutations, which are non-crossing pairings generating the meandric system. In this example, the number of loops in this meandric system is 2. Remarkably, it can be calculated by

$$ \#(\alpha^{-1}\beta) = \#((1, 2)(5, 4, 3) \circ (1, 2, 4)(3)(5)) = \#((1)(2, 3, 5, 4)) = 2. $$

To see this, one can follow the arrows in the figure to count the number of loops. In addition, note that in this example the top side is shallow while the bottom is not.

In short, graphically, two permutations over and under the straight lines give structural lines. “Fattening” them (or drawing new lines on both sides of those lines) gives loops of the meandric system. We state this property in general in the following proposition. One can refer to [19, Section 3] or [12, Proposition 3.1] for the proof.

**Proposition 2.1.** Suppose that a meandric system on $2n$ points is generated by $\alpha, \beta \in \text{NC}(n)$. Then, the number of loops of the meandric system is $\#(\alpha^{-1}\beta)$, the number of cycles of the permutation $\alpha^{-1}\beta$.

The result above is crucial to our work, since it allows us to relate the problem of counting loops of meandric systems to a combinatorial problem on (special subsets of) the symmetric group. We will also need the following lemma, showing that the Kreweras complement operation does not change the statistics of the systems.
**Proposition 2.2.** For $\alpha, \beta \in \text{NC}(n)$, we have

$$ \#((\alpha^{\text{Kr}})^{-1} \beta^{\text{Kr}}) = \#(\alpha^{-1} \beta). $$

*Proof.* By using the property of Kreweras complement, we have

$$ (\alpha^{\text{Kr}})^{-1} \beta^{\text{Kr}} = (\alpha^{-1} \gamma)^{-1} (\beta^{-1} \gamma) = \gamma^{-1} \alpha \beta^{-1} \gamma. $$

Since $\#(\cdot)$ is a class function, we have proved the claim.

# 3. Free and Boolean transformations

Our approach for the enumeration of special subsets of meandric systems is based on the theory of non-commutative probability theory. More precisely, using the various notions of independence existing in the non-commutative setting, we decompose meandric systems in irreducible components via the corresponding moment-cumulant formulas, which we then proceed to enumerate. In this section, we gather the relevant facts and formulas from the theory of free and Boolean independence, as well as some related technical combinatorial results that will be used in the later sections.

## 3.1. Basics

Below we discuss structures of the non-crossing partitions and the interval partitions and associated transforms. Although these notions stem from various notions of non-commutative independence, we will not make use of the probabilistic interpretations and focus on the combinatorics. Concretely, we will use these transforms to relate the generating series of some combinatorial class (encoded by the moments of some non-commutative distribution) to the generating series of a simpler class (encoded by the cumulants of some type). In the free probability theory, one can define inevitable transforms called *moment-cumulant formula*: for a lattice $L(n) \in \{\text{Int}(n), \text{NC}(n)\}$, it holds that

$$ \varphi(a_1 \cdots a_n) = \sum_{\sigma \in L(n)} \kappa_{\sigma}[a_1, \dots, a_n], $$

where $\varphi(\cdot)$ and $\kappa(\cdot)$ are, respectively, moment and cumulant functionals (depending on $L$), and $a_i$'s are non-commutative random variables. Interested readers can refer to [17, 20, 22]. Now, restricting ourselves to the case

$$ a = a_1 = \cdots = a_n $$

and using the multiplicativity of $\kappa(\cdot)$, we define the following transformations.
**Proposition 2.2.** For $\alpha, \beta \in \text{NC}(n)$, we have

$$ \#((\alpha^{\text{Kr}})^{-1} \beta^{\text{Kr}}) = \#(\alpha^{-1} \beta). $$

*Proof.* By using the property of Kreweras complement, we have

$$ (\alpha^{\text{Kr}})^{-1} \beta^{\text{Kr}} = (\alpha^{-1} \gamma)^{-1} (\beta^{-1} \gamma) = \gamma^{-1} \alpha \beta^{-1} \gamma. $$

Since $\#(\cdot)$ is a class function, we have proved the claim.

# 3. Free and Boolean transformations

Our approach for the enumeration of special subsets of meandric systems is based on the theory of non-commutative probability theory. More precisely, using the various notions of independence existing in the non-commutative setting, we decompose meandric systems in irreducible components via the corresponding moment-cumulant formulas, which we then proceed to enumerate. In this section, we gather the relevant facts and formulas from the theory of free and Boolean independence, as well as some related technical combinatorial results that will be used in the later sections.

## 3.1. Basics

Below we discuss structures of the non-crossing partitions and the interval partitions and associated transforms. Although these notions stem from various notions of non-commutative independence, we will not make use of the probabilistic interpretations and focus on the combinatorics. Concretely, we will use these transforms to relate the generating series of some combinatorial class (encoded by the moments of some non-commutative distribution) to the generating series of a simpler class (encoded by the cumulants of some type). In the free probability theory, one can define inevitable transforms called *moment-cumulant formula*: for a lattice $L(n) \in \{\text{Int}(n), \text{NC}(n)\}$, it holds that

$$ \varphi(a_1 \cdots a_n) = \sum_{\sigma \in L(n)} \kappa_{\sigma}[a_1, \dots, a_n], $$

where $\varphi(\cdot)$ and $\kappa(\cdot)$ are, respectively, moment and cumulant functionals (depending on $L$), and $a_i$'s are non-commutative random variables. Interested readers can refer to [17, 20, 22]. Now, restricting ourselves to the case

$$ a = a_1 = \cdots = a_n $$

and using the multiplicativity of $\kappa(\cdot)$, we define the following transformations.
**Definition 3.1.** Between sequences of numbers, the Boolean transform $\mathcal{F}_{\text{boole}}$ and the free transform $\mathcal{F}_{\text{free}}$

$$ \mathcal{F} : \{\kappa_n\}_{n=1}^{\infty} \mapsto \{m_n\}_{n=1}^{\infty} $$

are defined by

$$ m_n = \sum_{\sigma \in L(n)} \prod_{c \in \sigma} \kappa_{|c|}. $$

Here, $L(n) = \text{Int}(n)$ in the case of $\mathcal{F}_{\text{boole}}$ and $L(n) = \text{NC}(n)$ in the case of $\mathcal{F}_{\text{free}}$, while $c \in \sigma$ are the blocks of $\sigma$. This can be extended naturally to maps between polynomials (moment and cumulant generating functions)

$$ \mathcal{F} : K(X) \mapsto M(X), $$

where

$$ M(X) = \sum_{n=1}^{\infty} m_n X^n \quad \text{and} \quad K(X) = \sum_{n=1}^{\infty} \kappa_n X^n. $$

We quote a well-known property of the Boolean transform.

**Proposition 3.2** (Functional relation for Boolean transform [22, Proposition 2.1]). Suppose that the moment and cumulant generating functions $M = M(X)$ and $K = K(X)$ are related through the Boolean transform as in Definition 3.1: $\mathcal{F}_{\text{boole}}: K \mapsto M$. Then,

$$ K = \frac{M}{1+M} \quad \text{and} \quad M = \frac{K}{1-K}. $$

Next, we state a simple generalization of the moment-cumulant formula for free independence [20, Lecture 11] which treats the last block (i.e., the block containing $n$ for a partition $\beta \in \text{NC}(n)$) separately. It is a standard fact in free probability theory [20, Theorem 12.5] that the two generating series $K, M$, related by the free transform

$$ \mathcal{F}_{\text{free}}: K \mapsto M, $$

satisfy the *implicit* equation

$$ M(X) = K(X(1 + M(X))). $$

**Lemma 3.3.** For two sequences $\{h_n\}_{n=1}^{\infty}$ and $\{g_n\}_{n=1}^{\infty}$, we have

$$ \sum_{n=1}^{\infty} X^n \sum_{\beta \in \text{NC}(n)} h_{|\beta(n)|} \prod_{c \in \beta'} g_{|c|} = \sum_{s=1}^{\infty} h_s X^s \left( 1 + \sum_{i=1}^{\infty} \hat{g}_i X^i \right)^s. $$
**Definition 3.1.** Between sequences of numbers, the Boolean transform $\mathcal{F}_{\text{boole}}$ and the free transform $\mathcal{F}_{\text{free}}$

$$ \mathcal{F} : \{\kappa_n\}_{n=1}^{\infty} \mapsto \{m_n\}_{n=1}^{\infty} $$

are defined by

$$ m_n = \sum_{\sigma \in L(n)} \prod_{c \in \sigma} \kappa_{|c|}. $$

Here, $L(n) = \text{Int}(n)$ in the case of $\mathcal{F}_{\text{boole}}$ and $L(n) = \text{NC}(n)$ in the case of $\mathcal{F}_{\text{free}}$, while $c \in \sigma$ are the blocks of $\sigma$. This can be extended naturally to maps between polynomials (moment and cumulant generating functions)

$$ \mathcal{F} : K(X) \mapsto M(X), $$

where

$$ M(X) = \sum_{n=1}^{\infty} m_n X^n \quad \text{and} \quad K(X) = \sum_{n=1}^{\infty} \kappa_n X^n. $$

We quote a well-known property of the Boolean transform.

**Proposition 3.2** (Functional relation for Boolean transform [22, Proposition 2.1]). Suppose that the moment and cumulant generating functions $M = M(X)$ and $K = K(X)$ are related through the Boolean transform as in Definition 3.1: $\mathcal{F}_{\text{boole}}: K \mapsto M$. Then,

$$ K = \frac{M}{1+M} \quad \text{and} \quad M = \frac{K}{1-K}. $$

Next, we state a simple generalization of the moment-cumulant formula for free independence [20, Lecture 11] which treats the last block (i.e., the block containing $n$ for a partition $\beta \in \text{NC}(n)$) separately. It is a standard fact in free probability theory [20, Theorem 12.5] that the two generating series $K, M$, related by the free transform

$$ \mathcal{F}_{\text{free}}: K \mapsto M, $$

satisfy the *implicit* equation

$$ M(X) = K(X(1 + M(X))). $$

**Lemma 3.3.** For two sequences $\{h_n\}_{n=1}^{\infty}$ and $\{g_n\}_{n=1}^{\infty}$, we have

$$ \sum_{n=1}^{\infty} X^n \sum_{\beta \in \text{NC}(n)} h_{|\beta(n)|} \prod_{c \in \beta'} g_{|c|} = \sum_{s=1}^{\infty} h_s X^s \left( 1 + \sum_{i=1}^{\infty} \hat{g}_i X^i \right)^s. $$
Here, ${\hat{g}_n}^\infty_{n=1}$ is the free transform of ${g_n}^\infty_{n=1}$ as defined in Definition 3.1, and we used the following decomposition:

$$ \beta = \beta' \sqcup \beta(n), \qquad (3) $$

where $\beta(n)$ is the block of $\beta$ containing $n$.

*Proof.* Our proof is a standard computation:

$$
\begin{align*}
& \sum_{n=1}^{\infty} X^n \sum_{\beta \in \mathrm{NC}(n)} h_{|\beta(n)|} \prod_{c \in \beta'} g_{|c|} \\
&= \sum_{n=1}^{\infty} \sum_{s=1}^{n} h_s X^s \sum_{\substack{i_1+\dots+i_s=n-s \\ \text{with } i_j \ge 0}} \prod_{j=1}^{s} \underbrace{\sum_{\beta'_j \in \mathrm{NC}(i_j)} \prod_{c \in \beta'_j} g_{|c|} X^{|c|}}_{(\blacksquare)} \\
&= \sum_{s=1}^{\infty} h_s X^s \sum_{m=0}^{\infty} \sum_{\substack{i_1+\dots+i_m=m \\ \text{with } i_j \ge 0}} \prod_{j=1}^{s} \hat{g}_{i_j} X^{i_j} \\
&= \sum_{s=1}^{\infty} h_s X^s \left( 1 + \sum_{i=1}^{\infty} \hat{g}_i X^i \right)^s.
\end{align*}
$$

In the calculation, we have $(\blacksquare) = 1$ when $i_j = 0$ (we set $X^0 = 1$), which corresponds to the Catalan number $\mathrm{Cat}_0 = 1$. ■

## 3.2. Join and meet

On the lattice of $\mathrm{NC}(n)$, two important operations are defined. The first one is the so-called join: it is the smallest element $\gamma \in \mathrm{NC}(n)$ such that $\gamma \ge \alpha, \beta$. The other one is the so-called meet: the largest element $\gamma \in \mathrm{NC}(n)$ such that $\gamma \le \alpha, \beta$. More precisely, for $\alpha, \beta \in \mathrm{NC}(n)$, we consider their

$$ \text{join: } \alpha \lor \beta = \min\{\gamma \in \mathrm{NC}(n) : \alpha, \beta \le \gamma\}, $$

$$ \text{meet: } \alpha \land \beta = \max\{\gamma \in \mathrm{NC}(n) : \alpha, \beta \ge \gamma\}. $$

Here, the smallest and the largest elements in $\mathrm{NC}(n)$ are denoted by $0_n$ and $1_n$ such that $0_n = (1) \cdots (n)$ and $1_n = (1, \dots, n)$. Note that

$$ (\alpha \land \beta)^{\mathrm{Kr}} = \alpha^{\mathrm{Kr}} \lor \beta^{\mathrm{Kr}} $$

and

$$ (\alpha \lor \beta)^{\mathrm{Kr}} = \alpha^{\mathrm{Kr}} \land \beta^{\mathrm{Kr}}; $$

see [20, Lecture 9].
Here, ${\hat{g}_n}^\infty_{n=1}$ is the free transform of ${g_n}^\infty_{n=1}$ as defined in Definition 3.1, and we used the following decomposition:

$$ \beta = \beta' \sqcup \beta(n), \qquad (3) $$

where $\beta(n)$ is the block of $\beta$ containing $n$.

*Proof.* Our proof is a standard computation:

$$
\begin{align*}
& \sum_{n=1}^{\infty} X^n \sum_{\beta \in \mathrm{NC}(n)} h_{|\beta(n)|} \prod_{c \in \beta'} g_{|c|} \\
&= \sum_{n=1}^{\infty} \sum_{s=1}^{n} h_s X^s \sum_{\substack{i_1+\dots+i_s=n-s \\ \text{with } i_j \ge 0}} \prod_{j=1}^{s} \underbrace{\sum_{\beta'_j \in \mathrm{NC}(i_j)} \prod_{c \in \beta'_j} g_{|c|} X^{|c|}}_{(\blacksquare)} \\
&= \sum_{s=1}^{\infty} h_s X^s \sum_{m=0}^{\infty} \sum_{\substack{i_1+\dots+i_m=m \\ \text{with } i_j \ge 0}} \prod_{j=1}^{s} \hat{g}_{i_j} X^{i_j} \\
&= \sum_{s=1}^{\infty} h_s X^s \left( 1 + \sum_{i=1}^{\infty} \hat{g}_i X^i \right)^s.
\end{align*}
$$

In the calculation, we have $(\blacksquare) = 1$ when $i_j = 0$ (we set $X^0 = 1$), which corresponds to the Catalan number $\mathrm{Cat}_0 = 1$. ■

## 3.2. Join and meet

On the lattice of $\mathrm{NC}(n)$, two important operations are defined. The first one is the so-called join: it is the smallest element $\gamma \in \mathrm{NC}(n)$ such that $\gamma \ge \alpha, \beta$. The other one is the so-called meet: the largest element $\gamma \in \mathrm{NC}(n)$ such that $\gamma \le \alpha, \beta$. More precisely, for $\alpha, \beta \in \mathrm{NC}(n)$, we consider their

$$ \text{join: } \alpha \lor \beta = \min\{\gamma \in \mathrm{NC}(n) : \alpha, \beta \le \gamma\}, $$

$$ \text{meet: } \alpha \land \beta = \max\{\gamma \in \mathrm{NC}(n) : \alpha, \beta \ge \gamma\}. $$

Here, the smallest and the largest elements in $\mathrm{NC}(n)$ are denoted by $0_n$ and $1_n$ such that $0_n = (1) \cdots (n)$ and $1_n = (1, \dots, n)$. Note that

$$ (\alpha \land \beta)^{\mathrm{Kr}} = \alpha^{\mathrm{Kr}} \lor \beta^{\mathrm{Kr}} $$

and

$$ (\alpha \lor \beta)^{\mathrm{Kr}} = \alpha^{\mathrm{Kr}} \land \beta^{\mathrm{Kr}}; $$

see [20, Lecture 9].
First, we restrict the operations meet and join to $Int(n) \subseteq NC(n)$. To this end, we denote the complement of $Int(n)$ by

$$ \mathrm{Kr}\,\mathrm{Int}(n) = \{\alpha^{\mathrm{Kr}} : \alpha \in \mathrm{Int}(n)\}. $$

Notice that a partition is included in $\mathrm{Kr}\,\mathrm{Int}(n)$ if and only if it consists of a block containing $n$ and singletons. See Lemma 3.9 for details. Then, we have the following.

**Definition 3.4.** We define join and meet in $Int(n)$: for $\alpha, \beta \in NC(n)$,

$$ \alpha \vee_{\mathrm{Int}} \beta = \min\{\gamma \in \mathrm{Int}(n) : \alpha, \beta \le \gamma\}, \\ \alpha \wedge_{\mathrm{Kr}\,\mathrm{Int}} \beta = \max\{\gamma \in \mathrm{Kr}\,\mathrm{Int}(n) : \alpha, \beta \ge \gamma\}. $$

The new join $\alpha \vee_{\mathrm{Int}} \beta$ is obtained by finding the smallest interval partition which is larger than or equal to both of the interval partitions naturally induced by the “outer shells” of $\alpha$ and $\beta$. The new meet $\alpha \wedge_{\mathrm{Kr}\,\mathrm{Int}} \beta$ can be calculated as follows. Take the blocks in $\alpha$ and $\beta$ which contain $n$ and denote them as $\alpha(n)$ and $\beta(n)$. Then, $\alpha \wedge_{\mathrm{Kr}\,\mathrm{Int}} \beta$ is the partition consisting of the block induced by the set $\alpha(n) \cap \beta(n)$ and isolated points. The above construction lets us recover the similar identity as before:

$$ (\alpha \vee_{\mathrm{Int}} \beta)^{\mathrm{Kr}} = \alpha^{\mathrm{Kr}} \wedge_{\mathrm{Kr}\,\mathrm{Int}} \beta^{\mathrm{Kr}}. $$

**Remark 3.5.** The notion $\alpha \vee_{\mathrm{Int}} \beta$ in Definition 3.4 coincides with the definition of “interval closure” in [3, Definition 2.3—(11)].

**Lemma 3.6 (Key decomposition).** We have the following bijective map: for fixed $\sigma = c_1 \cdots c_m \in \mathrm{Int}(n)$, where the $c_i$'s are the blocks of $\sigma$,

$$ \{(\alpha, \beta) \in \mathrm{Int}(n) \times \mathrm{NC}(n) : \alpha \vee_{\mathrm{Int}} \beta = \sigma\} \\ \xrightarrow[m]{i=1} \{(\alpha_i, \beta_i) \in \mathrm{Int}(|c_i|) \times \mathrm{NC}(|c_i|) : \alpha \vee_{\mathrm{Int}} \beta = 1_{|c_i|}\}. $$

Also, a similar one-to-one relation holds true after replacing $NC(n)$ by $\mathrm{Int}(n)$.

*Proof.* First, we define the map. The condition $\sigma = \alpha \vee_{\mathrm{Int}} \beta$ has two implications. One is that we can write $\alpha = \bigsqcup_{i=1}^m \alpha|_{c_i}$ and $\beta = \bigsqcup_{i=1}^m \beta|_{c_i}$, where $\alpha|_{c_i} \in \mathrm{Int}(|c_i|)$ and $\beta|_{c_i} \in \mathrm{NC}(|c_i|)$; i.e., each block of $\alpha$ and $\beta$ belongs to one of $c_i$'s. This is because $\alpha \vee_{\mathrm{Int}} \beta$ would be coarser otherwise. The other is that $\alpha|_{c_i} \vee_{\mathrm{Int}} \beta|_{c_i} = 1_{|c_i|}$ because $\alpha \vee_{\mathrm{Int}} \beta$ would be finer otherwise. Next, it is clear that the map is injective because if two permutations are identical on each sub-interval, they are necessarily the same. Finally, to show surjectivity, take $\alpha|_{c_i} \in \mathrm{Int}(|c_i|)$ and $\beta|_{c_i} \in \mathrm{NC}(|c_i|)$ with $\alpha|_{c_i} \vee_{\mathrm{Int}} \beta|_{c_i} = 1_{|c_i|}$, and form $\alpha = \bigsqcup_{i=1}^m \alpha|_{c_i} \in \mathrm{Int}(n)$ and $\beta = \bigsqcup_{i=1}^m \beta|_{c_i} \in \mathrm{NC}(n)$. The construction implies that $\alpha \vee_{\mathrm{Int}} \beta \le \sigma$, and the condition $\alpha|_{c_i} \vee_{\mathrm{Int}} \beta|_{c_i} = 1_{|c_i|}$ implies that $\alpha \vee_{\mathrm{Int}} \beta \ge \sigma$. This completes the proof. ■
First, we restrict the operations meet and join to $Int(n) \subseteq NC(n)$. To this end, we denote the complement of $Int(n)$ by

$$ \mathrm{KrInt}(n) = \{ \alpha^{\mathrm{Kr}} : \alpha \in \mathrm{Int}(n) \}. $$

Notice that a partition is included in $\mathrm{KrInt}(n)$ if and only if it consists of a block containing $n$ and singletons. See Lemma 3.9 for details. Then, we have the following.

**Definition 3.4.** We define join and meet in $Int(n)$: for $\alpha, \beta \in NC(n)$,

$$ \alpha \vee_{\mathrm{Int}} \beta = \min\{\gamma \in \mathrm{Int}(n) : \alpha, \beta \leq \gamma\}, \\ \alpha \wedge_{\mathrm{KrInt}} \beta = \max\{\gamma \in \mathrm{KrInt}(n) : \alpha, \beta \geq \gamma\}. $$

The new join $\alpha \vee_{\mathrm{Int}} \beta$ is obtained by finding the smallest interval partition which is larger than or equal to both of the interval partitions naturally induced by the “outer shells” of $\alpha$ and $\beta$. The new meet $\alpha \wedge_{\mathrm{KrInt}} \beta$ can be calculated as follows. Take the blocks in $\alpha$ and $\beta$ which contain $n$ and denote them as $\alpha(n)$ and $\beta(n)$. Then, $\alpha \wedge_{\mathrm{KrInt}} \beta$ is the partition consisting of the block induced by the set $\alpha(n) \cap \beta(n)$ and isolated points. The above construction lets us recover the similar identity as before:

$$ (\alpha \vee_{\mathrm{Int}} \beta)^{\mathrm{Kr}} = \alpha^{\mathrm{Kr}} \wedge_{\mathrm{KrInt}} \beta^{\mathrm{Kr}}. $$

**Remark 3.5.** The notion $\alpha \vee_{\mathrm{Int}} \beta$ in Definition 3.4 coincides with the definition of “interval closure” in [3, Definition 2.3—(11)].

**Lemma 3.6 (Key decomposition).** We have the following bijective map: for fixed $\sigma = c_1 \cdots c_m \in \mathrm{Int}(n)$, where the $c_i$'s are the blocks of $\sigma$,

$$ \{(\alpha, \beta) \in \mathrm{Int}(n) \times \mathrm{NC}(n) : \alpha \vee_{\mathrm{Int}} \beta = \sigma\} \\ \xrightarrow[m]{i=1} \{(\alpha_i, \beta_i) \in \mathrm{Int}(|c_i|) \times \mathrm{NC}(|c_i|) : \alpha \vee_{\mathrm{Int}} \beta = 1_{|c_i|}\}. $$

Also, a similar one-to-one relation holds true after replacing $NC(n)$ by $\mathrm{Int}(n)$.

*Proof.* First, we define the map. The condition $\sigma = \alpha \vee_{\mathrm{Int}} \beta$ has two implications. One is that we can write $\alpha = \bigsqcup_{i=1}^m \alpha|_{c_i}$ and $\beta = \bigsqcup_{i=1}^m \beta|_{c_i}$, where $\alpha|_{c_i} \in \mathrm{Int}(|c_i|)$ and $\beta|_{c_i} \in \mathrm{NC}(|c_i|)$; i.e., each block of $\alpha$ and $\beta$ belongs to one of $c_i$'s. This is because $\alpha \vee_{\mathrm{Int}} \beta$ would be coarser otherwise. The other is that $\alpha|_{c_i} \vee_{\mathrm{Int}} \beta|_{c_i} = 1_{|c_i|}$ because $\alpha \vee_{\mathrm{Int}} \beta$ would be finer otherwise. Next, it is clear that the map is injective because if two permutations are identical on each sub-interval, they are necessarily the same. Finally, to show surjectivity, take $\alpha|_{c_i} \in \mathrm{Int}(|c_i|)$ and $\beta|_{c_i} \in \mathrm{NC}(|c_i|)$ with $\alpha|_{c_i} \vee_{\mathrm{Int}} \beta|_{c_i} = 1_{|c_i|}$, and form $\alpha = \bigsqcup_{i=1}^m \alpha|_{c_i} \in \mathrm{Int}(n)$ and $\beta = \bigsqcup_{i=1}^m \beta|_{c_i} \in \mathrm{NC}(n)$. The construction implies that $\alpha \vee_{\mathrm{Int}} \beta \leq \sigma$, and the condition $\alpha|_{c_i} \vee_{\mathrm{Int}} \beta|_{c_i} = 1_{|c_i|}$ implies that $\alpha \vee_{\mathrm{Int}} \beta \geq \sigma$. This completes the proof. ■
**Definition 3.7.** For $L(n) = \text{NC}(n)$ or $\text{Int}(n)$, define the following sets:

$$M_{n,r,a,b} = \{(\alpha, \beta) \in \text{Int}(n) \times L(n) : \|\alpha^{-1}\beta\| = r, \|\alpha\| = a, \|\beta\| = b\},$$

$$K_{n,r,a,b} = \{(\alpha, \beta) \in \text{Kr Int}(n) \times \text{KrL}(n):$$

$$\|\alpha^{-1}\beta\| = r, \|\alpha^{-1}1_n\| = a, \|\beta^{-1}1_n\| = b, \alpha \wedge_{\text{Kr Int}} \beta = 0_n\}$$

$$\leftrightarrow \{(\alpha, \beta) \in \text{Int}(n) \times L(n) : \|\alpha^{-1}\beta\| = r, \|\alpha\| = a, \|\beta\| = b, \alpha \vee_{\text{Int}} \beta = 1_n\}$$

and functions

$$M(X, Y, A, B) = \sum_{n=1}^{\infty} m_n X^n, \quad \text{where } m_n = \sum_{\substack{\alpha \in \text{Int}(n) \\ \beta \in L(n)}} Y^{\|\alpha^{-1}\beta\|} A^{\|\alpha\|} B^{\|\beta\|}, \quad (4)$$

$$K(X, Y, A, B) = \sum_{n=1}^{\infty} \kappa_n X^n, \quad \text{where } \kappa_n = \sum_{\substack{\alpha \in \text{Int}(n) \\ \beta \in L(n) \\ \alpha \vee_{\text{Int}} \beta = 1_n}} Y^{\|\alpha^{-1}\beta\|} A^{\|\alpha\|} B^{\|\beta\|}. \quad (5)$$

Now, we show that $M(X, Y, A, B)$ and $K(X, Y, A, B)$ are related by the Boolean transform $\mathcal{F}_{\text{boole}}$.

**Theorem 3.8.** We have

$$\mathcal{F}_{\text{boole}} : K(X, Y, A, B) \mapsto M(X, Y, A, B).$$

*Proof.* Following the notations in Definition 3.7 and using Lemma 3.6, we have

$$\begin{aligned} m_n &= \sum_{\substack{\sigma \in \text{Int}(n) \\ \alpha \in \text{Int}(n) \\ \beta \in L(n) \\ \alpha \vee_{\text{Int}} \beta = \sigma}} Y^{\|\alpha^{-1}\beta\|} A^{\|\alpha\|} B^{\|\beta\|} \\ &= \sum_{\substack{\sigma \in \text{Int}(n) \\ c \in \sigma}} \prod_{\substack{\alpha \in \text{Int}(|c|) \\ \beta \in L(|c|) \\ \alpha \vee_{\text{Int}} \beta = 1|_c|}} Y^{\|\alpha^{-1}\beta\|} A^{\|\alpha\|} B^{\|\beta\|}. \end{aligned}$$

We conclude by identifying the Boolean cumulants $\kappa_n$ from (5) using Definition 3.1. ■

### 3.3. Useful lemmas

In this subsection, we collect claims to be used in the following sections. Readers can come back later when they are needed.

**Lemma 3.9.** The following sets are in one-to-one correspondence:

$$\text{Kr Int}(n) \leftrightarrow \{Q \sqcup \{n\} : Q \subseteq [n-1]\}.$$
**Definition 3.7.** For $L(n) = \text{NC}(n)$ or $\text{Int}(n)$, define the following sets:

$$M_{n,r,a,b} = \{(\alpha, \beta) \in \text{Int}(n) \times L(n) : \|\alpha^{-1}\beta\| = r, \|\alpha\| = a, \|\beta\| = b\},$$

$$K_{n,r,a,b} = \{(\alpha, \beta) \in \text{Kr Int}(n) \times \text{KrL}(n):$$

$$\|\alpha^{-1}\beta\| = r, \|\alpha^{-1}1_n\| = a, \|\beta^{-1}1_n\| = b, \alpha \wedge_{\text{Kr Int}} \beta = 0_n\}$$

$$\leftrightarrow \{(\alpha, \beta) \in \text{Int}(n) \times L(n) : \|\alpha^{-1}\beta\| = r, \|\alpha\| = a, \|\beta\| = b, \alpha \vee_{\text{Int}} \beta = 1_n\}$$

and functions

$$M(X, Y, A, B) = \sum_{n=1}^{\infty} m_n X^n, \quad \text{where } m_n = \sum_{\substack{\alpha \in \text{Int}(n) \\ \beta \in L(n)}} Y^{\|\alpha^{-1}\beta\|} A^{\|\alpha\|} B^{\|\beta\|}, \quad (4)$$

$$K(X, Y, A, B) = \sum_{n=1}^{\infty} \kappa_n X^n, \quad \text{where } \kappa_n = \sum_{\substack{\alpha \in \text{Int}(n) \\ \beta \in L(n) \\ \alpha \vee_{\text{Int}} \beta = 1_n}} Y^{\|\alpha^{-1}\beta\|} A^{\|\alpha\|} B^{\|\beta\|}. \quad (5)$$

Now, we show that $M(X, Y, A, B)$ and $K(X, Y, A, B)$ are related by the Boolean transform $\mathcal{F}_{\text{boole}}$.

**Theorem 3.8.** We have

$$\mathcal{F}_{\text{boole}} : K(X, Y, A, B) \mapsto M(X, Y, A, B).$$

*Proof.* Following the notations in Definition 3.7 and using Lemma 3.6, we have

$$\begin{aligned} m_n &= \sum_{\substack{\sigma \in \text{Int}(n) \\ \alpha \in \text{Int}(n) \\ \beta \in L(n) \\ \alpha \vee_{\text{Int}} \beta = \sigma}} Y^{\|\alpha^{-1}\beta\|} A^{\|\alpha\|} B^{\|\beta\|} \\ &= \sum_{\substack{\sigma \in \text{Int}(n) \\ c \in \sigma}} \prod_{\substack{\alpha \in \text{Int}(|c|) \\ \beta \in L(|c|) \\ \alpha \vee_{\text{Int}} \beta = 1|_c|}} Y^{\|\alpha^{-1}\beta\|} A^{\|\alpha\|} B^{\|\beta\|}. \end{aligned}$$

We conclude by identifying the Boolean cumulants $\kappa_n$ from (5) using Definition 3.1. ■

**3.3. Useful lemmas**

In this subsection, we collect claims to be used in the following sections. Readers can come back later when they are needed.

**Lemma 3.9.** The following sets are in one-to-one correspondence:

$$\text{Kr Int}(n) \leftrightarrow \{Q \sqcup \{n\} : Q \subseteq [n-1]\}.$$
<figure><img src="image_7.png" /><figcaption>**Figure 5.** Showing how to construct elements of Kr Int(n), where $i_m = n$. The support of the non-trivial red block is $Q \sqcup \{n\}$ in Lemma 3.9.</figcaption></figure>

*Proof.* Take some interval partition

$$ \alpha = (1, \dots, i_1)(i_1 + 1, \dots, i_2) \cdots (i_{m-1} + 1, \dots, i_m) \in \mathrm{Int}(n) \quad \text{with } i_m = n. $$

Then, by the definition of Kreweras complement, the elements $i_1, i_2, \dots, n$ constitute a block in the complement, but other elements are always isolated. See Figure 5. ■

**Remark 3.10.** We make some remarks on Lemma 3.9.

(1) The identification shows that each element in Kr Int(n) has at most one non-trivial block $Q \sqcup \{n\}$, which necessarily contains the element n. We call this block a comb.

(2) Given an element $\alpha \in \mathrm{KrInt}(n)$, we denote by $Q_\alpha \subseteq [n-1]$ the subset $Q$ appearing in the identification from Lemma 3.9.

**Lemma 3.11.** For $\alpha \in \mathrm{KrInt}(n)$ and $\beta \in \mathrm{NC}(n)$, the block containing $n$ of the partition $\alpha \wedge_{\mathrm{KrInt}} \beta \in \mathrm{KrInt}(n)$ is given by

$$ (Q_\alpha \sqcup \{n\}) \cap \beta(n), $$

where $\beta(n)$ is the block of $\beta$ containing $n$. In particular, if $\beta \in \mathrm{KrInt}(n)$, then

$$ \alpha \wedge_{\mathrm{KrInt}} \beta = \alpha \wedge \beta. $$

*Proof.* By Lemma 3.9 and Definition 3.4, the block in question is given by

$$ \max\{Q \sqcup \{n\} : Q \subseteq [n-1], Q \sqcup \{n\} \subseteq Q_\alpha \sqcup \{n\}, \beta(n)\} = (Q_\alpha \sqcup \{n\}) \cap \beta(n). $$

Next, $\beta \in \mathrm{KrInt}(n)$ implies that

$$ \alpha \wedge_{\mathrm{KrInt}} \beta = (Q_\alpha \cap Q_\beta) \sqcup \{n\} = \alpha \wedge \beta. $$

This completes the proof. ■

**Lemma 3.12.** For $\alpha \in \mathrm{KrInt}(n)$ and $\beta \in \mathrm{NC}(n)$ with $\alpha \wedge_{\mathrm{KrInt}} \beta = 0_n$, we have

$$ \#(\alpha^{-1}\beta) = 2 \cdot |\{c \in \beta' : Q \cap c = \emptyset\}| + 1 - \#(\beta') + |Q|, $$

where $\beta = \beta' \sqcup \beta(n)$ such that $\beta(n)$ is the block containing $n$, and $Q = Q_\alpha$.
<figure><img src="image_7.png" /><figcaption>**Figure 5.** Showing how to construct elements of Kr Int(n), where $i_m = n$. The support of the non-trivial red block is $Q \sqcup \{n\}$ in Lemma 3.9.</figcaption></figure>

*Proof.* Take some interval partition

$$ \alpha = (1, \dots, i_1)(i_1 + 1, \dots, i_2) \cdots (i_{m-1} + 1, \dots, i_m) \in \mathrm{Int}(n) \quad \text{with } i_m = n. $$

Then, by the definition of Kreweras complement, the elements $i_1, i_2, \dots, n$ constitute a block in the complement, but other elements are always isolated. See Figure 5. ■

**Remark 3.10.** We make some remarks on Lemma 3.9.

(1) The identification shows that each element in Kr Int(n) has at most one non-trivial block $Q \sqcup \{n\}$, which necessarily contains the element n. We call this block a *comb*.

(2) Given an element $\alpha \in \mathrm{KrInt}(n)$, we denote by $Q_\alpha \subseteq [n-1]$ the subset $Q$ appearing in the identification from Lemma 3.9.

**Lemma 3.11.** For $\alpha \in \mathrm{KrInt}(n)$ and $\beta \in \mathrm{NC}(n)$, the block containing $n$ of the partition $\alpha \wedge_{\mathrm{KrInt}} \beta \in \mathrm{KrInt}(n)$ is given by

$$ (Q_\alpha \sqcup \{n\}) \cap \beta(n), $$

where $\beta(n)$ is the block of $\beta$ containing $n$. In particular, if $\beta \in \mathrm{KrInt}(n)$, then

$$ \alpha \wedge_{\mathrm{KrInt}} \beta = \alpha \wedge \beta. $$

*Proof.* By Lemma 3.9 and Definition 3.4, the block in question is given by

$$ \max\{Q \sqcup \{n\} : Q \subseteq [n-1], Q \sqcup \{n\} \subseteq Q_\alpha \sqcup \{n\}, \beta(n)\} = (Q_\alpha \sqcup \{n\}) \cap \beta(n). $$

Next, $\beta \in \mathrm{KrInt}(n)$ implies that

$$ \alpha \wedge_{\mathrm{KrInt}} \beta = (Q_\alpha \cap Q_\beta) \sqcup \{n\} = \alpha \wedge \beta. $$

This completes the proof. ■

**Lemma 3.12.** For $\alpha \in \mathrm{KrInt}(n)$ and $\beta \in \mathrm{NC}(n)$ with $\alpha \wedge_{\mathrm{KrInt}} \beta = 0_n$, we have

$$ \#(\alpha^{-1}\beta) = 2 \cdot |\{c \in \beta' : Q \cap c = \emptyset\}| + 1 - \#(\beta') + |Q|, $$

where $\beta = \beta' \sqcup \beta(n)$ such that $\beta(n)$ is the block containing $n$, and $Q = Q_\alpha$.
<figure><img src="image_8.png" /><figcaption>**Figure 6.** Panels (b), (c), and (d) describe (6) with $|c| = 3$. The upper black lines represent $Q \sqcup \{n\}$ and the lower black lines $c$. Preexisting loops of meandric systems are represented by blue lines, and new loops produced by adding $c$ are indicated by red lines.</figcaption></figure>

*Proof.* We count loops in the meandric system made of $(\alpha, \beta)$ by adding cycles in $\beta$ one by one. First, the condition $\alpha \wedge_{\mathrm{KrInt}} \beta = 0_n$ and Lemma 3.11 imply that

$$Q \cap \beta(n) = \emptyset.$$

Figure 6a shows that having $\ell \in Q \cap \beta(n)$ would contradict the condition

$$\alpha \wedge_{\mathrm{KrInt}} \beta = 0_n.$$

This means that adding $\beta(n)$ does not increase the number of loops, which corresponds to case 2 below. Next, we add a cycle $c \in \beta'$ to increase the number of loops as follows:

$$ \begin{array}{ll} \text{case 1:} & |Q \cap c| = 0 \Rightarrow +1, \\ \text{case 2:} & |Q \cap c| = 1 \Rightarrow \pm 0, \\ \text{case 3:} & |Q \cap c| \ge 2 \Rightarrow +|Q \cap c| - 1. \end{array} \qquad (6) $$

Although case 3 includes case 2, we use the above classification to make things clear. First, the condition

$$|Q \cap c| = 0$$

means that the block $c$ produces a loop without any interaction with $Q \sqcup \{n\}$ as in Figure 6b, where a newly created loop is drawn in red. Second, with the condition

$$|Q \cap c| = 1,$$
<figure><img src="image_8.png" /><figcaption>**Figure 6.** Panels (b), (c), and (d) describe (6) with $|c| = 3$. The upper black lines represent $Q \sqcup \{n\}$ and the lower black lines $c$. Preexisting loops of meandric systems are represented by blue lines, and new loops produced by adding $c$ are indicated by red lines.</figcaption></figure>

*Proof.* We count loops in the meandric system made of $(\alpha, \beta)$ by adding cycles in $\beta$ one by one. First, the condition $\alpha \wedge_{\mathrm{KrInt}} \beta = 0_n$ and Lemma 3.11 imply that

$$Q \cap \beta(n) = \emptyset.$$

Figure 6a shows that having $\ell \in Q \cap \beta(n)$ would contradict the condition

$$\alpha \wedge_{\mathrm{KrInt}} \beta = 0_n.$$

This means that adding $\beta(n)$ does not increase the number of loops, which corresponds to case 2 below. Next, we add a cycle $c \in \beta'$ to increase the number of loops as follows:

$$ \begin{array}{ll} \text{case 1:} & |Q \cap c| = 0 \Rightarrow +1, \\ \text{case 2:} & |Q \cap c| = 1 \Rightarrow \pm 0, \\ \text{case 3:} & |Q \cap c| \ge 2 \Rightarrow +|Q \cap c| - 1. \end{array} \qquad (6) $$

Although case 3 includes case 2, we use the above classification to make things clear. First, the condition

$$|Q \cap c| = 0$$

means that the block $c$ produces a loop without any interaction with $Q \sqcup \{n\}$ as in Figure 6b, where a newly created loop is drawn in red. Second, with the condition

$$|Q \cap c| = 1,$$
no new loop will be created although the preexisting loop containing $n$ will be
stretched by $c$, which is drawn by the blue line in Figure 6c. Third, in case

$$|Q \cap c| = m \geq 2,$$

suppose that

$$Q \cap c = \{i_1, \dots, i_m\},$$

and we connect $Q \sqcup \{n\}$ and $c$ one after another. To begin with, $i_1$ does not make any loop as in case 2. Next, however, connection at $i_2$ gives a new loop, which will be enclosed by the preexisting loop, increasing genus by one; see Figure 6d. This inductive argument shows the claim on case 3.

Therefore,

$$\#(\alpha^{-1}\beta) = 1 + \sum_{c \in \beta'} [2 \cdot 1_{Q \cap c = \emptyset} - 1 + |Q \cap c|],$$

which leads to the formula because $Q \cap \beta(n) = \emptyset$ implies that

$$\sum_{c \in \beta'} |Q \cap c| = |Q|.$$

This completes the proof.

**Remark 3.13.** The result follows equally from the equivalence $1 \Leftrightarrow 4$ from [14, Theorem 4.4] and the equality

$$1 + |\{c \in \beta' : Q \cap c = \emptyset\}| = \#(\alpha \tilde{\vee} \beta),$$

where $\tilde{\vee}$ denotes the join operation in the lattice of all partitions.

**Lemma 3.14.** For any partition $\beta$ of order $n$, not necessarily in $NC(n)$,

$$\sum_{Q \subseteq [n]} A^{|Q|} B^{|\{c \in \beta : Q \cap c = \emptyset\}|} = \prod_{c \in \beta} ((A+1)^{|c|} + B - 1).$$

*Proof.* First, note that the LHS, which we denote by $S(\beta)$, is multiplicative for block decomposition in $NC(n)$. Indeed, for $\beta = \beta_1 \sqcup \beta_2$,

$$
\begin{align*}
S(\beta) &= \sum_{Q \subseteq [n]} A^{|Q|} B^{|\{c \in \beta_1 : Q \cap c = \emptyset\}|} B^{|\{c \in \beta_2 : Q \cap c = \emptyset\}|} \\
&= \sum_{Q_1 \subseteq [\beta_1]} \sum_{Q_2 \subseteq [\beta_2]} A^{|Q_1| + |Q_2|} B^{|\{c \in \beta_1 : Q_1 \cap c = \emptyset\}|} B^{|\{c \in \beta_2 : Q_2 \cap c = \emptyset\}|} \\
&= S(\beta_1)S(\beta_2),
\end{align*}
$$
no new loop will be created although the preexisting loop containing $n$ will be
stretched by $c$, which is drawn by the blue line in Figure 6c. Third, in case

$$
|Q \cap c| = m \geq 2,
$$

suppose that

$$
Q \cap c = \{i_1, \dots, i_m\},
$$

and we connect $Q \sqcup \{n\}$ and $c$ one after another. To begin with, $i_1$ does not make
any loop as in case 2. Next, however, connection at $i_2$ gives a new loop, which will
be enclosed by the preexisting loop, increasing genus by one; see Figure 6d. This
inductive argument shows the claim on case 3.

Therefore,

$$
\#(\alpha^{-1}\beta) = 1 + \sum_{c \in \beta'} [2 \cdot 1_{Q \cap c = \emptyset} - 1 + |Q \cap c|],
$$

which leads to the formula because $Q \cap \beta(n) = \emptyset$ implies that

$$
\sum_{c \in \beta'} |Q \cap c| = |Q|.
$$

This completes the proof.

■

**Remark 3.13.** The result follows equally from the equivalence $1 \Leftrightarrow 4$ from [14, Theorem 4.4] and the equality

$$
1 + |\{c \in \beta' : Q \cap c = \emptyset\}| = \#(\alpha \tilde{\vee} \beta),
$$

where $\tilde{\vee}$ denotes the join operation in the lattice of *all* partitions.

**Lemma 3.14.** For any partition $\beta$ of order $n$, not necessarily in $NC(n)$,

$$
\sum_{Q \subseteq [n]} A^{|Q|} B^{|\{c \in \beta : Q \cap c = \emptyset\}|} = \prod_{c \in \beta} ((A+1)^{|c|} + B - 1).
$$

*Proof.* First, note that the LHS, which we denote by $S(\beta)$, is multiplicative for block decomposition in $NC(n)$. Indeed, for $\beta = \beta_1 \sqcup \beta_2$,

$$
\begin{align*}
S(\beta) &= \sum_{Q \subseteq [n]} A^{|Q|} B^{|\{c \in \beta_1 : Q \cap c = \emptyset\}|} B^{|\{c \in \beta_2 : Q \cap c = \emptyset\}|} \\
&= \sum_{Q_1 \subseteq [\beta_1]} \sum_{Q_2 \subseteq [\beta_2]} A^{|Q_1| + |Q_2|} B^{|\{c \in \beta_1 : Q_1 \cap c = \emptyset\}|} B^{|\{c \in \beta_2 : Q_2 \cap c = \emptyset\}|} \\
&= S(\beta_1) S(\beta_2),
\end{align*}
$$
where $[\beta_i]$ is the support of $\beta_i$. Clearly, the RHS is also multiplicative, so we prove the formula only for the case $\beta = 1_m$. Indeed,

$$ (\text{LHS}) = \sum_{Q \subseteq [m]} A^{|Q|} - 1 + B = (A+1)^m + B - 1 = (\text{RHS}), $$

where we treated the case $Q = \emptyset$ separately.

<figure><img src="image_9.png" /></figure>

## 4. Thin meandric systems

In this section, we consider the case where paths on both the upper and the lower sides of the coordinate line consist of interval partitions; i.e.,

$$ (\alpha, \beta) \in \text{Int}(n) \times \text{Int}(n). $$

A meandric system having, say, the top partition being an interval partition is called in [14] *shallow top*. Since such a meandric system has both a shallow top and a shallow bottom, we will call it *thin meandric system*. Since in this case there is no complicated layer structure due to non-crossing partitions, all the calculations are straightforward.

**Theorem 4.1.** For meandric systems of $\text{Int}(n) \times \text{Int}(n)$, the moment generating function $M(X, Y, A, B)$ and the cumulant generating function $K(X, Y, A, B)$ in Definition 3.7 are calculated as follows:

$$ M(X, Y, A, B) = \frac{X}{1 - X(1 + AB + (A + B)Y)} $$

and

$$ K(X, Y, A, B) = \frac{X}{1 - X(AB + (A + B)Y)}. $$

*Proof.* We compute $K(X, Y, A, B)$:

$$ \begin{align*} K(X, Y, A, B) &= \sum_{n=1}^{\infty} X^n \sum_{\substack{\alpha, \beta \in \text{Int}(n) \\ \alpha \lor \text{Int}\beta = 1_n}} Y^{\|\alpha^{-1}\beta\|} A^{\|\alpha\|} B^{\|\beta\|} \\ &= \sum_{n=1}^{\infty} X^n \sum_{\substack{\alpha, \beta \in \text{Kr Int}(n) \\ \alpha \land \text{Kr Int}\beta = 0_n}} Y^{\|\alpha^{-1}\beta\|} A^{\|\alpha^{-1} 1_n\|} B^{\|\beta^{-1} 1_n\|} \\ &= \sum_{n=1}^{\infty} X^n \sum_{\substack{Q, R \subseteq [n-1] \\ Q \cap R = \emptyset}} Y^{|Q|+|R|} A^{n-1-|Q|} B^{n-1-|R|}. \end{align*} $$
where $[\beta_i]$ is the support of $\beta_i$. Clearly, the RHS is also multiplicative, so we prove the formula only for the case $\beta = 1_m$. Indeed,

$$ (\text{LHS}) = \sum_{Q \subseteq [m]} A^{|Q|} - 1 + B = (A+1)^m + B - 1 = (\text{RHS}), $$

where we treated the case $Q = \emptyset$ separately.

## 4. Thin meandric systems

In this section, we consider the case where paths on both the upper and the lower sides of the coordinate line consist of interval partitions; i.e.,

$$ (\alpha, \beta) \in \text{Int}(n) \times \text{Int}(n). $$

A meandric system having, say, the top partition being an interval partition is called in [14] *shallow top*. Since such a meandric system has both a shallow top and a shallow bottom, we will call it *thin meandric system*. Since in this case there is no complicated layer structure due to non-crossing partitions, all the calculations are straightforward.

**Theorem 4.1.** For meandric systems of $\text{Int}(n) \times \text{Int}(n)$, the moment generating function $M(X, Y, A, B)$ and the cumulant generating function $K(X, Y, A, B)$ in Definition 3.7 are calculated as follows:

$$ M(X, Y, A, B) = \frac{X}{1 - X(1 + AB + (A + B)Y)} $$

and

$$ K(X, Y, A, B) = \frac{X}{1 - X(AB + (A + B)Y)}. $$

*Proof.* We compute $K(X, Y, A, B)$:

$$ \begin{align*} K(X, Y, A, B) &= \sum_{n=1}^{\infty} X^n \sum_{\substack{\alpha, \beta \in \text{Int}(n) \\ \alpha \lor \text{Int}\beta = 1_n}} Y^{\|\alpha^{-1}\beta\|} A^{\|\alpha\|} B^{\|\beta\|} \\ &= \sum_{n=1}^{\infty} X^n \sum_{\substack{\alpha, \beta \in \text{Kr Int}(n) \\ \alpha \land \text{Kr Int}\beta = 0_n}} Y^{\|\alpha^{-1}\beta\|} A^{\|\alpha^{-1} 1_n\|} B^{\|\beta^{-1} 1_n\|} \\ &= \sum_{n=1}^{\infty} X^n \sum_{\substack{Q, R \subseteq [n-1] \\ Q \cap R = \emptyset}} Y^{|Q|+|R|} A^{n-1-|Q|} B^{n-1-|R|}. \end{align*} $$
Here, $Q \sqcup \{n\}$ and $R \sqcup \{n\}$ are the supports of the combs (see Remark 3.10) of $\alpha$ and $\beta$, and clearly,

$$ \alpha \wedge_{\mathrm{KrInt}} \beta = 0_n \iff Q \cap R = \emptyset, $$

which also implies that

$$ \|\alpha^{-1}\beta\| = |Q| + |R|. $$

In addition, (1) and (2) explain the powers of $A$ and $B$.

Therefore,

$$ \begin{aligned} K(X, Y, A, B) &= \sum_{n=1}^{\infty} X^n \sum_{\substack{Q, R \subseteq [n-1] \\ Q \cap R = \emptyset}} (AB)^{n-1-|Q|-|R|} (AY)^{|R|} (BY)^{|Q|} \\ &= \sum_{n=1}^{\infty} X^n (AB + (A+B)Y)^{n-1} \\ &= \frac{X}{1 - X(AB + (A+B)Y)}. \end{aligned} $$

The generating function $M(X, Y, A, B)$ is obtained from $K(X, Y, A, B)$ by using Proposition 3.2:

$$ \begin{aligned} M(X, Y, A, B) &= \frac{X}{1 - X(AB + (A+B)Y)} \left[ 1 - \frac{X}{1 - X(AB + (A+B)Y)} \right]^{-1} \\ &= \frac{X}{1 - X(1 + AB + (A+B)Y)}. \end{aligned} \quad \blacksquare $$

**Corollary 4.2.** The number of thin meandric systems of order $n$ having $k$ connected components is given by

$$ 2^{n-1} \binom{n-1}{k-1}. $$

*Proof.* Set $A = B = 1$ in the above result and extract the coefficient of $X^n Y^{n-k}$:

$$ \begin{aligned} [X^n Y^{n-k}] M(X, Y) &= [X^n Y^{n-k}] \left( \frac{X}{1 - 2X(1 + Y)} \right) \\ &= [X^n Y^{n-k}] X \sum_{n=0}^{\infty} (2X(1 + Y))^n. \end{aligned} $$

This completes the proof.

<figure><img src="image_10.png" /></figure>

Notice that thin meanders (i.e., $k = 1$ above) correspond to $Q$ and $R$ forming a partition of $[n-1]$; hence, there are $2^{n-1}$ such objects.
Here, $Q \sqcup \{n\}$ and $R \sqcup \{n\}$ are the supports of the combs (see Remark 3.10) of $\alpha$ and $\beta$, and clearly,

$$ \alpha \wedge_{\mathrm{KrInt}} \beta = 0_n \iff Q \cap R = \emptyset, $$

which also implies that

$$ \|\alpha^{-1}\beta\| = |Q| + |R|. $$

In addition, (1) and (2) explain the powers of $A$ and $B$.

Therefore,

$$ \begin{aligned} K(X, Y, A, B) &= \sum_{n=1}^{\infty} X^n \sum_{\substack{Q, R \subseteq [n-1] \\ Q \cap R = \emptyset}} (AB)^{n-1-|Q|-|R|} (AY)^{|R|} (BY)^{|Q|} \\ &= \sum_{n=1}^{\infty} X^n (AB + (A+B)Y)^{n-1} \\ &= \frac{X}{1 - X(AB + (A+B)Y)}. \end{aligned} $$

The generating function $M(X, Y, A, B)$ is obtained from $K(X, Y, A, B)$ by using Proposition 3.2:

$$ \begin{aligned} M(X, Y, A, B) &= \frac{X}{1 - X(AB + (A+B)Y)} \left[ 1 - \frac{X}{1 - X(AB + (A+B)Y)} \right]^{-1} \\ &= \frac{X}{1 - X(1 + AB + (A+B)Y)}. \end{aligned} \quad \blacksquare $$

**Corollary 4.2.** The number of thin meandric systems of order $n$ having $k$ connected components is given by

$$ 2^{n-1} \binom{n-1}{k-1}. $$

*Proof.* Set $A = B = 1$ in the above result and extract the coefficient of $X^n Y^{n-k}$:

$$ \begin{aligned} [X^n Y^{n-k}] M(X, Y) &= [X^n Y^{n-k}] \left( \frac{X}{1 - 2X(1 + Y)} \right) \\ &= [X^n Y^{n-k}] X \sum_{n=0}^{\infty} (2X(1 + Y))^n. \end{aligned} $$

This completes the proof.

<figure><img src="image_9.png" /></figure>

Notice that thin meanders (i.e., $k = 1$ above) correspond to $Q$ and $R$ forming a partition of $[n-1]$; hence, there are $2^{n-1}$ such objects.
**5. Meandric systems with shallow top**

This section contains one of the main results of the paper, a generating series for the number of meandric systems with shallow top. The terminology comes from [14], where meandric systems having one partition (say, the top one) being an interval partition have been called *shallow top meanders*. It was recognized in [14] that this restricted setting allows for an explicit enumeration of meanders (meandric systems with one connected component) due to the simpler structure of the arches involved.

We derive the cumulant generating function of shallow top meandric systems and then apply the machinery from Section 3 to obtain the moment generating function. Our results generalize [14, Theorem 1.1] adding two new statistics to the generating function: the number of loops of the meandric system (counted by $Y$) and the number of cycles of the non-interval partition ($\beta$ in our notation, counted by $B$). The explicit number of loops of such meandric systems has been computed in [14].

**Theorem 5.1.** For meandric systems of $\text{Int}(n) \times \text{NC}(n)$, the Boolean cumulant generating function $K(X, Y, A, B)$ in Definition 3.7 is given by

$$K(X) = h(X(1 + \hat{g}(X))). \qquad (7)$$

Here, $\hat{g} = \mathcal{F}_{\text{free}}(g)$, and $g(x)$ and $h(x)$ are defined as

$$ \begin{aligned} g(X) &= \sum_{n=1}^{\infty} g_n X^n, \quad \text{where } g_n = BY[(1 + AY)^n + (AY)^n(Y^{-2} - 1)], \\ h(X) &= \sum_{n=1}^{\infty} h_n X^n, \quad \text{where } h_n = (AY)^{n-1}. \end{aligned} \qquad (8) $$

The generating function for shallow top meandric systems is given by

$$ M(X, Y, A, B) = \sum_{n=1}^{\infty} X^n \sum_{\substack{\alpha \in \text{Int}(n) \\ \beta \in \text{NC}(n)}} Y^{\|\alpha^{-1}\beta\|} A^{\|\alpha\|} B^{\|\beta\|} = \frac{K(X, Y, A, B)}{1 - K(X, Y, A, B)}. $$

*Proof.* Using Lemma 3.12 with the decomposition $\beta = \beta' \sqcup \beta(n)$, we have

$$ \begin{aligned} K(X, Y, A, B) &= \sum_{n=1}^{\infty} X^n \sum_{\beta \in \text{NC}(n)} \sum_{\substack{\alpha \in \text{Int}(n) \\ \alpha \wedge \text{Int} \beta = 1_n}} Y^{\|\alpha^{-1}\beta\|} A^{\|\alpha\|} B^{\|\beta\|} \\ &= \sum_{n=1}^{\infty} X^n \sum_{\beta \in \text{NC}(n)} \sum_{\substack{\alpha \in \text{Kr Int}(n) \\ \alpha \wedge \text{Kr Int} \beta = 0_n}} Y^{\|\alpha^{-1}\beta\|} A^{\|\alpha^{-1} 1_n\|} B^{\|\beta^{-1} 1_n\|} \\ &= \sum_{n=1}^{\infty} X^n \sum_{\beta \in \text{NC}(n)} \sum_{Q \subseteq [\beta'] \atop Q \subseteq [\beta'] } Y^{n-2 \cdot \{c \in \beta' : Q \cap c = \emptyset\} - 1 + \#(\beta') - |Q|} A^{n-1 - |Q|} B^{\#(\beta')} \end{aligned} $$
## 5. Meandric systems with shallow top

This section contains one of the main results of the paper, a generating series for the number of meandric systems with shallow top. The terminology comes from [14], where meandric systems having one partition (say, the top one) being an interval partition have been called *shallow top meanders*. It was recognized in [14] that this restricted setting allows for an explicit enumeration of meanders (meandric systems with one connected component) due to the simpler structure of the arches involved.

We derive the cumulant generating function of shallow top meandric systems and then apply the machinery from Section 3 to obtain the moment generating function. Our results generalize [14, Theorem 1.1] adding two new statistics to the generating function: the number of loops of the meandric system (counted by $Y$) and the number of cycles of the non-interval partition ($\beta$ in our notation, counted by $B$). The explicit number of loops of such meandric systems has been computed in [14].

**Theorem 5.1.** For meandric systems of $\text{Int}(n) \times \text{NC}(n)$, the Boolean cumulant generating function $K(X, Y, A, B)$ in Definition 3.7 is given by

$$K(X) = h(X(1 + \hat{g}(X))). \qquad (7)$$

Here, $\hat{g} = \mathcal{F}_{\text{free}}(g)$, and $g(x)$ and $h(x)$ are defined as

$$ \begin{aligned} g(X) &= \sum_{n=1}^{\infty} g_n X^n, \quad \text{where } g_n = BY[(1 + AY)^n + (AY)^n (Y^{-2} - 1)], \\ h(X) &= \sum_{n=1}^{\infty} h_n X^n, \quad \text{where } h_n = (AY)^{n-1}. \end{aligned} \qquad (8) $$

The generating function for shallow top meandric systems is given by

$$ M(X, Y, A, B) = \sum_{n=1}^{\infty} X^n \sum_{\substack{\alpha \in \text{Int}(n) \\ \beta \in \text{NC}(n)}} Y^{\|\alpha^{-1}\beta\|} A^{\|\alpha\|} B^{\|\beta\|} = \frac{K(X, Y, A, B)}{1 - K(X, Y, A, B)}. $$

*Proof.* Using Lemma 3.12 with the decomposition $\beta = \beta' \sqcup \beta(n)$, we have

$$ \begin{aligned} K(X, Y, A, B) &= \sum_{n=1}^{\infty} X^n \sum_{\beta \in \text{NC}(n)} \sum_{\substack{\alpha \in \text{Int}(n) \\ \alpha \wedge \text{Int}\beta = 1_n}} Y^{\|\alpha^{-1}\beta\|} A^{\|\alpha\|} B^{\|\beta\|} \\ &= \sum_{n=1}^{\infty} X^n \sum_{\beta \in \text{NC}(n)} \sum_{\substack{\alpha \in \text{KrInt}(n) \\ \alpha \wedge \text{KrInt}\beta = 0_n}} Y^{\|\alpha^{-1}\beta\|} A^{\|\alpha^{-1}1_n\|} B^{\|\beta^{-1}1_n\|} \\ &= \sum_{n=1}^{\infty} X^n \sum_{\beta \in \text{NC}(n)} \sum_{Q \subseteq [\beta'] \atop Q \subseteq [\beta]} Y^{n-2 \cdot \{c \in \beta' : Q \cap c = \emptyset\} - 1 + \#(\beta') - |Q|} A^{n-1 - |Q|} B^{\#(\beta')} \end{aligned} $$
Here, $[\beta']$ is the support of $\beta'$ and $Q = Q_\alpha$, and

$$ \|\beta^{-1}1_n\| = n - 1 - \|\beta\| = n - 1 - (n - \#(\beta)) = \#(\beta'). $$

Moreover, we used the fact that

$$ \alpha \wedge_{\mathrm{KrInt}} \beta = 0_n \iff Q \cap \beta(n) = \emptyset. $$

Then, we continue our calculation with Lemma 3.14:

$$
\begin{align*}
K(X, Y, A, B) \\
&= \sum_{n=1}^{\infty} X^n \sum_{\beta \in \mathrm{NC}(n)} (AY)^{n-1} (BY)^{\#(\beta')} \sum_{Q \subseteq [\beta']} (A^{-1}Y^{-1})^{|Q|} (Y^{-2})^{|\{c \in \beta' : Q \cap c = \emptyset\}|} \\
&= \sum_{n=1}^{\infty} X^n \sum_{\beta \in \mathrm{NC}(n)} (AY)^{|\beta'| + |\beta(n)| - 1} (BY)^{\#(\beta')} \prod_{c \in \beta'} [(A^{-1}Y^{-1} + 1)^{|c|} + Y^{-2} - 1] \\
&= \sum_{n=1}^{\infty} X^n \sum_{\beta \in \mathrm{NC}(n)} (AY)^{|\beta(n)| - 1} \prod_{c \in \beta'} BY[(1 + AY)^{|c|} + (AY)^{|c|}(Y^{-2} - 1)].
\end{align*}
$$

Therefore, using the definition (8) and Lemma 3.3, we calculate

$$ K(X, Y, A, B) = \sum_{n=1}^{\infty} X^n \sum_{\beta \in \mathrm{NC}(n)} h_{|\beta(n)|} \prod_{c \in \beta'} g_{|c|} = \sum_{s=1}^{\infty} h_s X^s \left( 1 + \sum_{i=1}^{\infty} \hat{g}_i X^i \right)^s, $$

where $\mathcal{F}_{\mathrm{free}} : g \mapsto \hat{g}$ is the free transform. This completes the proof. $\blacksquare$

<figure><img src="image_11.png" /></figure>

Note that the Boolean cumulant generating function $K$ from (7) is not quite explicit due to the definition of the function $\hat{g}$, which is given implicitly through its free transform $\mathcal{F}_{\mathrm{free}}$. Solving for $\hat{g}$ explicitly requires inverting a function, which cannot be done in full generality. Our theorem has the theoretical interest of expressing the moment generating function of the shallow top meandric systems with the help of the functional transforms associated to the type of lattices, the top, respectively, the bottom, partitions belong to. Moreover, one can use the implicit formulas from Theorem 5.1 to extract useful information regarding the enumeration of shallow top meandric systems. For example, the main result of [14] states that the number of shallow top meanders on $2n$ points with $m$ blocks on the bottom is the LHS of the identity

$$ \frac{1}{n} \binom{n}{m-1} \binom{n+m-1}{m-1} = [X^n Y^{n-1} A^{n-m}] M(X, Y, A, 1). $$

We could not recover the LHS from the RHS, which is ours, while the identity itself is true.
Here, $[\beta']$ is the support of $\beta'$ and $Q = Q_\alpha$, and

$$ \|\beta^{-1} 1_n\| = n - 1 - \|\beta\| = n - 1 - (n - \#(\beta)) = \#(\beta'). $$

Moreover, we used the fact that

$$ \alpha \wedge_{\mathrm{KrInt}} \beta = 0_n \iff Q \cap \beta(n) = \emptyset. $$

Then, we continue our calculation with Lemma 3.14:

$$
\begin{align*}
K(X, Y, A, B) \\
&= \sum_{n=1}^{\infty} X^n \sum_{\beta \in \mathrm{NC}(n)} (AY)^{n-1} (BY)^{\#(\beta')} \sum_{Q \subseteq [\beta'] \atop Q \subseteq [\beta':Q \cap c=\emptyset]} (A^{-1}Y^{-1})^{|Q|} (Y^{-2})^{|c \in \beta':Q \cap c=\emptyset|} \\
&= \sum_{n=1}^{\infty} X^n \sum_{\beta \in \mathrm{NC}(n)} (AY)^{|\beta'|+|\beta(n)|-1} (BY)^{\#(\beta')} \prod_{c \in \beta'} [(A^{-1}Y^{-1} + 1)^{|c|} + Y^{-2} - 1] \\
&= \sum_{n=1}^{\infty} X^n \sum_{\beta \in \mathrm{NC}(n)} (AY)^{|\beta(n)|-1} \prod_{c \in \beta'} BY[(1 + AY)^{|c|} + (AY)^{|c|}(Y^{-2} - 1)].
\end{align*}
$$

Therefore, using the definition (8) and Lemma 3.3, we calculate

$$ K(X, Y, A, B) = \sum_{n=1}^{\infty} X^n \sum_{\beta \in \mathrm{NC}(n)} h_{|\beta(n)|} \prod_{c \in \beta'} g_{|c|} = \sum_{s=1}^{\infty} h_s X^s \left( 1 + \sum_{i=1}^{\infty} \hat{g}_i X^i \right)^s, $$

where $\mathcal{F}_{\mathrm{free}}: g \mapsto \hat{g}$ is the free transform. This completes the proof. $\blacksquare$

<figure><img src="image_10.png" /></figure>

Note that the Boolean cumulant generating function $K$ from (7) is not quite explicit due to the definition of the function $\hat{g}$, which is given implicitly through its free transform $\mathcal{F}_{\mathrm{free}}$. Solving for $\hat{g}$ explicitly requires inverting a function, which cannot be done in full generality. Our theorem has the theoretical interest of expressing the moment generating function of the shallow top meandric systems with the help of the functional transforms associated to the type of lattices, the top, respectively, the bottom, partitions belong to. Moreover, one can use the implicit formulas from Theorem 5.1 to extract useful information regarding the enumeration of shallow top meandric systems. For example, the main result of [14] states that the number of shallow top meanders on $2n$ points with $m$ blocks on the bottom is the LHS of the identity

$$ \frac{1}{n} \binom{n}{m-1} \binom{n+m-1}{m-1} = [X^n Y^{n-1} A^{n-m}] M(X, Y, A, 1). $$

We could not recover the LHS from the RHS, which is ours, while the identity itself is true.
<figure><img src="image_12.png" /><figcaption>Figure 7. Examples for the rainbow partition $\beta_{\text{rainbow}}$ when $n = 6, 7$ and its Kreweras complement.</figcaption></figure>

## 6. Shallow top semi-meandric systems

In this section, we consider shallow top semi-meandric systems: meandric systems formed by an interval partition and the so-called *rainbow partition*, which is defined as follows:

$$ \beta_{\text{rainbow}} = \begin{cases} (1, n)(2, n-1)\cdots(\frac{n}{2}, \frac{n}{2}+1) & (n \text{ is even}), \\ (1, n)(2, n-1)\cdots(\frac{n+1}{2}) & (n \text{ is odd}). \end{cases} $$

The terminology is justified by the fact that meandric systems with one of the partitions (say, the bottom one) is fixed to be the rainbow partition are called semi-meandric systems [9]. We further specialize this setting by considering interval partitions on the top.

One can find graphical representations of rainbow partitions (as well as their Kreweras complements) in Figure 7. By using the decomposition in (3), we can write

$$ \beta_{\text{rainbow}}^{\text{Kr}} = (\beta_{\text{rainbow}}^{\text{Kr}})' \sqcup \beta_{\text{rainbow}}^{\text{Kr}}(n). \quad (9) $$

It always holds that

$$ \beta_{\text{rainbow}}^{\text{Kr}}(n) = \{n\}, $$

and $(\beta_{\text{rainbow}}^{\text{Kr}})' \in \text{NC}(n-1)$ is a rainbow partition. Moreover, all cycles in $(\beta_{\text{rainbow}}^{\text{Kr}})'$ are of length 2, unless $n$ is even, when only one exceptional cycle consists of a single point: $\{n/2\}$.

Note that the definition of the moment generating function in Definition 3.7 can be naturally extended to the current case, so we can state and prove the main result of this section.

**Theorem 6.1.** The generating function of shallow top semi-meandric systems $M(X, Y, A)$ defined by $\text{Int}(n) \times \{\beta_{\text{rainbow}}\}$ is given by

$$ M(X, Y, A) := M(X, Y, A, 1) = \frac{X + X^2(Y + A)}{1 - X^2Y(1 + 2YA + A^2)}. \quad (10) $$
<figure><img src="image_11.png" /><figcaption>**Figure 7.** Examples for the rainbow partition $\beta_{\text{rainbow}}$ when $n = 6, 7$ and its Kreweras complement.</figcaption></figure>

## 6. Shallow top semi-meandric systems

In this section, we consider *shallow top semi-meandric systems*: meandric systems formed by an interval partition and the so-called *rainbow partition*, which is defined as follows:

$$ \beta_{\text{rainbow}} = \begin{cases} (1, n)(2, n-1)\cdots(\frac{n}{2}, \frac{n}{2}+1) & (n \text{ is even}), \\ (1, n)(2, n-1)\cdots(\frac{n+1}{2}) & (n \text{ is odd}). \end{cases} $$

The terminology is justified by the fact that meandric systems with one of the partitions (say, the bottom one) is fixed to be the rainbow partition are called semi-meandric systems [9]. We further specialize this setting by considering interval partitions on the top.

One can find graphical representations of rainbow partitions (as well as their Kreweras complements) in Figure 7. By using the decomposition in (3), we can write

$$ \beta_{\text{rainbow}}^{\text{Kr}} = (\beta_{\text{rainbow}}^{\text{Kr}})' \sqcup \beta_{\text{rainbow}}^{\text{Kr}}(n). \quad (9) $$

It always holds that

$$ \beta_{\text{rainbow}}^{\text{Kr}}(n) = \{n\}, $$

and $(\beta_{\text{rainbow}}^{\text{Kr}})' \in \text{NC}(n-1)$ is a rainbow partition. Moreover, all cycles in $(\beta_{\text{rainbow}}^{\text{Kr}})'$ are of length 2, unless $n$ is even, when only one exceptional cycle consists of a single point: $\{n/2\}$.

Note that the definition of the moment generating function in Definition 3.7 can be naturally extended to the current case, so we can state and prove the main result of this section.

**Theorem 6.1.** *The generating function of shallow top semi-meandric systems $M(X, Y, A)$ defined by $\text{Int}(n) \times \{\beta_{\text{rainbow}}\}$ is given by*

$$ M(X, Y, A) := M(X, Y, A, 1) = \frac{X + X^2(Y + A)}{1 - X^2Y(1 + 2YA + A^2)}. \quad (10) $$
*Proof.* In this proof, we treat our problem in the Kreweras-complement view but do not use the cumulant generating function. First, by writing

$$ \beta := \beta_{\text{rainbow}}^{\text{Kr}}, $$

we have

$$ \begin{aligned} M(X, Y, A) &= \sum_{n=1}^{\infty} X^n \sum_{\alpha \in \text{Int}(n)} Y^{\|\alpha^{-1}\beta_{\text{rainbow}}\|} A^{\|\alpha\|} \\ &= \sum_{n=1}^{\infty} X^n \sum_{\substack{\alpha \in \text{Kr Int}(n) \\ \alpha \wedge \text{Kr Int} \beta = 0_n}} Y^{\|\alpha^{-1}\beta\|} A^{\|\alpha^{-1} 1_n\|}, \end{aligned} $$

where we used Proposition 2.2. We claim that the condition $\alpha \wedge_{\text{Kr Int}} \beta = 0_n$ always holds in this case. Indeed, as in Remark 3.10, $\alpha \in \text{Kr Int}(n)$ consists of isolated points and possibly at most one non-trivial cycle containing $n$. On the other hand, we see from (9) and Figure 7 that $\{n\}$ is always an isolated point in $\beta$. Hence, Definition 3.4 implies that the meet of the two partitions inside the lattice $\text{Kr Int}(n)$ is trivial.

Next, we apply Lemma 3.12 to $\text{NC}(n)$ and then Lemma 3.14 to $\text{NC}(n-1)$:

$$ \begin{aligned} M(X, Y, A) &= \sum_{n=1}^{\infty} X^n \sum_{Q \subseteq [n-1]} Y^{n-2 \cdot |\{c \in \beta': Q \cap c = \emptyset\}| - 1 + \lfloor \frac{n}{2} \rfloor - |Q|} A^{n-1 - |Q|} \\ &= \sum_{n=1}^{\infty} X^n Y^{n-1 + \lfloor \frac{n}{2} \rfloor} A^{n-1} \sum_{Q \subseteq [n-1]} (Y^{-2})^{|\{c \in \beta': Q \cap c = \emptyset\}|} ((YA)^{-1})^{|Q|} \\ &= \sum_{n=1}^{\infty} X^n (YA)^{n-1} Y^{\lfloor \frac{n}{2} \rfloor} \underbrace{\prod_{c \in \beta'} (( (YA)^{-1} + 1 )^{|c|} + Y^{-2} - 1 )}_{(\star)} . \end{aligned} $$

Moreover, recall that the cycles of $\beta'$ are all pairs, except for the case when $n$ is even, where we have an extra singleton. Hence, we can make $(\star)$ explicit:

$$ (\star) = ((YA)^{-2} + 2(YA)^{-1} + Y^{-2})^{\lfloor \frac{n}{2} \rfloor - e(n)} ((YA)^{-1} + Y^{-2})^{e(n)}, $$

where

$$ e(n) = \begin{cases} 1, & n \text{ is even}, \\ 0, & n \text{ is odd}. \end{cases} $$

Here, note that

$$ 2(\lfloor \frac{n}{2} \rfloor - e(n)) + e(n) = n - 1, $$

which is the number of points in $\beta'$.
*Proof.* In this proof, we treat our problem in the Kreweras-complement view but do not use the cumulant generating function. First, by writing

$$ \beta := \beta_{\text{rainbow}}^{\text{Kr}}, $$

we have

$$ \begin{aligned} M(X, Y, A) &= \sum_{n=1}^{\infty} X^n \sum_{\alpha \in \text{Int}(n)} Y^{\|\alpha^{-1}\beta_{\text{rainbow}}\|} A^{\|\alpha\|} \\ &= \sum_{n=1}^{\infty} X^n \sum_{\substack{\alpha \in \text{Kr Int}(n) \\ \alpha \wedge \text{Kr Int} \beta = 0_n}} Y^{\|\alpha^{-1}\beta\|} A^{\|\alpha^{-1} 1_n\|}, \end{aligned} $$

where we used Proposition 2.2. We claim that the condition $\alpha \wedge_{\text{Kr Int}} \beta = 0_n$ always holds in this case. Indeed, as in Remark 3.10, $\alpha \in \text{Kr Int}(n)$ consists of isolated points and possibly at most one non-trivial cycle containing $n$. On the other hand, we see from (9) and Figure 7 that $\{n\}$ is always an isolated point in $\beta$. Hence, Definition 3.4 implies that the meet of the two partitions inside the lattice $\text{Kr Int}(n)$ is trivial.

Next, we apply Lemma 3.12 to $\text{NC}(n)$ and then Lemma 3.14 to $\text{NC}(n-1)$:

$$ \begin{aligned} M(X, Y, A) &= \sum_{n=1}^{\infty} X^n \sum_{Q \subseteq [n-1]} Y^{n-2 \cdot |\{c \in \beta': Q \cap c = \emptyset\}| - 1 + \lfloor \frac{n}{2} \rfloor - |Q|} A^{n-1 - |Q|} \\ &= \sum_{n=1}^{\infty} X^n Y^{n-1 + \lfloor \frac{n}{2} \rfloor} A^{n-1} \sum_{Q \subseteq [n-1]} (Y^{-2})^{|\{c \in \beta': Q \cap c = \emptyset\}|} ((YA)^{-1})^{|Q|} \\ &= \sum_{n=1}^{\infty} X^n (YA)^{n-1} Y^{\lfloor \frac{n}{2} \rfloor} \underbrace{\prod_{c \in \beta'} (( (YA)^{-1} + 1)^{|c|} + Y^{-2} - 1 )}_{(\star)} . \end{aligned} $$

Moreover, recall that the cycles of $\beta'$ are all pairs, except for the case when $n$ is even, where we have an extra singleton. Hence, we can make $(\star)$ explicit:

$$ (\star) = ((YA)^{-2} + 2(YA)^{-1} + Y^{-2})^{\lfloor \frac{n}{2} \rfloor - e(n)} ((YA)^{-1} + Y^{-2})^{e(n)}, $$

where

$$ e(n) = \begin{cases} 1, & n \text{ is even,} \\ 0, & n \text{ is odd.} \end{cases} $$

Here, note that

$$ 2(\lfloor \frac{n}{2} \rfloor - e(n)) + e(n) = n - 1, $$

which is the number of points in $\beta'$.
Finally, dividing the series into two parts depending on the parity of $n$, we have

$$
\begin{aligned}
M(X, Y, A) &= \sum_{n=1}^{\infty} X^n [Y(1 + 2YA + A^2)]^{\lfloor \frac{n}{2} \rfloor - e(n)} (Y + A)^{e(n)} \\
&= X \sum_{m=0}^{\infty} [X^2Y(1 + 2YA + A^2)]^m \\
&\quad + X^2(Y + A) \sum_{m=0}^{\infty} [X^2Y(1 + 2YA + A^2)]^m \\
&= \frac{X + X^2(Y + A)}{1 - X^2Y(1 + 2YA + A^2)}.
\end{aligned}
$$

This completes the proof.

<figure><img src="image_13.png" /></figure>

**Remark 6.2.** It is straightforward to extract the distribution of the number of loops at fixed $n$ from (10):

$$
\forall n \ge 1, \quad [X^n]M(X, Y, 1) = \begin{cases} (2Y)^{k-1}(Y+1)^k & \text{if } n = 2k, \\ (2Y(Y+1))^{k-1} & \text{if } n = 2k-1. \end{cases}
$$

In particular, the number of shallow top semi-meanders is the coefficient of $X^n Y^{n-1}$ in $M(X, Y, 1)$, which is $2^{\lfloor n/2 \rfloor - 1}$. Note that this number can also be computed directly.

7. Random matrix models for meandric systems

We present in this section several matrix models for the different types of meandric
systems that we study. These models are motivated by quantum information theory,
and they allow for a uniform presentation, the matrix model being constructed from a
tensor product of two (random) completely positive maps related, respectively, to the
type of non-crossing partitions used to build the meander.

Let us introduce basic definitions in quantum information theory as far as we need.
First, a matrix $\rho \in \mathcal{M}_d(\mathbb{C})$ is called a *quantum state* if it is positive semi-definite and
has unit trace so that the eigenvalues give a probability distribution. Bell states are
notable quantum states showing non-classical features. An un-normalized Bell state
can be written as

$$
\omega_d = \Omega_d \Omega_d^* \in \mathcal{M}_{d^2}(\mathbb{C}),
$$

where $\Omega_d$ is a vector in $\mathbb{C}^d \otimes \mathbb{C}^d$:

$$
\Omega_d = \sum_{i=1}^{d} e_i \otimes e_i \in \mathbb{C}^d \otimes \mathbb{C}^d,
$$
Finally, dividing the series into two parts depending on the parity of $n$, we have

$$
\begin{align*}
M(X, Y, A) &= \sum_{n=1}^{\infty} X^n [Y(1 + 2YA + A^2)]^{\lfloor \frac{n}{2} \rfloor - e(n)} (Y + A)^{e(n)} \\
&= X \sum_{m=0}^{\infty} [X^2Y(1 + 2YA + A^2)]^m \\
&\qquad + X^2(Y + A) \sum_{m=0}^{\infty} [X^2Y(1 + 2YA + A^2)]^m \\
&= \frac{X + X^2(Y + A)}{1 - X^2Y(1 + 2YA + A^2)}.
\end{align*}
$$

This completes the proof.

<figure><img src="image_12.png" /></figure>

**Remark 6.2.** It is straightforward to extract the distribution of the number of loops at fixed $n$ from (10):

$$
\forall n \ge 1, \quad [X^n] M(X, Y, 1) = \begin{cases} (2Y)^{k-1}(Y+1)^k & \text{if } n = 2k, \\ (2Y(Y+1))^{k-1} & \text{if } n = 2k-1. \end{cases}
$$

In particular, the number of shallow top semi-meanders is the coefficient of $X^n Y^{n-1}$ in $M(X, Y, 1)$, which is $2^{\lfloor n/2 \rfloor - 1}$. Note that this number can also be computed directly.

**7. Random matrix models for meandric systems**

We present in this section several matrix models for the different types of meandric
systems that we study. These models are motivated by quantum information theory,
and they allow for a uniform presentation, the matrix model being constructed from a
tensor product of two (random) completely positive maps related, respectively, to the
type of non-crossing partitions used to build the meander.

Let us introduce basic definitions in quantum information theory as far as we need.
First, a matrix $\rho \in \mathcal{M}_d(\mathbb{C})$ is called a *quantum state* if it is positive semi-definite and
has unit trace so that the eigenvalues give a probability distribution. Bell states are
notable quantum states showing non-classical features. An un-normalized Bell state
can be written as

$$
\omega_d = \Omega_d \Omega_d^* \in \mathcal{M}_{d^2}(\mathbb{C}),
$$

where $\Omega_d$ is a vector in $\mathbb{C}^d \otimes \mathbb{C}^d$:

$$
\Omega_d = \sum_{i=1}^{d} e_i \otimes e_i \in \mathbb{C}^d \otimes \mathbb{C}^d,
$$
where {$e_i$}$_{i=1}^d$ is the canonical basis for $\mathbb{C}^d$. Note that $\omega_d$ is a rank-one projection onto the subspace spanned by $\Omega_d$. Next, a linear map $\Phi: M_d(\mathbb{C}) \to M_{d'}(\mathbb{C})$ is called a *quantum channel* if it is completely positive (CP) and trace preserving. The CP condition is that $\Phi \otimes \text{id}_{d''}$ is positive for any $d'' \in \mathbb{N}$ [25, Section 2.2]. Here, $\text{id}_{d''}$ is the identity map on $M_{d''}(\mathbb{C})$. We require complete positivity rather than positivity because quantum channels should preserve positivity in arbitrarily larger systems. According to the Stinespring dilation theorem [23] from operator theory, any CP map $\Phi: M_d(\mathbb{C}) \to M_{d'}(\mathbb{C})$ can be written as

$$ \Phi_A(X) = [\text{id}_{d'} \otimes \text{Tr}_s](AXA^*) $$

for some operator $A: \mathbb{C}^d \to \mathbb{C}^{d'} \otimes \mathbb{C}^s$. Here, $\text{Tr}_s$ is the trace operation on $M_s(\mathbb{C})$. Note that taking $s = dd'$ allows one to recover all CP maps by varying $A$. Moreover, if $A$ is an isometry, $\Phi_A$ is also trace preserving yielding a quantum channel; all quantum channels can be written as $\Phi_A$ [25, Corollary 2.27].

## 7.1. Meanders

We start with the case of usual meanders and meandric systems, obtained by stacking two general non-crossing partitions one on top of the other. We will first state two models from the literature and then introduce a new, simpler one, which will be generalized in later subsections to different types of meandric systems.

Let us define the *meander polynomial*

$$ m_n(l) = \sum_{\alpha, \beta \in NC(n)} l^{\#(\alpha^{-1}\beta)}, $$

where $\alpha, \beta$ are the non-crossing partitions used to build the meandric system having $\#(\alpha^{-1}\beta)$ loops (or connected components). Note that $m_n$ can be related to the coefficient of $X^n$ of the following polynomial $M$ (similar to the one in (4); see also [12, Section 5]), evaluated at $A = B = 1$:

$$ M(X, Y, A, B) = \sum_{n=1}^{\infty} X^n \sum_{\alpha, \beta \in NC(n)} Y^{\|\alpha^{-1}\beta\|} A^{\|\alpha\|} B^{\|\beta\|}. \quad (11) $$

The first matrix models for meandric systems are due to P. Di Francesco and collaborators; see [9, Section 5] or [8, Section 6]. We recall here, for the sake of comparison with our new models, the GUE-based construction from the former reference. A *Ginibre random matrix G* is a matrix having independent and identically distributed (i.i.d.) entries $G_{ij}$ following a standard complex Gaussian distribution; a Ginibre random matrix can be rectangular, and we do not assume any symmetry properties for it.
where {$e_i$}$_{i=1}^d$ is the canonical basis for $\mathbb{C}^d$. Note that $\omega_d$ is a rank-one projection onto the subspace spanned by $\Omega_d$. Next, a linear map $\Phi: M_d(\mathbb{C}) \to M_{d'}(\mathbb{C})$ is called a *quantum channel* if it is completely positive (CP) and trace preserving. The CP condition is that $\Phi \otimes \text{id}_{d''}$ is positive for any $d'' \in \mathbb{N}$ [25, Section 2.2]. Here, $\text{id}_{d''}$ is the identity map on $M_{d''}(\mathbb{C})$. We require complete positivity rather than positivity because quantum channels should preserve positivity in arbitrarily larger systems. According to the Stinespring dilation theorem [23] from operator theory, any CP map $\Phi: M_d(\mathbb{C}) \to M_{d'}(\mathbb{C})$ can be written as

$$ \Phi_A(X) = [\text{id}_{d'} \otimes \text{Tr}_S](AXA^*) $$

for some operator $A: \mathbb{C}^d \to \mathbb{C}^{d'} \otimes \mathbb{C}^s$. Here, $\text{Tr}_s$ is the trace operation on $M_s(\mathbb{C})$. Note that taking $s = dd'$ allows one to recover all CP maps by varying $A$. Moreover, if $A$ is an isometry, $\Phi_A$ is also trace preserving yielding a quantum channel; all quantum channels can be written as $\Phi_A$ [25, Corollary 2.27].

## 7.1. Meanders

We start with the case of usual meanders and meandric systems, obtained by stacking two general non-crossing partitions one on top of the other. We will first state two models from the literature and then introduce a new, simpler one, which will be generalized in later subsections to different types of meandric systems.

Let us define the *meander polynomial*

$$ m_n(l) = \sum_{\alpha, \beta \in NC(n)} l^{\#(\alpha^{-1}\beta)}, $$

where $\alpha, \beta$ are the non-crossing partitions used to build the meandric system having $\#(\alpha^{-1}\beta)$ loops (or connected components). Note that $m_n$ can be related to the coefficient of $X^n$ of the following polynomial $M$ (similar to the one in (4); see also [12, Section 5]), evaluated at $A = B = 1$:

$$ M(X, Y, A, B) = \sum_{n=1}^{\infty} X^n \sum_{\alpha, \beta \in NC(n)} Y^{\|\alpha^{-1}\beta\|} A^{\|\alpha\|} B^{\|\beta\|}. \quad (11) $$

The first matrix models for meandric systems are due to P. Di Francesco and collaborators; see [9, Section 5] or [8, Section 6]. We recall here, for the sake of comparison with our new models, the GUE-based construction from the former reference. A *Ginibre random matrix G* is a matrix having independent and identically distributed (i.i.d.) entries $G_{ij}$ following a standard complex Gaussian distribution; a Ginibre random matrix can be rectangular, and we do not assume any symmetry properties for it.
Define now a GUE (Gaussian Unitary Ensemble) random matrix

$$B = \frac{G + G^*}{\sqrt{2}} \in \mathcal{M}_d(\mathbb{C}),$$

where $G$ is a $d \times d$ Ginibre matrix. Note that the GUE matrix defined above is not normalized in the usual way; see [2, Chapter 2] or [18, Chapter 1].

**Proposition 7.1** ([9, Section 5]). Let $\ell$ be a fixed positive integer, and consider

$$B_1, \dots, B_\ell \in \mathcal{M}_d(\mathbb{C})$$

i.i.d. GUE matrices. Then, for all $n \ge 1$,

$$m_n(\ell) = \lim_{d \to \infty} \mathbb{E} \frac{1}{d^2} \mathrm{Tr} \left( \sum_{i=1}^{\ell} \frac{B_i \otimes \bar{B}_i}{d} \right)^{2n}.$$

A second matrix model for meanders was discovered in relation to the theory of quantum information, more precisely in the study of partial transposition of random quantum states. We recall briefly the setup here. A *Wishart random matrix* of parameters $(d, s)$ is simply defined by $W = GG^*$, where $G \in \mathcal{M}_{d \times s}(\mathbb{C})$ is a Ginibre matrix. Note that $W$ is by definition a positive semi-definite matrix, and thus, its normalized version $\rho = W/\mathrm{Tr} W$ is called a *density matrix* or a *quantum state* in quantum theory [25]. This model for random density matrices was introduced in [26], and it is called the *induced measure* of parameters $(d, s)$. For bipartite quantum states

$$\rho \in \mathcal{M}_{d^2}(\mathbb{C}) = \mathcal{M}_d(\mathbb{C}) \otimes \mathcal{M}_d(\mathbb{C}),$$

the *partial transposition* operation

$$\rho^{\Gamma} := [\mathrm{id}_d \otimes \mathrm{transp}_d](\rho)$$

plays a crucial role in quantum information theory, in relation to the notion of entanglement [15]. Before stating the result from [13], let us also mention that the combinatorics of meanders appears also in computations related to random quantum channels; see [11, Section 6.2].

**Proposition 7.2** ([13, Theorem 4.2]). Let $\rho \in \mathcal{M}_{d^2}(\mathbb{C})$ be a random bi-partite quantum state of parameters $(d^2, \ell)$ for some fixed integer $\ell \ge 1$. Then, for all $n \ge 1$,

$$m_n(\ell) = \lim_{d \to \infty} \mathbb{E} \frac{1}{d^2} \mathrm{Tr}(\ell d \rho^{\Gamma})^{2n}.$$

We would like to introduce now a new, simpler matrix model for meandric systems, which we will later generalize to include different types of non-crossing partitions.
Define now a GUE (Gaussian Unitary Ensemble) random matrix

$$B = \frac{G + G^*}{\sqrt{2}} \in \mathcal{M}_d(\mathbb{C}),$$

where $G$ is a $d \times d$ Ginibre matrix. Note that the GUE matrix defined above is not normalized in the usual way; see [2, Chapter 2] or [18, Chapter 1].

**Proposition 7.1** ([9, Section 5]). Let $\ell$ be a fixed positive integer, and consider

$$B_1, \dots, B_\ell \in \mathcal{M}_d(\mathbb{C})$$

i.i.d. GUE matrices. Then, for all $n \ge 1$,

$$m_n(\ell) = \lim_{d \to \infty} \mathbb{E} \frac{1}{d^2} \mathrm{Tr} \left( \sum_{i=1}^{\ell} \frac{B_i \otimes \bar{B}_i}{d} \right)^{2n}.$$

A second matrix model for meanders was discovered in relation to the theory of quantum information, more precisely in the study of partial transposition of random quantum states. We recall briefly the setup here. A *Wishart random matrix* of parameters $(d, s)$ is simply defined by $W = GG^*$, where $G \in \mathcal{M}_{d \times s}(\mathbb{C})$ is a Ginibre matrix. Note that $W$ is by definition a positive semi-definite matrix, and thus, its normalized version $\rho = W/\mathrm{Tr} W$ is called a *density matrix* or a *quantum state* in quantum theory [25]. This model for random density matrices was introduced in [26], and it is called the *induced measure* of parameters $(d, s)$. For bipartite quantum states

$$\rho \in \mathcal{M}_{d^2}(\mathbb{C}) = \mathcal{M}_d(\mathbb{C}) \otimes \mathcal{M}_d(\mathbb{C}),$$

the *partial transposition* operation

$$\rho^{\Gamma} := [\mathrm{id}_d \otimes \mathrm{transp}_d](\rho)$$

plays a crucial role in quantum information theory, in relation to the notion of entanglement [15]. Before stating the result from [13], let us also mention that the combinatorics of meanders appears also in computations related to random quantum channels; see [11, Section 6.2].

**Proposition 7.2** ([13, Theorem 4.2]). Let $\rho \in \mathcal{M}_{d^2}(\mathbb{C})$ be a random bi-partite quantum state of parameters $(d^2, \ell)$ for some fixed integer $\ell \ge 1$. Then, for all $n \ge 1$,

$$m_n(\ell) = \lim_{d \to \infty} \mathbb{E} \frac{1}{d^2} \mathrm{Tr}(\ell d \rho^{\Gamma})^{2n}.$$

We would like to introduce now a new, simpler matrix model for meandric systems, which we will later generalize to include different types of non-crossing partitions.
<figure><img src="image_14.png" /><figcaption>**Figure 8.** A graphical representation of the bi-partite matrix $Z = [\Phi_G \otimes \Phi_H](\omega_\ell)$. Round labels represent the space $\mathbb{C}^d$, while square labels represent $\mathbb{C}^\ell$.</figcaption></figure>

**Theorem 7.3.** Consider two independent Ginibre matrices $G, H \in \mathcal{M}_{d2 \times \ell}(\mathbb{C})$ and the corresponding CP maps $\Phi_{G,H} : \mathcal{M}_\ell(\mathbb{C}) \to \mathcal{M}_d(\mathbb{C})$. Define

$$Z := [\Phi_G \otimes \Phi_H](\omega_\ell) \in \mathcal{M}_{d2}(\mathbb{C}).$$

Then, for all $n \ge 1$,

$$m_n(\ell) = \lim_{d \to \infty} \mathbb{E} \frac{1}{d^2} \mathrm{Tr} \left( \frac{Z}{d^2} \right)^n.$$

*Proof.* The statement is a moment computation which is quite standard in the theory of random matrices. We give a proof using the graphical version of Wick's formula developed in [7]. The diagram corresponding to the matrix $Z$ is depicted in Figure 8.

To compute the $n$-th moment of $Z$, $\mathbb{E} \mathrm{Tr} Z^n$, one considers the expectation value of the trace of the concatenation of $n$ instances of the diagram in Figure 8. This expectation value is, according to the graphical Wick formula [7, Theorem 3.2], a combinatorial sum indexed by two permutations $\alpha, \beta \in S_n$ of diagrams $\mathcal{D}_{\alpha,\beta}$. Note that we have here two (independent) permutations since we are dealing with independent Gaussian matrices $G$ and $H$: the permutation $\alpha$ is encoding the wiring of the $G$-matrices, while $\beta$ encodes the wiring of the $H$-matrices. A diagram $\mathcal{D}_{\alpha,\beta}$ consists of the following (see Figure 9 for a simple example):

* $\#(\alpha) + \#(\alpha^{-1}\gamma)$ loops corresponding to the round decorations of $G$,

* $\#(\beta) + \#(\beta^{-1}\gamma)$ loops corresponding to the round decorations of $H$,

* $\#(\alpha^{-1}\beta)$ loops corresponding to all the square decorations,

where $\gamma = (123 \cdots p) \in S_p$ is the full-cycle permutation and the boxes are numbered from right to left. Let us first justify the formula for the number of $d$-dimensional (i.e., corresponding to round decorations) loops given by $\alpha$. Note that the permutation $\alpha$, acting on the top boxes, gives rise to two types of loops: the top ones, in which the output of the $i$-th $G$ box is connected to the corresponding input of the $i$-th $G^*$ box, and the bottom ones, where the output of the $i$-th $G$ box is connected to the
<figure><img src="image_13.png" /><figcaption>**Figure 8.** A graphical representation of the bi-partite matrix $Z = [\Phi_G \otimes \Phi_H](\omega_\ell)$. Round labels represent the space $\mathbb{C}^d$, while square labels represent $\mathbb{C}^\ell$.</figcaption></figure>

**Theorem 7.3.** Consider two independent Ginibre matrices $G, H \in \mathcal{M}_{d2 \times \ell}(\mathbb{C})$ and the corresponding CP maps $\Phi_{G,H} : \mathcal{M}_\ell(\mathbb{C}) \to \mathcal{M}_d(\mathbb{C})$. Define

$$Z := [\Phi_G \otimes \Phi_H](\omega_\ell) \in \mathcal{M}_{d2}(\mathbb{C}).$$

Then, for all $n \ge 1$,

$$m_n(\ell) = \lim_{d \to \infty} \mathbb{E} \frac{1}{d^2} \mathrm{Tr} \left( \frac{Z}{d^2} \right)^n.$$

*Proof.* The statement is a moment computation which is quite standard in the theory of random matrices. We give a proof using the graphical version of Wick's formula developed in [7]. The diagram corresponding to the matrix $Z$ is depicted in Figure 8.

To compute the $n$-th moment of $Z$, $\mathbb{E} \mathrm{Tr} Z^n$, one considers the expectation value of the trace of the concatenation of $n$ instances of the diagram in Figure 8. This expectation value is, according to the graphical Wick formula [7, Theorem 3.2], a combinatorial sum indexed by two permutations $\alpha, \beta \in S_n$ of diagrams $\mathcal{D}_{\alpha,\beta}$. Note that we have here two (independent) permutations since we are dealing with independent Gaussian matrices $G$ and $H$: the permutation $\alpha$ is encoding the wiring of the $G$-matrices, while $\beta$ encodes the wiring of the $H$-matrices. A diagram $\mathcal{D}_{\alpha,\beta}$ consists of the following (see Figure 9 for a simple example):

* $\#(\alpha) + \#(\alpha^{-1}\gamma)$ loops corresponding to the round decorations of $G$,

* $\#(\beta) + \#(\beta^{-1}\gamma)$ loops corresponding to the round decorations of $H$,

* $\#(\alpha^{-1}\beta)$ loops corresponding to all the square decorations,

where $\gamma = (123 \cdots p) \in S_p$ is the full-cycle permutation and the boxes are numbered from right to left. Let us first justify the formula for the number of $d$-dimensional (i.e., corresponding to round decorations) loops given by $\alpha$. Note that the permutation $\alpha$, acting on the top boxes, gives rise to two types of loops: the top ones, in which the output of the $i$-th $G$ box is connected to the corresponding input of the $i$-th $G^*$ box, and the bottom ones, where the output of the $i$-th $G$ box is connected to the
<figure><img src="image_15.png" /><figcaption>**Figure 9.** The diagram $\mathcal{D}_{\alpha=(1)(2), \beta=(12)}$ as a term in the graphical Wick expansion of $\mathbb{E} \mathrm{Tr} Z^2$. This diagram consists of 6 $d$-dimensional loops (3 corresponding to the top (red) pictures and 3 corresponding to the bottom (blue) ones) and of 1 $\ell$-dimensional loop.</figcaption></figure>

corresponding input of the $\gamma(i)$-th $G^*$ box. It is now an easy combinatorial fact that the number of connected components of a bipartite graph on $2n$ vertices having edges

$$ \{(i, n + \gamma(i))\}_{i=1}^n \sqcup \{(i, n + \sigma(i))\}_{i=1}^n $$

is precisely $\#(\sigma^{-1}\gamma)$, proving our claim. A similar argument settles the case of the $\ell$-dimensional loops, where the top and the bottom symbols are identified by the wires corresponding to the maximally entangled state $\omega_d$.

The result of applying the graphical Wick formula is thus

$$ d^{-2-2p} \mathbb{E} \mathrm{Tr} Z^p = d^{-2-2p} \sum_{\alpha, \beta \in S_n} d^{\#(\alpha)+\#(\alpha^{-1}\gamma)+\#(\beta)+\#(\beta^{-1}\gamma)} \ell^{\#(\alpha^{-1}\beta)}. $$

Using standard combinatorial inequalities about permutations (see [5] or [20, Lecture 23]), we have

$$ \begin{aligned} \#(\alpha) + \#(\alpha^{-1}\gamma) &\le p+1, \\ \#(\beta) + \#(\beta^{-1}\gamma) &\le p+1 \end{aligned} $$

with equality if and only if both $\alpha$ and $\beta$ are geodesic permutations (see Section 2.1) corresponding to non-crossing partitions. Moreover, for such permutations, $\#(\alpha^{-1}\beta)$ is precisely the number of loops of the meandric system built from $\alpha$ and $\beta$ (see Proposition 2.1), finishing the proof. ■

**Remark 7.4.** In the statement above, one can replace the random CP map $\Phi_H$ with $\Phi_G$ or even $\Phi_{\bar{G}}$. This fact, quite surprising at first, is due to the particular asymptotic regime we are interested in, that is, $d \to \infty$ and $\ell$ fixed. When performing the
<figure><img src="image_14.png" /><figcaption>**Figure 9.** The diagram $\mathcal{D}_{\alpha=(1)(2), \beta=(12)}$ as a term in the graphical Wick expansion of $\mathbb{E} \mathrm{Tr} Z^2$. This diagram consists of 6 $d$-dimensional loops (3 corresponding to the top (red) pictures and 3 corresponding to the bottom (blue) ones) and of 1 $\ell$-dimensional loop.</figcaption></figure>

corresponding input of the $\gamma(i)$-th $G^*$ box. It is now an easy combinatorial fact that the number of connected components of a bipartite graph on $2n$ vertices having edges

$$ \{(i, n + \gamma(i))\}_{i=1}^n \sqcup \{(i, n + \sigma(i))\}_{i=1}^n $$

is precisely $\#(\sigma^{-1}\gamma)$, proving our claim. A similar argument settles the case of the $\ell$-dimensional loops, where the top and the bottom symbols are identified by the wires corresponding to the maximally entangled state $\omega_d$.

The result of applying the graphical Wick formula is thus

$$ d^{-2-2p} \mathbb{E} \mathrm{Tr} Z^p = d^{-2-2p} \sum_{\alpha, \beta \in S_n} d^{\#(\alpha)+\#(\alpha^{-1}\gamma)+\#(\beta)+\#(\beta^{-1}\gamma)} \ell^{\#(\alpha^{-1}\beta)}. $$

Using standard combinatorial inequalities about permutations (see [5] or [20, Lecture 23]), we have

$$ \#(\alpha) + \#(\alpha^{-1}\gamma) \le p + 1, $$

$$ \#(\beta) + \#(\beta^{-1}\gamma) \le p + 1 $$

with equality if and only if both $\alpha$ and $\beta$ are geodesic permutations (see Section 2.1) corresponding to non-crossing partitions. Moreover, for such permutations, $\#(\alpha^{-1}\beta)$ is precisely the number of loops of the meandric system built from $\alpha$ and $\beta$ (see Proposition 2.1), finishing the proof. ■

**Remark 7.4.** In the statement above, one can replace the random CP map $\Phi_H$ with $\Phi_G$ or even $\Phi_{\bar{G}}$. This fact, quite surprising at first, is due to the particular asymptotic regime we are interested in, that is, $d \to \infty$ and $\ell$ fixed. When performing the
Gaussian integration using the graphical Wick calculus, one obtains a sum over permutations $\alpha \in S_{2n}$; however, due to the fact that $\ell$ is fixed, the permutation $\alpha$ will be constraint to leave invariant the top (resp., the bottom) $n$ points; this, in turn, amounts to having a decomposition $\alpha = \alpha^T \sqcup \alpha^B$, with $\alpha^{T,B} \in S_n$, and the proof would continue as above. Note that if $\ell$ would grow with $d$, different behavior would occur; see, e.g., [6].

**Remark 7.5.** One can keep track of the parameters $A$ and $B$ appearing in the definition of the generating function $M$ from (11) by adding a decoration of type “A” (resp., “B”) on the partial traces appearing in the Stinespring dilation formulas for the channels $\Phi_G$ (resp., $\Phi_H$); we leave the details to the reader.

## 7.2. Shallow top meanders

We consider in this section shallow top meanders, that is, meanders built out of a general non-crossing partition and an interval partition (which sits on the top). We will construct a random matrix model for these combinatorial objects by replacing the random channel $\Phi_H$ from Theorem 7.3 by a non-random channel. First, we define the corresponding shallow top meander polynomial by

$$m_n^{\text{ST}}(\ell) := \sum_{\substack{\alpha \in \text{Int}(n) \\ \beta \in \text{NC}(n)}} \ell^{\#(\alpha^{-1}\beta)} = \sum_{\substack{\alpha \in \text{Kr Int}(n) \\ \beta \in \text{NC}(n)}} \ell^{\#(\alpha^{-1}\beta)}.$$

**Theorem 7.6.** Consider a Ginibre matrix $G \in \mathcal{M}_{d^2 \times \ell}(\mathbb{C})$ and the corresponding completely positive map

$$\Phi_G : \mathcal{M}_\ell(\mathbb{C}) \to \mathcal{M}_d(\mathbb{C}) \\ X \mapsto [\text{Tr}_d \otimes \text{id}_d](GXG^*).$$

Define

$$Z := [\Phi_G \otimes \Psi](\omega_\ell) \in \mathcal{M}_{d\ell}(\mathbb{C}), \\ Z_0 := [\Phi_G \otimes \text{id}](\omega_\ell) \in \mathcal{M}_{d\ell}(\mathbb{C}),$$

where the completely positive map $\Psi$ is defined by

$$\Psi : \mathcal{M}_\ell(\mathbb{C}) \to \mathcal{M}_\ell(\mathbb{C}) \qquad (12) \\ X \mapsto X + (\text{Tr} X) I_\ell.$$

Then, for all integers $n$, $\ell \ge 1$,

$$m_n^{\text{ST}}(\ell) = \lim_{d \to \infty} \mathbb{E} \frac{1}{d} \text{Tr}[(d^{-1} Z_0)(d^{-1} Z)^{n-1}].$$
Gaussian integration using the graphical Wick calculus, one obtains a sum over permutations $\alpha \in S_{2n}$; however, due to the fact that $\ell$ is fixed, the permutation $\alpha$ will be constraint to leave invariant the top (resp., the bottom) $n$ points; this, in turn, amounts to having a decomposition $\alpha = \alpha^T \sqcup \alpha^B$, with $\alpha^{T,B} \in S_n$, and the proof would continue as above. Note that if $\ell$ would grow with $d$, different behavior would occur; see, e.g., [6].

**Remark 7.5.** One can keep track of the parameters $A$ and $B$ appearing in the definition of the generating function $M$ from (11) by adding a decoration of type “A” (resp., “B”) on the partial traces appearing in the Stinespring dilation formulas for the channels $\Phi_G$ (resp., $\Phi_H$); we leave the details to the reader.

## 7.2. Shallow top meanders

We consider in this section shallow top meanders, that is, meanders built out of a general non-crossing partition and an interval partition (which sits on the top). We will construct a random matrix model for these combinatorial objects by replacing the random channel $\Phi_H$ from Theorem 7.3 by a non-random channel. First, we define the corresponding shallow top meander polynomial by

$$m_n^{\text{ST}}(\ell) := \sum_{\substack{\alpha \in \text{Int}(n) \\ \beta \in \text{NC}(n)}} \ell^{\#(\alpha^{-1}\beta)} = \sum_{\substack{\alpha \in \text{Kr Int}(n) \\ \beta \in \text{NC}(n)}} \ell^{\#(\alpha^{-1}\beta)}.$$

**Theorem 7.6.** Consider a Ginibre matrix $G \in \mathcal{M}_{d^2 \times \ell}(\mathbb{C})$ and the corresponding completely positive map

$$\Phi_G : \mathcal{M}_\ell(\mathbb{C}) \to \mathcal{M}_d(\mathbb{C}) \\ X \mapsto [\text{Tr}_d \otimes \text{id}_d](GXG^*).$$

Define

$$Z := [\Phi_G \otimes \Psi](\omega_\ell) \in \mathcal{M}_{d\ell}(\mathbb{C}), \\ Z_0 := [\Phi_G \otimes \text{id}](\omega_\ell) \in \mathcal{M}_{d\ell}(\mathbb{C}),$$

where the completely positive map $\Psi$ is defined by

$$\Psi : \mathcal{M}_{\ell}(\mathbb{C}) \to \mathcal{M}_{\ell}(\mathbb{C}) \qquad (12) \\ X \mapsto X + (\text{Tr} X) I_{\ell}.$$

Then, for all integers $n$, $\ell \ge 1$,

$$m_n^{\text{ST}}(\ell) = \lim_{d \to \infty} \mathbb{E} \frac{1}{d} \text{Tr}[(d^{-1} Z_0)(d^{-1} Z)^{n-1}].$$
<figure><img src="image_16.png" /><figcaption>**Figure 10.** The diagram corresponding to $\mathrm{Tr}[Z_0 Z^{n-1}]$.</figcaption></figure>

<figure><img src="image_17.png" /><figcaption>**Figure 11.** Connecting the Choi–Jamiołkowski matrices $C_i$ by the permutation $\beta$ and $\gamma$, where $\gamma(i) = i + 1$.</figcaption></figure>

*Proof.* We will use the graphical Wick formula to compute the expectation value $\mathbb{E} \mathrm{Tr}[Z_0 Z^{n-1}]$. We will encode the action of the linear map $\Psi$ by its Choi–Jamiołkowski matrix $C_\Psi = \omega_\ell + I_{\ell 2}$. Diagrammatically, we will apply the Wick formula to the diagram in Figure 10, with

$$C_1 = C_2 = \cdots = C_{n-1} = C_\Psi = \omega_\ell + I_{\ell 2} \quad \text{and} \quad C_n = \omega_\ell.$$

Applying the graphical Wick formula to compute the expectation over the Gaussian random matrix $G$, we have

$$\mathbb{E} \mathrm{Tr}[Z_0 Z^{n-1}] = \sum_{\beta \in S_n} d^{\#(\beta)} d^{\#(\beta^{-1}\gamma)} \mathrm{Tr}_{\beta,\gamma}[C_1, C_2, \dots, C_n],$$

where the trace factor above corresponds to the diagram obtained by connecting the top output of the $i$-th $C$-box to the top input of the $\beta(i)$-th $C$-box and the bottom output of the $i$-th $C$-box to the bottom input of the $\gamma(i)$-th $C$-box; see Figure 11. Note that the matrices $C_i$ are of finite size $\ell^2$. Thus, in order to take the limit $d \to \infty$, we have to maximize the exponent $\#(\beta) + \#(\beta^{-1}\gamma)$. Using the triangle inequality, we obtain (see the proof of Theorem 7.3)

$$\lim_{d \to \infty} \mathbb{E} \frac{1}{d} \mathrm{Tr}[(d^{-1}Z_0)(d^{-1}Z)^{n-1}] = \sum_{\beta \in \mathrm{NC}(n)} \mathrm{Tr}_{\beta,\gamma}[C_1, C_2, \dots, C_n].$$
<figure><img src="image_15.png" /><figcaption>**Figure 10.** The diagram corresponding to $\mathrm{Tr}[Z_0 Z^{n-1}]$.</figcaption></figure>

<figure><img src="image_16.png" /><figcaption>**Figure 11.** Connecting the Choi–Jamiołkowski matrices $C_i$ by the permutation $\beta$ and $\gamma$, where $\gamma(i) = i + 1$.</figcaption></figure>

*Proof.* We will use the graphical Wick formula to compute the expectation value $\mathbb{E} \mathrm{Tr}[Z_0 Z^{n-1}]$. We will encode the action of the linear map $\Psi$ by its Choi–Jamiołkowski matrix $C_\Psi = \omega_\ell + I_{\ell 2}$. Diagrammatically, we will apply the Wick formula to the diagram in Figure 10, with

$$C_1 = C_2 = \dots = C_{n-1} = C_\Psi = \omega_\ell + I_{\ell 2} \quad \text{and} \quad C_n = \omega_\ell.$$

Applying the graphical Wick formula to compute the expectation over the Gaussian random matrix $G$, we have

$$\mathbb{E} \mathrm{Tr}[Z_0 Z^{n-1}] = \sum_{\beta \in S_n} d^{\#(\beta)} d^{\#(\beta^{-1}\gamma)} \mathrm{Tr}_{\beta,\gamma}[C_1, C_2, \dots, C_n],$$

where the trace factor above corresponds to the diagram obtained by connecting the top output of the $i$-th $C$-box to the top input of the $\beta(i)$-th $C$-box and the bottom output of the $i$-th $C$-box to the bottom input of the $\gamma(i)$-th $C$-box; see Figure 11. Note that the matrices $C_i$ are of finite size $\ell^2$. Thus, in order to take the limit $d \to \infty$, we have to maximize the exponent $\#(\beta) + \#(\beta^{-1}\gamma)$. Using the triangle inequality, we obtain (see the proof of Theorem 7.3)

$$\lim_{d \to \infty} \mathbb{E} \frac{1}{d} \mathrm{Tr}[(d^{-1} Z_0)(d^{-1} Z)^{n-1}] = \sum_{\beta \in \mathrm{NC}(n)} \mathrm{Tr}_{\beta, \gamma}[C_1, C_2, \dots, C_n].$$
<figure><img src="image_18.png" /><figcaption>**Figure 12.** Following the top outputs (in red) of the C-boxes in the diagram $\text{Tr}_{\beta,\gamma}[C_1^Q, C_2^Q, \dots, C_{n-1}^Q, C_n]$. Left: $\beta(i) \notin \bar{Q}$; right: $\beta(i) = \bar{q}_j \in \bar{Q}$.</figcaption></figure>

We will now develop the diagram corresponding to the trace in the sum above. We will encode the choice of $\omega_\ell$ or $I_{\ell 2}$ for each matrix $C_i$ (here, $i \in [n-1]$) by a subset $Q \subseteq [n-1]$; an integer $i \in [n-1]$ is an element of $Q$ if and only if we choose the matrix $\omega_\ell$ for the box $C_i$. Let $\alpha \in \text{Kr Int}(n)$ be the comb partition encoded by the subset $Q$ (see Lemma 3.9). We claim that

$$ \text{Tr}_{\beta,\gamma}[C_1^Q, C_2^Q, \dots, C_{n-1}^Q, C_n] = \ell^{\#(\alpha^{-1}\beta)}, \quad (13) $$

where, for $i \in [n-1]$,

$$ C_i^Q = \begin{cases} \omega_\ell & \text{if } i \in Q, \\ I_{\ell 2} & \text{if } i \notin Q. \end{cases} $$

The claim (13) allows us to conclude, since

$$ m_n^{\text{ST}}(\ell) = \sum_{\substack{Q \subseteq [n-1] \\ \beta \in \text{NC}(n)}} \text{Tr}_{\beta,\gamma}[C_1^Q, C_2^Q, \dots, C_{n-1}^Q, C_n] = \sum_{\substack{\alpha \in \text{Kr Int}(n) \\ \beta \in \text{NC}(n)}} \ell^{\#(\alpha^{-1}\beta)}. $$

Let us now prove (13). Recall from Lemma 3.9 that the geodesic comb permutation $\alpha \in \text{Kr Int}(n)$ associated to a subset $Q \subseteq [n-1]$ is given by

$$ \alpha(i) = \begin{cases} \bar{q}_{j+1} & \text{if } i = \bar{q}_j \in \bar{Q}, \\ i & \text{if } i \notin \bar{Q}, \end{cases} $$

where $\bar{Q} = Q \sqcup \{n\} = \{\bar{q}_1, \dots, \bar{q}_{|Q|+1}\}$. Hence, if we were to follow the top outputs of the boxes $C_i^Q$, we would have (see Figure 12)

$$ i \mapsto \begin{cases} \beta_i = \alpha^{-1} \circ \beta(i) & \text{if } \beta(i) \notin \bar{Q}, \\ \bar{q}_{j-1} = \alpha^{-1} \circ \beta(i) & \text{if } \beta(i) = \bar{q}_j \in \bar{Q}, \end{cases} $$

which shows the claim (13), finishing the proof. ■
<figure><img src="image_17.png" /><figcaption>**Figure 12.** Following the top outputs (in red) of the C-boxes in the diagram $\text{Tr}_{\beta,\gamma}[C_1^Q, C_2^Q, \dots, C_{n-1}^Q, C_n]$. Left: $\beta(i) \notin \bar{Q}$; right: $\beta(i) = \bar{q}_j \in \bar{Q}$.</figcaption></figure>

We will now develop the diagram corresponding to the trace in the sum above. We will encode the choice of $\omega_\ell$ or $I_{\ell 2}$ for each matrix $C_i$ (here, $i \in [n-1]$) by a subset $Q \subseteq [n-1]$; an integer $i \in [n-1]$ is an element of $Q$ if and only if we choose the matrix $\omega_\ell$ for the box $C_i$. Let $\alpha \in \text{Kr Int}(n)$ be the comb partition encoded by the subset $Q$ (see Lemma 3.9). We claim that

$$ \mathrm{Tr}_{\beta,\gamma}[C_1^Q, C_2^Q, \dots, C_{n-1}^Q, C_n] = \ell^{\#(\alpha^{-1}\beta)}, \quad (13) $$

where, for $i \in [n-1]$,

$$ C_i^Q = \begin{cases} \omega_\ell & \text{if } i \in Q, \\ I_{\ell 2} & \text{if } i \notin Q. \end{cases} $$

The claim (13) allows us to conclude, since

$$ m_n^{\mathrm{ST}}(\ell) = \sum_{\substack{Q \subseteq [n-1] \\ \beta \in \mathrm{NC}(n)}} \mathrm{Tr}_{\beta,\gamma}[C_1^Q, C_2^Q, \dots, C_{n-1}^Q, C_n] = \sum_{\substack{\alpha \in \mathrm{Kr Int}(n) \\ \beta \in \mathrm{NC}(n)}} \ell^{\#(\alpha^{-1}\beta)}. $$

Let us now prove (13). Recall from Lemma 3.9 that the geodesic comb partition $\alpha \in \text{Kr Int}(n)$ associated to a subset $Q \subseteq [n-1]$ is given by

$$ \alpha(i) = \begin{cases} \bar{q}_{j+1} & \text{if } i = \bar{q}_j \in \bar{Q}, \\ i & \text{if } i \notin \bar{Q}, \end{cases} $$

where $\bar{Q} = Q \sqcup \{n\} = \{\bar{q}_1, \dots, \bar{q}_{|Q|+1}\}$. Hence, if we were to follow the top outputs of the boxes $C_i^Q$, we would have (see Figure 12)

$$ i \mapsto \begin{cases} \beta_i = \alpha^{-1} \circ \beta(i) & \text{if } \beta(i) \notin \bar{Q}, \\ \bar{q}_{j-1} = \alpha^{-1} \circ \beta(i) & \text{if } \beta(i) = \bar{q}_j \in \bar{Q}, \end{cases} $$

which shows the claim (13), finishing the proof. ■
<figure><img src="image_19.png" /><figcaption>**Figure 13.** The LHS shows the Choi–Jamiołkowski matrices of the two possible operations: $X \mapsto \text{Tr}[X]I_\ell$ or $X \mapsto X$, respectively.</figcaption></figure>

<figure><img src="image_20.png" /><figcaption>**Figure 14.** The diagram for $\text{Tr}[\omega_l Z^{n-1}]$. Each row contains $(n-1)$ boxes corresponding to the Choi–Jamiołkowski matrix of the map $\Psi$.</figcaption></figure>

### 7.3. Thin meandric systems

In the case of thin meandric systems (corresponding to bottom and top permutations corresponding to interval partitions, see Section 4), there is a matrix model which is closely related to the one in the previous section. Actually, one needs to replace in the statement of Theorem 7.6 the random CP map $\Phi_G$ (responsible for the general non-crossing permutation $\beta$) by another copy of the deterministic linear CP map $\Psi$ from (12). Before stating and proving the result, let us define the corresponding meander polynomial

$$m_n^{\text{thin}}(\ell) := \sum_{\alpha, \beta \in \text{Int}(n)} \ell^{\#(\alpha^{-1}\beta)} = \sum_{\alpha, \beta \in \text{Kr Int}(n)} \ell^{\#(\alpha^{-1}\beta)}.$$

**Theorem 7.7.** *Recall the linear, completely positive map $\Psi$ from (12) and define the matrix $Z := [\Psi \otimes \Psi](\omega_\ell) \in M_{d^2}(\mathbb{C})$. Then, for all integers $n$, $\ell \ge 1$,*

$$m_n^{\text{thin}}(\ell) = \text{Tr}[\omega_l Z^{n-1}] = \ell(2 + 2\ell)^{n-1}.$$

*Proof.* First, Figure 13 shows how we can interpret the Choi–Jamiołkowski matrix of $\Psi$.

Then, it is straightforward to see that the diagram corresponding to $m_n^{\text{thin}}(\ell)$ is the one from Figure 14, where there are $(n-1)$ boxes containing the sum of $I_{\ell 2}$ and $\omega_\ell$ on each of the two rows. Develop now the diagram as a sum indexed by pairs $(Q, R)$ of subsets of $[n-1]$, where in the top row we replace the $i$-th box by $\omega_\ell$ if $i \in Q$ and
<figure><img src="image_18.png" /><figcaption>**Figure 13.** The LHS shows the Choi–Jamiołkowski matrices of the two possible operations: $X \mapsto \text{Tr}[X]I_\ell$ or $X \mapsto X$, respectively.</figcaption></figure>

<figure><img src="image_19.png" /><figcaption>**Figure 14.** The diagram for $\text{Tr}[\omega_l Z^{n-1}]$. Each row contains $(n-1)$ boxes corresponding to the Choi–Jamiołkowski matrix of the map $\Psi$.</figcaption></figure>

### 7.3. Thin meandric systems

In the case of thin meandric systems (corresponding to bottom and top permutations corresponding to interval partitions, see Section 4), there is a matrix model which is closely related to the one in the previous section. Actually, one needs to replace in the statement of Theorem 7.6 the random CP map $\Phi_G$ (responsible for the general non-crossing permutation $\beta$) by another copy of the deterministic linear CP map $\Psi$ from (12). Before stating and proving the result, let us define the corresponding meander polynomial

$$m_n^{\text{thin}}(\ell) := \sum_{\alpha, \beta \in \text{Int}(n)} \ell^{\#(\alpha^{-1}\beta)} = \sum_{\alpha, \beta \in \text{Kr Int}(n)} \ell^{\#(\alpha^{-1}\beta)}.$$

**Theorem 7.7.** *Recall the linear, completely positive map $\Psi$ from (12) and define the matrix $Z := [\Psi \otimes \Psi](\omega_\ell) \in M_{d^2}(\mathbb{C})$. Then, for all integers $n$, $\ell \ge 1$,*

$$m_n^{\text{thin}}(\ell) = \text{Tr}[\omega_l Z^{n-1}] = \ell(2 + 2\ell)^{n-1}.$$

*Proof.* First, Figure 13 shows how we can interpret the Choi–Jamiołkowski matrix of $\Psi$.

Then, it is straightforward to see that the diagram corresponding to $m_n^{\text{thin}}(\ell)$ is the one from Figure 14, where there are $(n-1)$ boxes containing the sum of $I_{\ell 2}$ and $\omega_\ell$ on each of the two rows. Develop now the diagram as a sum indexed by pairs $(Q, R)$ of subsets of $[n-1]$, where in the top row we replace the $i$-th box by $\omega_\ell$ if $i \in Q$ and
by the identity matrix otherwise, and we use the subset $R$ in the similar manner for the bottom row. It is straightforward to see that the diagram obtained has at most $n$ loops (each contributing a factor $\ell$) and that the exact number of loops is $n - |Q\Delta R|$, where $\Delta$ is the symmetric difference operation. In other words, each time the $i$-th boxes are different on the two rows, a loop is “lost”. Hence,

$$ \mathrm{Tr}[\omega_l Z^{n-1}] = \sum_{Q, R \subseteq [n-1]} \ell^{n - |Q\Delta R|}. $$

It is now easy to check that, given two permutations $\alpha, \beta \in \mathrm{Kr}\,\mathrm{Int}(n)$ defined, respectively, by the subsets $Q, R \subseteq [n-1]$, we have

$$ \#(\alpha^{-1}\beta) = n - |Q\Delta R|, $$

establishing the first claim. The final equality is obtained by noting that

$$ Z = (2 + \ell)I + \omega_l = (2 + \ell)\left(I - \frac{\omega_l}{l}\right) + (2 + 2l)\frac{\omega_l}{l}, $$

which implies in turn that

$$ Z^{n-1} = (2 + \ell)^{n-1} \left( I - \frac{\omega_l}{l} \right) + (2 + 2l)^{n-1} \frac{\omega_l}{l}, $$

and thus, $\mathrm{Tr}[\omega_l Z^{n-1}] = \ell(2 + 2l)^{n-1}$; see also Corollary 4.2. ■

**Acknowledgments.** The authors thank the anonymous referees for many useful remarks and suggestions, and in particular for pointing to them the alternative proof from Remark 3.13. MF acknowledges JSPS KAKENHI (Grants nos. JP16K00005 and JP20K11667). IN was supported by the ANR project ESQuisses (Grant no. ANR-20-CE47-0014-01). This work was supported by Bilateral Joint Research Projects (Japan–France Integrated Action Program (SAKURA), Grant no. JPJSBP120203202, and MEAE-MESRI, PHC Sakura).

## References

[1] M. H. Albert and M. S. Paterson, *Bounds for the growth rate of meander numbers*. J. Combin. Theory Ser. A **112** (2005), no. 2, 250–262 Zbl 1076.05001 MR 2177485

[2] G. W. Anderson, A. Guionnet, and O. Zeitouni, *An introduction to random matrices*. Cambridge Stud. Adv. Math. 118, Cambridge University Press, Cambridge, 2010 Zbl 1184.15023 MR 2760897

[3] O. Arizmendi, T. Hasebe, F. Lehner, and C. Vargas, *Relations between cumulants in non-commutative probability*. Adv. Math. **282** (2015), 56–92 Zbl 1319.05019 MR 3374523
by the identity matrix otherwise, and we use the subset $R$ in the similar manner for the bottom row. It is straightforward to see that the diagram obtained has at most $n$ loops (each contributing a factor $\ell$) and that the exact number of loops is $n - |Q\Delta R|$, where $\Delta$ is the symmetric difference operation. In other words, each time the $i$-th boxes are different on the two rows, a loop is “lost”. Hence,

$$ \mathrm{Tr}[\omega_l Z^{n-1}] = \sum_{Q, R \subseteq [n-1]} \ell^{n - |Q\Delta R|}. $$

It is now easy to check that, given two permutations $\alpha, \beta \in \mathrm{Kr}\,\mathrm{Int}(n)$ defined, respectively, by the subsets $Q, R \subseteq [n-1]$, we have

$$ \#(\alpha^{-1}\beta) = n - |Q\Delta R|, $$

establishing the first claim. The final equality is obtained by noting that

$$ Z = (2 + \ell)I + \omega_l = (2 + \ell)\left(I - \frac{\omega_l}{l}\right) + (2 + 2l)\frac{\omega_l}{l}, $$

which implies in turn that

$$ Z^{n-1} = (2 + \ell)^{n-1} \left(I - \frac{\omega_l}{l}\right) + (2 + 2l)^{n-1} \frac{\omega_l}{l}, $$

and thus, $\mathrm{Tr}[\omega_l Z^{n-1}] = \ell(2 + 2l)^{n-1}$; see also Corollary 4.2. ■

**Acknowledgments.** The authors thank the anonymous referees for many useful remarks and suggestions, and in particular for pointing to them the alternative proof from Remark 3.13. MF acknowledges JSPS KAKENHI (Grants nos. JP16K00005 and JP20K11667). IN was supported by the ANR project ESQuisses (Grant no. ANR-20-CE47-0014-01). This work was supported by Bilateral Joint Research Projects (Japan–France Integrated Action Program (SAKURA), Grant no. JPJSBP120203202, and MEAE-MESRI, PHC Sakura).

## References

[1] M. H. Albert and M. S. Paterson, *Bounds for the growth rate of meander numbers*. J. Combin. Theory Ser. A **112** (2005), no. 2, 250–262 Zbl 1076.05001 MR 2177485

[2] G. W. Anderson, A. Guionnet, and O. Zeitouni, *An introduction to random matrices*. Cambridge Stud. Adv. Math. 118, Cambridge University Press, Cambridge, 2010 Zbl 1184.15023 MR 2760897

[3] O. Arizmendi, T. Hasebe, F. Lehner, and C. Vargas, *Relations between cumulants in non-commutative probability*. Adv. Math. **282** (2015), 56–92 Zbl 1319.05019 MR 3374523
[4] J. S. Beissinger, *The enumeration of irreducible combinatorial objects. J. Combin. Theory Ser. A* **38** (1985), no. 2, 143–169 Zbl **0587.05004** MR **784711**

[5] P. Biane, *Some properties of crossings and partitions. Discrete Math.* **175** (1997), no. 1-3, 41–53 Zbl **0892.05006** MR **1475837**

[6] B. Collins and I. Nechita, *Random quantum channels I: Graphical calculus and the Bell state phenomenon. Comm. Math. Phys.* **297** (2010), no. 2, 345–370 Zbl **1191.81050** MR **2651902**

[7] B. Collins and I. Nechita, *Gaussianization and eigenvalue statistics for random quantum channels (III). Ann. Appl. Probab.* **21** (2011), no. 3, 1136–1179 Zbl **1221.81035** MR **2830615**

[8] P. Di Francesco, *Matrix model combinatorics: Applications to folding and coloring. In Random matrix models and their applications*, pp. 111–170, Math. Sci. Res. Inst. Publ. 40, Cambridge University Press, Cambridge, 2001 Zbl **1129.81334** MR **1842785**

[9] P. Di Francesco, O. Golinelli, and E. Guitter, *Meander, folding, and arch statistics. Math. Comput. Modelling* **26** (1997), no. 8-10, 97–147; Combinatorics and physics (Marseilles, 1995) Zbl **1185.82026** MR **1492504**

[10] V. Féray and P. Thévenin, *Components in meandric systems and the infinite noodle. Int. Math. Res. Not. IMRN* **2023** (2023), no. 14, 12538–12560 Zbl **1519.05014** MR **4615238**

[11] M. Fukuda and I. Nechita, *Additivity rates and PPT property for random quantum channels. Ann. Math. Blaise Pascal* **22** (2015), no. 1, 1–72 Zbl **1338.46072** MR **3361563**

[12] M. Fukuda and I. Nechita, *Enumerating meandric systems with large number of loops. Ann. Inst. Henri Poincaré D* **6** (2019), no. 4, 607–640 Zbl **1431.05006** MR **4033682**

[13] M. Fukuda and P. Śniady, *Partial transpose of random quantum states: exact formulas and meanders. J. Math. Phys.* **54** (2013), no. 4, article no. 042202, 23 pp. Zbl **1285.81005** MR **3088232**

[14] I. P. Goulden, A. Nica, and D. Puder, *Asymptotics for a class of meandric systems, via the Hasse diagram of NC(n). Int. Math. Res. Not. IMRN* **2020** (2020), no. 4, 983–1034 Zbl **1437.05105** MR **4073935**

[15] R. Horodecki, P. Horodecki, M. Horodecki, and K. Horodecki, *Quantum entanglement. Rev. Modern Phys.* **81** (2009), no. 2, 865–942 Zbl **1205.81012** MR **2515619**

[16] S. K. Lando and A. K. Zvonkin, *Plane and projective meanders. Theoret. Comput. Sci.* **117** (1993), no. 1-2, 227–241 Zbl **0792.05005** MR **1235181**

[17] F. Lehner, *Cumulants in noncommutative probability theory. I. Noncommutative exchangeability systems. Math. Z.* **248** (2004), no. 1, 67–100 Zbl **1089.46040** MR **2092722**

[18] J. A. Mingo and R. Speicher, *Free probability and random matrices*. Fields Inst. Monogr. 35, Springer, New York; Fields Institute for Research in Mathematical Sciences, Toronto, ON, 2017 Zbl **1387.60005** MR **3585560**

[19] A. Nica, *Free probability aspect of irreducible meandric systems, and some related observations about meanders. Infin. Dimens. Anal. Quantum Probab. Relat. Top.* **19** (2016), no. 2, article no. 1650011, 22 pp. Zbl **1359.46053** MR **3511892**
[4] J. S. Beissinger, The enumeration of irreducible combinatorial objects. *J. Combin. Theory Ser. A* **38** (1985), no. 2, 143–169 Zbl **0587.05004** MR **784711**

[5] P. Biane, Some properties of crossings and partitions. *Discrete Math.* **175** (1997), no. 1-3, 41–53 Zbl **0892.05006** MR **1475837**

[6] B. Collins and I. Nechita, Random quantum channels I: Graphical calculus and the Bell state phenomenon. *Comm. Math. Phys.* **297** (2010), no. 2, 345–370 Zbl **1191.81050** MR **2651902**

[7] B. Collins and I. Nechita, Gaussianization and eigenvalue statistics for random quantum channels (III). *Ann. Appl. Probab.* **21** (2011), no. 3, 1136–1179 Zbl **1221.81035** MR **2830615**

[8] P. Di Francesco, Matrix model combinatorics: Applications to folding and coloring. In *Random matrix models and their applications*, pp. 111–170, Math. Sci. Res. Inst. Publ. 40, Cambridge University Press, Cambridge, 2001 Zbl **1129.81334** MR **1842785**

[9] P. Di Francesco, O. Golinelli, and E. Guitter, Meander, folding, and arch statistics. *Math. Comput. Modelling* **26** (1997), no. 8-10, 97–147; Combinatorics and physics (Marseilles, 1995) Zbl **1185.82026** MR **1492504**

[10] V. Féray and P. Thévenin, Components in meandric systems and the infinite noodle. *Int. Math. Res. Not.* **IMRN 2023** (2023), no. 14, 12538–12560 Zbl **1519.05014** MR **4615238**

[11] M. Fukuda and I. Nechita, Additivity rates and PPT property for random quantum channels. *Ann. Math. Blaise Pascal* **22** (2015), no. 1, 1–72 Zbl **1338.46072** MR **3361563**

[12] M. Fukuda and I. Nechita, Enumerating meandric systems with large number of loops. *Ann. Inst. Henri Poincaré D 6* (2019), no. 4, 607–640 Zbl **1431.05006** MR **4033682**

[13] M. Fukuda and P. Śniady, Partial transpose of random quantum states: exact formulas and meanders. *J. Math. Phys.* **54** (2013), no. 4, article no. 042202, 23 pp. Zbl **1285.81005** MR **3088232**

[14] I. P. Goulden, A. Nica, and D. Puder, Asymptotics for a class of meandric systems, via the Hasse diagram of NC(n). *Int. Math. Res. Not.* **IMRN 2020** (2020), no. 4, 983–1034 Zbl **1437.05105** MR **4073935**

[15] R. Horodecki, P. Horodecki, M. Horodecki, and K. Horodecki, *Quantum entanglement*. *Rev. Modern Phys.* **81** (2009), no. 2, 865–942 Zbl **1205.81012** MR **2515619**

[16] S. K. Lando and A. K. Zvonkin, Plane and projective meanders. *Theoret. Comput. Sci.* **117** (1993), no. 1-2, 227–241 Zbl **0792.05005** MR **1235181**

[17] F. Lehner, Cumulants in noncommutative probability theory. I. Noncommutative exchangeability systems. *Math. Z.* **248** (2004), no. 1, 67–100 Zbl **1089.46040** MR **2092722**

[18] J. A. Mingo and R. Speicher, *Free probability and random matrices*. Fields Inst. Monogr. 35, Springer, New York; Fields Institute for Research in Mathematical Sciences, Toronto, ON, 2017 Zbl **1387.60005** MR **3585560**

[19] A. Nica, Free probability aspect of irreducible meandric systems, and some related observations about meanders. *Infin. Dimens. Anal. Quantum Probab. Relat. Top.* **19** (2016), no. 2, article no. 1650011, 22 pp. Zbl **1359.46053** MR **3511892**
[20] A. Nica and R. Speicher, *Lectures on the combinatorics of free probability*. London Math. Soc. Lecture Note Ser. 335, Cambridge University Press, Cambridge, 2006
Zbl 1133.60003 MR 2266879

[21] A. Nica and P. Zhong, *An operator that relates to semi-meander polynomials via a two-sided q-Wick formula*. *Indiana Univ. Math. J.* **69** (2020), no. 6, 2089–2127
Zbl 1455.05008 MR 4170088

[22] R. Speicher and R. Woroudi, *Boolean convolution*. In *Free probability theory (Waterloo, ON, 1995)*, pp. 267–279, Fields Inst. Commun. 12, American Mathematical Society, Providence, RI, 1997
Zbl 0872.46033 MR 1426845

[23] W. F. Stinespring, *Positive functions on $C^*$-algebras*. *Proc. Amer. Math. Soc.* **6** (1955), 211–216
Zbl 0064.36703 MR 69403

[24] D. Voiculescu, *Symmetries of some reduced free product $C^*$-algebras*. In *Operator algebras and their connections with topology and ergodic theory (Bușteni, 1983)*, pp. 556–588, Lecture Notes in Math. 1132, Springer, Berlin, 1985
Zbl 0618.46048 MR 799593

[25] J. Watrous, *The theory of quantum information*. Cambridge University Press, Cambridge, 2018
Zbl 1393.81004

[26] K. Życzkowski and H.-J. Sommers, *Induced measures in the space of mixed quantum states*. *J. Phys. A* **34** (2001), no. 35, 7111–7125
Zbl 1031.81011 MR 1863143

Communicated by Adrian Tanasă

Received 12 April 2021; revised 25 September 2023.

**Motohisa Fukuda**

Yamagata University, 1-4-12 Kojirakawa, Yamagata 990-8560, Japan;

fukuda@sci.kj.yamagata-u.ac.jp

**Ion Nechita**

Laboratoire de Physique Théorique, Université de Toulouse, CNRS, UPS, 31062 Toulouse,
France;

nechita@irsamc.ups-tlse.fr
[20] A. Nica and R. Speicher, *Lectures on the combinatorics of free probability*. London Math. Soc. Lecture Note Ser. 335, Cambridge University Press, Cambridge, 2006
Zbl 1133.60003 MR 2266879

[21] A. Nica and P. Zhong, *An operator that relates to semi-meander polynomials via a two-sided q-Wick formula*. *Indiana Univ. Math. J.* **69** (2020), no. 6, 2089–2127
Zbl 1455.05008 MR 4170088

[22] R. Speicher and R. Woroudi, *Boolean convolution*. In *Free probability theory (Waterloo, ON, 1995)*, pp. 267–279, Fields Inst. Commun. 12, American Mathematical Society, Providence, RI, 1997 Zbl 0872.46033 MR 1426845

[23] W. F. Stinespring, *Positive functions on $C^*$-algebras*. *Proc. Amer. Math. Soc.* **6** (1955), 211–216 Zbl 0064.36703 MR 69403

[24] D. Voiculescu, *Symmetries of some reduced free product $C^*$-algebras*. In *Operator algebras and their connections with topology and ergodic theory (Buşteni, 1983)*, pp. 556–588, Lecture Notes in Math. 1132, Springer, Berlin, 1985 Zbl 0618.46048 MR 799593

[25] J. Watrous, *The theory of quantum information*. Cambridge University Press, Cambridge, 2018 Zbl 1393.81004

[26] K. Życzkowski and H.-J. Sommers, *Induced measures in the space of mixed quantum states*. *J. Phys. A* **34** (2001), no. 35, 7111–7125 Zbl 1031.81011 MR 1863143

Communicated by Adrian Tanasă

Received 12 April 2021; revised 25 September 2023.

**Motohisa Fukuda**

Yamagata University, 1-4-12 Kojirakawa, Yamagata 990-8560, Japan;

fukuda@sci.kj.yamagata-u.ac.jp

**Ion Nechita**

Laboratoire de Physique Théorique, Université de Toulouse, CNRS, UPS, 31062 Toulouse,
France;

nechita@irsamc.ups-tlse.fr