# A Baxter class of a different kind, and other bijective
results using tableau sequences ending with a row shape

Sophie Burrill, Stephen Melczer, Marni Mishna

► To cite this version:

Sophie Burrill, Stephen Melczer, Marni Mishna. A Baxter class of a different kind, and other bijective results using tableau sequences ending with a row shape. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.369-380, 10.46298/dmtcs.2530. hal-01337810

HAL Id: hal-01337810

https://hal.science/hal-01337810

Submitted on 27 Jun 2016

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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
A Baxter class of a different kind, and other bijective results using tableau sequences ending with a row shape

Sophie Burrill¹ and Stephen Melczer²† and Marni Mishna¹‡

¹Department of Mathematics, Simon Fraser University, Burnaby BC Canada

²Cheriton School of Computer Science, University of Waterloo, Waterloo ON Canada & U. Lyon, CNRS, ENS de Lyon, Inria, UCBL, Laboratoire LIP

**Abstract.** Tableau sequences of bounded height have been central to the analysis of k-noncrossing set partitions and matchings. We show here that families of sequences that end with a row shape are particularly compelling and lead to some interesting connections. First, we prove that hesitating tableaux of height at most two ending with a row shape are counted by Baxter numbers. This permits us to define three new Baxter classes which, remarkably, do not obviously possess the antipodal symmetry of other known Baxter classes. Oscillating tableau of height bounded by k ending in a row are in bijection with Young tableaux of bounded height 2k. We discuss this recent result, and some generating function implications. Many of our proofs are analytic in nature, so there are intriguing combinatorial bijections to be found.

**Résumé.** Les séquences de tableau de hauteur bornée sont au centre de l'analyse des partages et couplages. Nous montrons que les familles de squences qui se terminent par une seule ligne sont particulièrement fascinantes. Tout d'abord, nous prouvons que les tableaux hésitants de hauteur au plus deux se terminant par une seule ligne sont dénombrés par les nombres de Baxter. Cela nous permet de définir trois nouvelles classes Baxter qui, remarquablement, ne possèdent évidemment pas la symétrie antipodes des autres classes Baxter connus. Nous discutons le résultat récent qui dit que les tableaux oscillants de hauteur au plus k se terminant dans une ligne sont en bijection avec les tableaux de Young de hauteur au plus 2k. Nos preuves sont analytiques, il y a donc des bijections combinatoires intrigantes à trouvés.

**Keywords:** Young tableaux, nonnesting partitions, matchings, Baxter permutations, bijections, oscillating tableaux

# 1 Introduction

The counting sequence for Baxter permutations, whose elements

$$B_n = \sum_{k=1}^{n} \frac{\binom{n+1}{k-1} \binom{n+1}{k} \binom{n+1}{k+1}}{\binom{n+1}{1} \binom{n+1}{2}}$$

<footnote>†Supported by an NSERC Alexander Graham Bell Canada Graduate Scholarship</footnote>

<footnote>‡Supported by an NSERC Discovery Grant</footnote>
are known as Baxter numbers, is a fascinating combinatorial entity, enumerating a diverse selection of combinatorial classes and resurfacing in many contexts which do not a priori appear connected. The recent comprehensive survey of Felsner, Fusy, Noy and Orden [14] finds many structural commonalities among these seemingly diverse families of objects.

Here we describe three new combinatorial classes which are enumerated by Baxter numbers. These classes have combinatorial bijections between them, but **do not** share many of the properties of the other known Baxter classes aside from a natural Catalan subclass. Rather, they connect to the restricted arc diagram family of objects, whose study was launched by Chen, Deng, Du, Stanley and Yan [10]. We have discovered a bridge between classic Baxter objects and sequences of tableaux, and consequently walks in Weyl chambers. The main focus of this article is tableau sequences that end in a (possibly empty) row shape: as these correspond to a family of lattice walks that end on a boundary, we are able to deduce enumerative results and find surprising connections to other known combinatorial structures. Another consequence of this construction is a new generating tree description for Baxter numbers.

Our main results are Theorem 1 and Theorem 2. They use the integer lattice $W_k = \{(x_k, \dots, x_1) : x_k > \dots > x_1 > 0, x_i \in \mathbb{N}\}$. All of the other combinatorial classes referenced in the statement are defined in the next section.

**Theorem 1** The following classes are in bijection for all nonnegative integers $m, n$ and $k$:

1. $\mathcal{H}_{n,m}^{(k)}$: the set of hesitating tableaux of length $2n$, with maximum height bounded by $k$, starting from $\emptyset$, ending in a strip of length $m$;

2. $\mathcal{L}_{n,m}^{(k)}$: the set of $W_k$-hesitating lattice walks of length $2n$, starting at $\delta = (k, k-1, \dots, 1)$ ending at $(m+k, k-1, \dots, 1)$;

3. $\Omega_{n,m}^{(k)}$: open partition diagrams of length $n$ with $m$ open arcs, but with no enhanced $(k+1)$-nesting, nor future enhanced $(k+1)$-nesting.

The equivalence $(1) \equiv (2)$ follows almost immediately from the proof of Theorem 3.6 of [10]. We discuss it in Section 3. We then prove the equivalence $(1) \equiv (3)$, by providing an explicit bijection. It is a slight modification of the bijection $\bar{\phi}$ used in the proof of Theorem 4.3 of [10].

It is well known that both $\mathcal{L}_{n,0}^{(1)}$ and $\Omega_{n,0}^{(1)}$ are of cardinality $C_n$, the Catalan number of index $n$. Furthermore, we have the following theorem, proved in Section 4.

**Theorem 2** Let $\ell^{(k)}m(n) = |\mathcal{L}_{n,m}^{(k)}|$. The number of walks in $\mathcal{L}_{n,m}^{(2)}$ over all possible values of $m$ is equal to the Baxter number of index $n+1$. That is,

$$ \sum_{m=0}^{n} \ell_{m}^{(2)}(n) = B_{n+1}. $$

The related class of oscillating tableaux that end in a row also gives rise to some interesting results.

**Theorem 3** The following classes are in bijection:

1. Oscillating tableaux of length $n$, maximum height bounded by $k$ ending in a strip of length $m$;

2. The set of $W_k$-oscillating lattice walks of length $n$ ending at $(m+k, k-1, \dots, 1)$;
3. Open matching diagrams of length $n$ with no $(k+1)$-nesting, nor future $(k+1)$-nesting, with $m$ open arcs.

The proof of this theorem is analogous to the proof of the previous theorem, and we do not present it here. Rather, we are highly intrigued by a fourth class that also appears to be in bijection.

**Conjecture 4** The set of $W_k$-oscillating lattice walks of length $n$ ending at the boundary $\{(m+k, k-1, \dots, 1) : m \ge 0\}$ is in bijection with standard Young tableaux of size $n$, with height bounded by 2k.

As far as we can tell, this was first conjectured by Burrill [8]. Using the lattice path characterization, we access generating function expressions, and prove the conjecture for $k \le 8$. We discuss the strong evidence for Conjecture 4 in Section 5.

# 2 The Combinatorial Classes

We now describe the combinatorial classes mentioned in the two main theorems.

## 2.1 Tableaux families

There are three tableaux families that we consider.

**oscillating tableau** This is a sequence of Ferrers diagrams such that at every stage a box is either added, or deleted. The sequences start from an empty shape, and have a specified ending shape. The size is the length of the sequence.

**standard Young tableau** This is an oscillating tableau where boxes are only added and never removed.

**hesitating tableau** This is a variant of the oscillating tableaux. They are even length sequences of Ferrers diagrams that start from an empty tableaux. The sequence is composed of pairs of moves of the form: (i) do nothing then add a box; (ii) remove a box then do nothing; or (iii) add a box then remove a box.

In each case, if no diagram in the sequence is of height $k+1$, we say that the tableau has height bounded by $k$. This is how we arrive to the set $\mathcal{H}_{n,m}^{(k)}$, of hesitating tableaux of length $2n$, with height bounded by $k$, ending in the shape $(m)^{(i)}$.

## 2.2 Lattice walks

We focus on two different lattice path families. We are interested in walks in the region$^{(ii)}$ $W_k = \{(x_1, x_2, \dots, x_k) : x_i \in \mathbb{Z}, x_1 > x_2 > \dots > x_k > 0\}$ starting at the point $\delta = (k, k-1, \dots, 1)$. Let $e_i$ be the elementary vector with a 1 at position $i$ and 0 elsewhere. We permit steps that do nothing, which we call “stay steps”.

The class of $W_k$-oscillating walks starts at $\delta$ and takes steps of type $e_i$ or $-e_i$, for $1 \le i \le k$. We define $O_{n,m}^{(k)}$ to be the set of oscillating walks in $W_k$ of length $n$, ending at the point $me_1 + \delta$.

A $W_k$-hesitating walk is of even length, and steps occur in the following pairs: (i) a stay step followed by an $e_i$ step; (ii) a $-e_i$ step followed by a stay step; (iii) an $e_i$ step followed by $-e_j$ step. We focus on $\mathcal{L}_{n,m}^{(k)}$: the set of hesitating lattice walks of length $2n$ in $W_k$, starting at $(k, k-1, \dots, 1)$ and ending at $(m+k, k-1, \dots, 1)$.

<footnote>(i) Here, $(0) \equiv \emptyset$</footnote>

<footnote>(ii) Remark this model is a reparametrization of the region considered in [10]. We slightly shift the notation of [6].</footnote>
## 2.3 Open arc diagrams

Matchings and set partitions are two combinatorial classes that have natural representations using arc diagrams. In the arc diagram representation of a set partition of $\{1, 2, \dots, n\}$, a row of increasing vertices is labelled from 1 to $n$. A partition block $\{a_1, a_2, \dots, a_j\}$, ordered $a_1 < a_2 < \dots < a_j$, is represented by the arcs $(a_1, a_2), (a_2, a_3), \dots, (a_{j-1}, a_j)$ which are always drawn above the row of vertices. The set partition $\pi = \{\{1, 3, 7\}, \{2, 8\}, \{4\}, \{5, 6\}\}$ is depicted as an arc diagram in Figure 1. Matchings are represented similarly, with each pair contributing an arc. A set of $k$ arcs $(i_1, j_1), \dots, (i_k, j_k)$ form a $k$-

<figure><img src="image_2.png" /><figcaption>Fig. 1: The set partition $\pi = \{1, 3, 7\}, \{2, 8\}, \{4\}, \{5, 6\}$</figcaption></figure>

nesting if $i_1 < i_2 < \dots < i_k < j_k < \dots < j_2 < j_1$. They form an *enhanced k-nesting* if $i_1 < i_2 < \dots < i_k \le j_k < \dots < j_2 < j_1$. They form a *k-crossing* if $i_1 < i_2 < \dots < i_k < j_1 < j_2 < \dots < j_k$. Figure 2 illustrates a 3-nesting, an enhanced 3-nesting, and a 3-crossing. A partition is *k-nonnesting* if it does not contain any collection of edges that form a *k-nesting*.

<figure><img src="image_3.png" /><figcaption>Fig. 2: A 3-nesting, an enhanced 3-nesting, a 3-crossing, and a future enhanced 3-nesting</figcaption></figure>

Recently, Burrill, Elizalde, Mishna and Yen [9] generalized arc diagrams by permitting semi-arcs: in the diagrams, each arc must have a left endpoint, but not necessarily a right endpoint. The notion of *k-nesting* is generalized to a *future k-nesting*, which is a pattern with an open arc to the left of a $(k-1)$-nesting, and a future enhanced *k-nesting* is defined similarly. An example is given in Figure 2. Burrill et al. [9] conjectured that open partition diagrams with no future enhanced 3-nestings, nor enhanced 3-nestings were counted by Baxter numbers.

# 3 Bijections

We now give the bijections to prove Theorem 1. Table 1 illustrates the different mappings in the case of $n = 2, k = 2$.

## 3.1 Tableaux to walks

The bijection between $\mathcal{H}_{n,m}^{(k)}$ and $\mathcal{L}_{n,m}^{(k)}$ is a straightforward consequence of the proof of Theorem 3.6 of [10]. The authors give the bijection explicitly for vacillating tableaux, but the results follow directly for the case of hesitating tableaux. In their bijection, a shape $\lambda = (\lambda_1, \dots, \lambda_k)$ in a hesitating tableaux corresponds to a point in position $\delta + \lambda = (\lambda_1 + k, \lambda_2 + k - 1, \dots, \lambda_k + 1)$ in the hesitating walk.

## 3.2 Arc diagrams and tableaux

We modify Chen et al.'s bijection between set partitions and hesitating tableaux to incorporate the possibility that an edge is not closed. In this abstract, we simply describe how to modify Marberg's presentation
<table><caption>Tab. 1: The six objects of size $n = 2$ for each class in Theorem 1</caption><thead><tr><th></th><th>Tableaux $\mathcal{H}_{2,m}^{(2)}$</th><th>Walks $\mathcal{L}_{2,m}^{(2)}$</th><th>Open partitions $\Omega_{2,m}^{(2)}$</th></tr></thead><tbody><tr><td>$m=0$</td><td>$\emptyset \Box \emptyset \Box \emptyset$<br>$\emptyset \emptyset \Box \emptyset \emptyset$</td><td>$ (2,1)-(3,1)-(2,1)-(3,1)-(2,1) $<br>$ (2,1)-(2,1)-(3,1)-(2,1)-(2,1) $</td><td>$ \bullet \bullet $<br>$ \rightsquigarrow $</td></tr><tr><td>$m=1$</td><td>$\emptyset \Box \emptyset \emptyset \Box$<br>$\emptyset \emptyset \emptyset \Box \Box \Box$<br>$\emptyset \emptyset \Box \Box \Box \Box$</td><td>$ (2,1)-(3,1)-(2,1)-(2,1)-(3,1) $<br>$ (2,1)-(2,1)-(3,1)-(4,1)-(3,1) $<br>$ (2,1)-(2,1)-(3,1)-(3,2)-(3,1) $</td><td>$ \bullet \cdot \triangleright $<br>$ \triangleright \cdot \triangleright $<br>$ \triangleright \cdot \cdot $</td></tr><tr><td>$m=2$</td><td>$\emptyset \emptyset \Box \Box \Box \Box$</td><td>$ (2,1)-(2,1)-(3,1)-(3,1)-(4,1) $</td><td>$ \triangleright \cdot \triangleright $</td></tr></tbody></table>

<figure><img src="image_4.png" /><figcaption>Fig. 3: Preparing an open diagram for the bijection.</figcaption></figure>

in [21] of the bijection to handle open arcs. We refer readers to that article, or to Chen et al. to get the full description.

**Proposition 5** The subset of $\Omega_{n,m}^{(k)}$ comprised of open partition diagrams of size $n$ avoiding both enhanced $(k+1)$-nestings, and future enhanced $(k+1)$-nestings consisting of diagrams with $m$ open arcs, is in bijection with hesitating tableaux of length $2n$ of maximum height $k$, ending with a single row of length $m$.

**Proof:** We prove this by describing how to process open arcs. We assume the reader has some familiarity with the original bijection to have a brief presentation of our bijection. We read diagrams from left to right, and insert and delete cells under the same rules as Marberg [21]. The insertion depends on the right endpoints of the arcs. If the diagram has $n$ vertices, we incrementally label the right endpoints of the open arcs with labels $n+1$ to $n+m$ from left to right, as seen in Figure 3.

Recall how vertices are processed in this bijection. Each vertex corresponds to two steps; if $i$ is a left endpoint, first do nothing and then insert its (possibly artificial) right endpoint into the tableau; if $i$ is a right endpoint, delete it from the tableau and then do nothing; if $i$ is both a right endpoint of some arc $(i', i)$ and left endpoint of $(i, i'')$, first insert $i''$ into the tableaux and then delete $i$. If $i$ is a fixed point, first insert $i$, then delete $i$. The insertion is done with RSK, and the deletion is simple cell deletion.

In this process, the values corresponding to open arcs are inserted in the tableau in order, and are never deleted. By RSK, they will all be in the same row. Once the other points are deleted, all that will remains is a single row of length $m$.

The inverse map of Marberg (and ultimately Chen et al.) is similarly adapted. $\square$
# 4 When $k = 2$ the complete generating function is Baxter

## 4.1 Baxter permutations

Baxter numbers comprise entry A001181 of the Online Encyclopedia of Integer Sequences (OEIS) [18], and their main interpretation is the number of permutations $\sigma$ of $n$ such that there are no indices $i < j < k$ satisfying $\sigma(j+1) < \sigma(i) < \sigma(k) < \sigma(j)$ or $\sigma(j) < \sigma(k) < \sigma(i) < \sigma(j+1)$. They were introduced by Baxter [2] in a question about compositions of commuting functions, and have since been found in many places in combinatorics.

Chung et al. [11] found the explicit formula for the $n^{th}$ Baxter number given in Section 1, and also gave a second order linear recurrence:

$$8(n+2)(n+1)B_n + (7n^2 + 49n + 82)B_{n+1} - (n+6)(n+5)B_{n+2} = 0. \quad (1)$$

We prove Theorem 2 by a generating function argument. We use the notation $\bar{x} = \frac{1}{x}$, and work in the ring of formal series $\mathbb{Q}[x, \bar{x}][t]$. The operator $PT_x$ (resp $NT_x$) extracts positive (resp. negative) powers of $x$ in series of $\mathbb{Q}[x, \bar{x}][t]$. We relate this to the diagonal operator $\Delta$ defined by: $\Delta \sum_{i,j \in \mathbb{N}} f_{i,j} x^i t^j = \sum_n f_{n,n} t^n$.

A bivariate series in $\mathbb{Q}[x][t]$ is D-finite with respect to $t$ and $x$ if the set of its partial derivatives spans a finite dimensional vector space over $\mathbb{Q}$. Lipshitz [20] proved that if $F(x, t) \in \mathbb{Q}[x][t]$ is D-finite then so is $f(t) = \Delta F(x, t)$. This result is effective, and creative telescoping strategies have resulted in efficient algorithms for computing such differential equations [13, 5]: that is, given a system of differential equations satisfied by $F(x, t)$, one can compute the linear differential equation satisfied by $\Delta F(x, t) = f(t)$. There are several implementations in various computer algebra systems, such as Mgfun by Chyzak in Maple [12], and the HolonomicFunctions package of Koutschan in Mathematica [19].

Roughly, the strategy is to use elimination in an Ore algebra or an ansatz of undetermined coefficients to compute differential operators annihilating the multivariate integral

$$\frac{1}{2\pi i} \int_{\Omega} \frac{F(x, t/x)}{x} dx = \Delta F(x, t), \quad (2)$$

where $\Omega$ is an appropriate contour in $\mathbb{C}$ containing the origin.

## 4.2 A generating function for hesitating walks ending on an axis

We recall Proposition 12 of Bousquet-Mélou and Xin [6]; As noted earlier, we have shifted our indices, and our presentation of their results are duely adapted. Here $Q_k$ is the first quadrant $Q_k = \{(x_1, \dots, x_k) : x_i > 0\}$.

**Proposition 6 (Bousquet-Mélou and Xin, Proposition 12 of [6])** For any starting and ending points $\lambda$ and $\mu$ in $W_k$, the number of $W_k$-hesitating walks going from $\lambda$ to $\mu$ can be expressed in terms of the number of $Q_k$ hesitating walks as follows:

$$w_k(\lambda, \mu, n) = \sum_{\pi \in S_k} (-1)^\pi q_k(\lambda, \pi(\mu), n),$$

where $(-1)^\pi$ is the sign of $\pi$ and $\pi(\mu_1, \dots, \mu_k) = (\mu_{\pi(1)}, \dots, \mu_{\pi(k)})$.
The result is proved by a classic reflection argument using a simple sign reversing involution between
pairs of walks; the walks restricted to $W_k$ appear as fixed points. We restrict to $k = 2$, and define

$$
H(x; t) = \sum_{i,n} q_2((2, 1), (i, 1), 2n) x^i t^n \quad \text{and} \quad V(y; t) = \sum_{i,n} q_2((2, 1), (1, i), 2n) y^i t^n.
$$

By applying the proposition we see immediatety that

$$
W(x, t) = \sum_{i,n} w_2((2, 1), (i, 1), 2n) x^i t^n = H(x; t) - V(x; t). \quad (3)
$$

Their explicit Proposition 13 is key to our solution.

**Proposition 7 (Bousquet-Mélou and Xin, Proposition 13 of [6])** The series $H(x; t)$ and $V(y; t)$ which count $Q_2$-hesitating walks of even length ending on the x-axis and on the y-axis, satisfy

$$
xH(x; t) = PT_x \frac{Y}{t(1+x)} (x^2 - Y^2/x^2 + Y/x^3) \quad (4)
$$

$$
\bar{x}^2 V(\bar{x}; t) = NT_x \frac{Y}{t(1+x)} (x^2 - Y^2/x^2 + Y/x^3), \quad (5)
$$

where $Y$ is the algebraic function

$$
Y = \frac{-tx^2 + (1-2t)x - t\sqrt{t^2x^4 - 2tx^3 + (-2t^2-4t+1)x^2 - 2tx + t^2}}{2t(1+x)}.
$$

Using this, we can express $W(x, t)$ as a diagonal. Define

$$
G(x, t) = \frac{Y}{t(1+x)} \left( x^2 - \frac{Y^2}{x^2} + \frac{Y}{x^3} \right). \quad (6)
$$

**Lemma 8** The generating function for the class of walks of $W_2$-hesitating walks of even length end on the $x$-axis defined

$$
W(t) = \sum_{i,n} w_2((2, 1), (i, 1), n) t^n
$$

satisfies

$$
W(t) = \Delta \left( \left( G\left(\frac{1}{x}, xt\right) - G(x, xt) \right) \frac{1}{1-x} \right). \quad (7)
$$

**Proof:** We remark that $W(t) = H(1;t) - V(1;t)$ by Equation 3. We apply Proposition 7, and then convert $PT$ and $NT$ operators to diagonal operations by straightforward series manipulation:

$$
H(1; t) = \mathit{PT}_x G(x, t)|_{x=1} = \Delta \left( G\left(\frac{1}{x}, xt\right) \frac{1}{1-x} \right), \quad V(1; t) = \Delta \left( G(x, xt) \frac{1}{1-x} \right). \quad (8)
$$

□

**Theorem 9** Let $B_n$ be the number of Baxter permutations of size $n$. Then $W(t) = \sum B_{n+1}t^n$.
**Proof:** We prove this using effective computations for D-finite closure properties. Using the Mathematica package of Koutschan [19] we use our expression for $W(t)$ as a diagonal to calculate that it satisfies the differential equation $\mathcal{L} \cdot W(t) = 0$, where $\mathcal{L}$ is the differential operator

$$ \mathcal{L} := t^4 (t+1)(8t-1) D_t^5 + t^3 (-20 + 147t + 176t^2) D_t^4 + 4t^2 (-30 + 241t + 304t^2) D_t^3 \\ + 12t (-20 + 191t + 256t^2) D_t^2 + 24 (-5 + 72t + 104t^2) D_t + 240 + 384t. $$

Furthermore, the Equation 1 implies that the shifted generating function for the Baxter numbers written above also satisfies this differential equation. As the solution space of the differential operator $\mathcal{L}$ is a vector space of dimension 5; to prove equality it is sufficient to show that the first five terms of the generating functions are equal. We have verified that the initial terms in the series agree for over 200 terms. □

## 4.3 A new generating tree

A generating tree for a combinatorial class expresses recursive structure in a rooted plane tree with labelled nodes. The objects of size $n$ are each uniquely generated, and the set of objects of size $n$ comprise the $n^{th}$ level of the tree. They are useful for enumeration, and for showing that two classes are in bijection. One consequence of Theorem 2 is a new generating tree construction for Baxter objects.

Several different formalisms exist for generating trees, notably [1]. The central properties are as follows. Every object $\gamma$ in a combinatorial class $\mathcal{C}$ is assigned a label $\ell(\gamma) \in \mathbb{Z}^k$, for some fixed $k$. There is a rewriting rule on these labels with the property that if two nodes have the same label then the ordered list of labels of their children is also the same. We consider labels that are pairs of positive integers, specified by $\{\ell_{\text{Root}} : [i, j] \to \text{Succ}([i, j])\}$, where $\ell_{\text{Root}}$ is the label of the root.

Two generating trees for Baxter objects are known in the literature, and one consequence of Theorem 1 is a third, using the generating tree for $\Omega^{(k)}$ given by Burrill et al. [9]. This tree differs from the other two already at the third level, illustrating a very different decomposition of the objects. For the three different systems, we give the succession rules, and the first 5 levels of the tree (unlabelled) in Figure 4.

# 5 Standard Young tableaux of bounded height

Chen et al. [10] give an analogy comparing the relationship between oscillating tableaux and irreducible representations of the Brauer algebra to the relationship of standard Young tableaux and the symmetric group. Indeed, there are many connections between standard Young tableaux of bounded height and oscillating tableaux of bounded height, but we were unable to find any consideration of the following conjecture.

**Conjecture 10** The set of oscillating lattice walks of length $n$ in $W_k$ ending at the boundary $\{(m+k, k-1, \dots, 1) : m \ge 0\}$ is in bijection with the set of standard Young tableaux of size $n$, of height bounded by $2k$.

The case of $k = 1$ is straightforward. An oscillating walk in $W_1$ is simply a sequence of $e_1$ and $-e_1$ steps such that at any point the number of $e_1$ is greater than or equal to the number of $-e_1$. There is a simple bijection to standard Young tableaux of height 2: Given an oscillating walk as a sequence of steps, $w = w_1, w_2, \dots, w_n$, the standard Young tableaux is filled by putting entry $j$ on the top row of the tableau if $w_j = e_1$, and on the second row if $w_j = -e_1$. However, the interaction between the steps is less straightforward in higher dimensions.
<figure><img src="image_5.png" /><figcaption>Fig. 4: The first five levels of each of the Baxter generating tree. They are respectively from [4] [7] [9].</figcaption></figure>

Eric Fusy remarked to us that the inverse RSK bijection maps standard Young tableaux to involutions, as the images of pairs of identical tableaux. This does not directly give our matching diagrams, but it is a promising candidate for a bijection.

To give evidence for this conjecture, we first give expressions for the exponential generating functions using determinants of matrices filled with Bessel functions. For any $k$ the equivalence could be verified in this manner, and we have done so for $k \le 8$. It is possible that very explicit manipulations might also give an answer.

Next we express Young tableaux as walks, and use standard generating function techniques for the ordinary generating functions. This gives us a different characterization of the bijection in terms of walks, and two expressions for the generating functions as diagonals of rational functions. The technical details of the constructions are reserved for the long version of this article.

## 5.1 A determinant approach

Our first approach to settling this conjecture is a direct appeal to two recent enumerative results. In this section, $b_j(x) = I_j(2x) = \sum_n \frac{(2x)^{2n+j}}{n!(n+j)!}$, the hyperbolic Bessel function of the first kind of order $j$.

Let the $\tilde{Y}_k(t)$ be the exponential generating function for the class of standard Young tableaux with height bounded by $k$. Formulas for $\tilde{Y}_k(t)$ follow from works of Gordon, Houten, Bender and Knuth [15, 16, 3], which depend on the parity of $k$. We are only interested in the even values here.

**Theorem 11 ([15, 16, 3])** The exponential generating function for the class of standard Young tableaux of height bounded by $2k$ is given by

$$ \tilde{Y}_{2k}(t) = \det[b_{i-j}(t) + b_{i+j-1}(t)]_{1 \le i,j \le k}. $$

Around the same time, Grabiner-Magyar [17] determined an exponential generating function for $O_n^{(k)}(\lambda; \mu)$, the number of oscillating lattice walks of length $n$ from $\lambda$ to $\mu$, which stay within the $k$-dimensional Weyl chamber $W_k$ and take steps in the positive or negative unit coordinate vectors.
**Theorem 12 (Grabiner-Magyar [17])** For fixed $\lambda, \mu \in W_k$, the exponential generating function for $O_n(\lambda; \mu)$ satisfies

$$O_{\lambda, \mu}(t) = \sum_{n \ge 0} |O_n(\lambda; \mu)| \frac{t^n}{n!} = \det (b_{\mu_i - \lambda_j}(2t) - b_{\mu_i + \lambda_j}(2t))_{1 \le i,j \le k}.$$

We specialize the start and end positions as $\lambda = \delta = (d, d-1, \dots, 1)$ and $\mu = \delta + me_1 = (d+m', d-1, \dots, 1) = (m, d-1, \dots, 1)$. We are interested in the sum over all values of $m$, and define $O_k(t) = \sum_{m \ge 0} O_{\delta, me_1+\delta}(t)$. Using their result we deduce the following.

**Proposition 13** The exponential generating function for the class of oscillating tableaux ending with a row shape is the finite sum

$$\tilde{O}_k(t) = \sum_{u=0}^{k-1} (-1)^u \sum_{\ell=u}^{2k-1-2u} (I_\ell) \det(I_{i-j} - I_{kd-i-j})_{0 \le i \le k-1, i \ne u, 1 \le j \le k-1}.$$

This follows from the fact that the infinite sum which arises from direct application of Grabiner and Magyar's formula telescopes, using also the identity $b_{-k} = b_k$.

Our conjecture is equivalent to $\tilde{O}_k(t) = \tilde{Y}_{2k}(t)$. Here are the first two values:

$$\tilde{O}_1(t) = \tilde{Y}_2(t) = b_0 + b_1, \quad \tilde{O}_2(t) = \tilde{Y}_4(t) = b_0^2 + b_0 b_1 + b_0 b_3 - 2b_1 b_2 - b_2^2 - b_1^2 + b_1 b_3.$$

The determinants are easy to compute for small values, and they agree for $k \le 8$.

## 5.2 A diagonal approach

Using Theorem 3, we can reformulate the conjecture to be strictly in terms of lattice paths by viewing standard Young tableaux as oscillating tableaux with no deleting steps.

**Conjecture 14** The set of oscillating lattice walks of length $n$ in $W_k$ starting at $\delta = (k, k-1, \dots, 1)$ and ending at the boundary at the boundary $\{me_1 + \delta : m \ge 0\}$ is in bijection with the set of oscillating lattice walks of length $n$ in $W_{2k}$, using only positive steps ($e_j$), starting at $\delta$ and ending anywhere in the region.

To approach this, we consider the set of walks separately using some standard enumeration techniques: namely the orbit sum method and results on reflectable walks in Weyl Chambers. Some of the enumerative parallels of these strategies in this context are discussed in [22]. The advantage of these diagonal representations is potential access to asymptotic enumeration formulas, and possibly alternative combinatorial representations. All of the generating functions are D-finite, and we can use the work of [5] to determine bounds on the shape of the annihilating differential equation.

**Theorem 15** The ordinary generating function for oscillating walks starting at $\delta$ and ending on the boundary $\{me_1 + \delta : m \ge 0\}$, is given by the following formula:

$$O_k(t) = \Delta \left[ \frac{t^{2d-1} (z_3 z_4^2 \cdots z_k^{k-2}) (z_1 + 1) \prod_{1 \le j < i \le k} (z_i - z_j) (z_i z_j - 1) \cdot \prod_{2 \le i \le k} (z_i^2 - 1)}{1 - t (z_1 \cdots z_k) (z_1 + \bar{z}_1 + \cdots z_d + \bar{z}_d)} \right].$$
The proof of Theorem 15 is a rather direct application of Gessel and Zeilberger's formula for reflectable walks in Weyl chambers.

By applying an orbit sum analysis, we derive the following expression. There are still some points to verify in the computation, so although we believe it, and have verified it up to $k = 8$, this form remains as a conjecture.

**Conjecture 16** The ordinary generating function for standard Young tableau of height at most $k$ is

$$Y_k(t) = \Delta \left( \frac{(z_1 \cdots z_{k-1}) \Phi(\bar{z})}{(1 - t(z_1 \cdots z_{k-1}) S(\mathbf{z}))(1 - z_1) \cdots (1 - z_{k-1})} \right),$$

where

$$S(\mathbf{z}) = \bar{z}_1 + \bar{z}_1 z_2 + \cdots + \bar{z}_{k-1} z_{k-2} + z_{k-1},$$

and

$$\Phi(\mathbf{z}) = \frac{(z_1 z_{k-1} - 1)}{(z_1 \cdots z_{k-1})^{k-1}} \prod_{j=1}^{k-2} (z_1 z_j - z_{j+1}) \prod_{j=2}^{k-1} (z_{k-1} z_j - z_{j-1}) \prod_{j=1}^{k-3} \prod_{k=j+2}^{k-1} (z_j z_k - z_{j+1} z_{k-1}).$$

In order to prove the conjecture, giving an explicit diagonal representation for the generating function of the number of standard Young tableaux of a given height, it is sufficient to prove that for every $d$

$$\sum_{\sigma \in \mathcal{G}} (-1)^{\text{sgn}(g)} \sigma(z_1 \cdots z_{d-1}) = \frac{(z_1 z_{k-1} - 1)}{(z_1 \cdots z_{k-1})^{k-1}} \prod_{j=1}^{k-2} (z_1 z_j - z_{j+1}) \prod_{j=2}^{k-1} (z_{k-1} z_j - z_{j-1}) \prod_{j=1}^{k-3} \prod_{k=j+2}^{k-1} (z_j z_k - z_{j+1} z_{k-1}),$$

where $\mathcal{G}$ is the finite group of rational transformations of $\mathbb{R}^{d-1}$ generated by

$$\begin{align*}
\phi_1 &: (z_1, \dots, z_{d-1}) \mapsto (\bar{z}_1 z_2, \dots, z_{d-1}) \\
(1 < k < d-1) \quad \phi_k &: (z_1, \dots, z_{d-1}) \mapsto (z_1, \dots, z_{k-1}, \quad z_{k-1} \bar{z}_k z_{k+1}, \quad z_{k+1}, \dots, z_{d-1}) \\
\phi_{d-1} &: (z_1, \dots, z_{d-1}) \mapsto (z_1, \dots, z_{d-1}, z_{d-2} \bar{z}_{d-1}),
\end{align*}$$

which acts on $f \in \mathbb{R}[z_1, \dots, z_d]$ by $\sigma(f(z_1, \dots, z_{d-1})) = f(\sigma(z_1, \dots, z_{d-1}))$. It can be shown that $\mathcal{G}$ is isomorphic to the symmetric group $S_d$, however the action of its elements in terms such as $\sigma(z_1 \cdots z_{d-1})$ is less clear.

# 6 Conclusion

These problems are clearly begging for combinatorial proofs. There are a huge number of candidates for Baxter objects to choose from, and hopefully the Catalan subclasses are retained.

The diagonal expressions in Section 5.2, which are of interest in their own right, are also compelling in a wider context. We are quite interested in the conjecture of Christol on whether or not globally bounded D-finite series can always be expressed as a diagonal of a rational function. The class of standard Young tableau of bounded height is a very intriguing case, and follows our study of lattice path walks [22] wherein we consider the study of diagonal expressions for known D-finite classes.

# Acknowledgements

We are extremely grateful to Eric Fusy, Julien Courtiel, Sylvie Corteel, Lily Yen, Yvan le Borgne and Sergi Elizalde for stimulating conversations, and important insights.
References

[1] Cyril Banderier, Mireille Bousquet-Mélou, Alain Denise, Philippe Flajolet, Danièle Gardy, and Dominique Gouyou-Beauchamps. Generating functions for generating trees. *Discrete Math.*, 246(1-3):29–55, 2002. Formal power series and algebraic combinatorics (Barcelona, 1999).

[2] Glen Baxter. On fixed points of the composite of commuting functions. *Proc. Amer. Math. Soc.*, 15:851–855, 1964.

[3] Edward A. Bender and Donald E. Knuth. Enumeration of plane partitions. *J. Combinatorial Theory Ser. A*, 13:40–54, 1972.

[4] Nicolas Bonichon, Mireille Bousquet-Mélou, and Eric Fusy. Baxter permutations and plane bipolar orientations. *Sém. Lothar. Combin.*, 61:Art. B61Ah, 29 pp. (electronic), 2010.

[5] A. Bostan, P. Lairez, and B. Salvy. Creative telescoping for rational functions using the griffiths-dwork method. In *Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC)*, New York, NY, USA. ACM., pages 93–100, 2013.

[6] Mireille Bousquet-Mélou and Guoce Xin. On partitions avoiding 3-crossings. *Sém. Lothar. Combin.*, 54:Art. B54e, 21 pp. (electronic), 2005/07.

[7] Mathilde Bouvel and Olivier Guibert. Refined Enumeration of Permutations Sorted with Two Stacks and a $D_8$-Symmetry. *Ann. Comb.*, 18(2):199–232, 2014.

[8] Sophie Burrill. *A generating tree approach to k-nonnesting arc diagrams*. PhD thesis, Simon Fraser University, Burnaby, Canada, July 2014. http://summit.sfu.ca/system/files/iritems1/14390/etd8479_SBurrill.pdf.

[9] Sophie Burrill, Sergi Elizalde, Marni Mishna, and Lily Yen. A generating tree approach to k-nonnesting partitions and permutations. *arXiv preprint arXiv:1108.5615*, 2012. arXiv:1108.5615.

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

[11] F. R. K. Chung, R. L. Graham, V. E. Hoggatt, Jr., and M. Kleiman. The number of Baxter permutations. *J. Combin. Theory Ser. A*, 24(3):382–394, 1978.

[12] F. Chyzak. Holonomic systems and automatic proofs of identities. *INRIA Research Report*, (no. 2371):61 pages, 1994.

[13] F. Chyzak. An extension of zeilberger's fast algorithm to general holonomic functions. *Discrete Math.*, 217(1-3):115–134, 2000.

[14] Stefan Felsner, Éric Fusy, Marc Noy, and David Orden. Bijections for Baxter families and related objects. *J. Combin. Theory Ser. A*, 118(3):993–1020, 2011.

[15] Basil Gordon. Notes on plane partitions. V. *J. Combinatorial Theory Ser. B*, 11:157–168, 1971.

[16] Basil Gordon and Lorne Houten. Notes on plane partitions. I, II. *J. Combinatorial Theory*, 4:72–80; 81–99, 1968.

[17] David J. Grabiner and Peter Magyar. Random walks in Weyl chambers and the decomposition of tensor powers. *J. Algebraic Combin.*, 2(3):239–260, 1993.

[18] OEIS Foundation Inc. *The On-Line Encyclopedia of Integer Sequences*. Published electronically at http://oeis.org, 2011.

[19] C. Koutschan. A fast approach to creative telescoping. *Math. Comput. Sci.*, 4(2-3):259–266, 2010.

[20] L. Lipshitz. The diagonal of a $D$-finite power series is $D$-finite. *J. Algebra*, 113(2):373–378, 1988.

[21] Eric Marberg. Crossings and nestings in colored set partitions. *Electron. J. Combin.*, 20(4):Paper 6, 30, 2013.

[22] S. Melczer and M. Mishna. Asymptotic lattice path enumeration using diagonals. In *Proceedings of the Analysis of Algorithms, Paris*, 2014. http://arxiv.org/abs/1402.1230.