# Involutions on Baxter Objects

Kevin Dilks¹†

¹School of Mathematics, University of Minnesota, Minneapolis, MN 55455

**Abstract.** Baxter numbers are known to count several families of combinatorial objects, all of which come equipped with natural involutions. In this paper, we add a combinatorial family to the list, and show that the known bijections between these objects respect these involutions. We also give a formula for the number of objects fixed under this involution, showing that it is an instance of Stembridge’s “$q = -1$ phenomenon”.

**Résumé.** Les nombres Baxter comptent plusieurs familles d'objets combinatoires, qui sont tous équipées avec des involutions naturels. Dans ce papier, nous ajoutons une famille combinatoire à la liste, et nous montrons que les bijections connus entre ces objets respectent ces involutions. En plus, nous donnons une formule pour le nombre d'objets fixés par cette involution et nous montrons qu'elle est une instance du “phénomène $q = -1$” de Stembridge.

**Keywords:** Baxter permutations, involutions, bijections

## 1 Introduction

The Baxter numbers are given by $B(n) := \sum_{k=0}^{n-1} \Theta_{k,n-k-1}$ where

$$ \Theta_{k,l} = \frac{\binom{n+1}{k} \binom{n+1}{k+1} \binom{n+1}{k+2}}{\binom{n+1}{1} \binom{n+1}{2}} \quad (1) $$

for $n = k + l + 1$. The summand $\Theta_{k,l}$ counts many things, defined below, and illustrated in Tables 1 through 4:

(A) Baxter permutations in $S_n$ with $k$ ascents and $l$ descents. [2]

(B) Baxter permutations in $S_n$ with $k$ inverse ascents and $l$ inverse descents.

(C) Twisted Baxter permutations in $S_n$ with $k$ inverse ascents and $l$ inverse descents. [9]

(D) Non-intersecting lattice paths from $A_1 = (0, 2)$, $A_2 = (1, 1)$, and $A_3 = (2, 0)$ to $B_1 = (k, l + 2)$, $B_2 = (k + 1, l + 1)$, $B_3 = (k + 2, l)$, which we will call $(k,l)$-Baxter paths. [5]

(E) Standard Young tableaux of shape $3 \times n$ with no consecutive entries in any row, and $k$ instances of $(i, i + 1)$ in the union of the first and third row, which we will call Baxter tableaux. [4]

<footnote>†Funded by NSF GRFP</footnote>
(F) Diagonal rectangulations of size $n$, where $k$ is the number of times the interior of the diagonal is intersected vertically, and $\ell$ is the number of times it is intersected horizontally. [9]

(G) Plane partitions in a $k \times l \times 3$ box, which we will call *Baxter plane partitions*.

Baxter permutations are those that avoid the patterns 3-14-2 and 2-41-3, where an occurrence of the pattern 3-14-2 in a permutation $w = w_1 \dots w_n$ means there exists a quadruple of indices $\{i, j, j+1, k\}$ with $i < j < j+1 < k$ and $w_j < w_k < w_i < w_{j+1}$ (and similarly for 2-41-3). For example, 25314 contains an instance of the pattern 2413, but not 2-41-3. For $n=4$, there are $B(4) = 22$ Baxter permutations in $S_4$, with the only excluded ones being 2413 and 3142. Twisted Baxter permutation have a syntactically similar definition, being those that avoid 2-41-3 and 3-41-2. Call these larger sets counted by $B(n)$ a set of *Baxter objects of order $n$*, and their subsets counted by $\Theta_{k,\ell}$ a set of *Baxter objects of order $(k,\ell)$*. Each of these subsets has a natural involution that preserves $k$ and $\ell$:

* Conjugation by the longest permutation $w_0$ for (A), (B), and (C).

* Rotation by $180^\circ$ about a central point for (D) and (F)

* Schützenberger evacuation for (E), which in the special case of a rectangular tableaux with $N$ boxes corresponds to rotating the tableaux $180^\circ$ and then replacing every label $i$ with $N+1-i$.

* Taking the complement of a plane partition in the $k \times l \times 3$ box for (G).

Since Baxter permutations are closed under taking inverses [9], the map $w \mapsto w^{-1}$ provides an obvious bijection between Baxter objects (A) and (B). There are known bijections between the Baxter objects (A), (D) and (E) (see [4][5]), between the objects (B), (C) and (F) (see [9]). We will also show the equivalence of objects (D) and (G). Section 2 is devoted to the following theorem:

**Theorem 1.** *The given bijections between the above 7 classes of Baxter objects of order $(k,\ell)$, commute with their respective involutions.*

Since the bijections commute with the respective involutions, this means the number of Baxter objects of order $(k,\ell)$ fixed under involution is the same for all 7 classes of Baxter objects. Denote this common number $\Theta_{k,\ell}$. Also, we introduce the $q$-analogue of $\Theta_{k,\ell}$,

$$ \Theta_{k,\ell}(q) := \frac{\begin{bmatrix} n+1 \\ k \end{bmatrix}_q \begin{bmatrix} n+1 \\ k+1 \end{bmatrix}_q \begin{bmatrix} n+1 \\ k+2 \end{bmatrix}_q}{\begin{bmatrix} n+1 \\ 1 \end{bmatrix}_q \begin{bmatrix} n+1 \\ 2 \end{bmatrix}_q} \qquad (2) $$

$$ \text{where } n = k + \ell + 1, \begin{bmatrix} n \\ i \end{bmatrix}_q = \frac{[n]_q!}{[k]_q! [n-k]_q!}, [m]_q! = [m]_q [m-1]_q \dots [1]_q, \text{ and } [j]_q = 1 + q + \dots + q^{j-1}. $$

**Theorem 2.** *$\Theta_{k,\ell}(q)$ lies in $\mathbb{N}[q]$, has symmetric coefficients, and satisfies $[\Theta_{k,\ell}(q)]_{q=-1} = \Theta_{k,\ell}^\circ$.*

The proof of Theorem 2 is given in Section 3, using the theory of plane partitions.
# 2 Proof of Theorem 1

## 2.1 Objects (D) and (G)

A plane partition is an array $(\pi_{i,j})_{i,j \ge 1}$ of non-negative integers with finitely many non-zero entries that weakly increases along rows and columns. The plane partitions inside an $a \times b \times c$ box are those where $\pi_{i,j} \le c$, and $\pi_{i,j} = 0$ if $i > a$ or $j > b$. Its complement in the $a \times b \times c$ box is the plane partition given by $\pi'_{i,j} = c - \pi_{a-i,b-j}$ for $1 \le i \le a$ and $1 \le j \le b$ and $0$ elsewhere.

**Theorem 3.** There is a bijection between $(k, \ell)$ Baxter paths and plane partitions in a $k \times \ell \times 3$ box, which equivariantly takes conjugation by $w_0$ to taking the complement of a plane partition. (i)

*Proof*. Each individual lattice path from $A_i$ to $B_i$ naturally corresponds to a partition $\lambda_i$ inside of a $k \times \ell$ box, (our convention will be to take $\lambda_i$ to be the part of the $k \times \ell$ box with $A_i$ and $B_i$ as corners that lies above the given lattice path). The non-intersecting condition is equivalent to requiring $\lambda_3 \subseteq \lambda_2 \subseteq \lambda_1$, which is precisely the condition necessary for a triple of partitions to be a plane partition when stacked. Additionally, one can see the involution on lattice paths (which is 180° rotation) corresponds to taking $\lambda_3 \supseteq \lambda_2 \supseteq \lambda_1$ to $\lambda_1^c \subseteq \lambda_2^c \subseteq \lambda_3^c$, where $\lambda^c$ is the complement of $\lambda$ in the $k \times \ell$ box, which is the same as taking the complement of the plane partition in the $k \times \ell \times 3$ box. $\square$

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

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

For the rest of this extended abstract, most of the proofs will be sketched or omitted.

## 2.2 Objects (A), (D), and (E)

**Theorem 4** (Dulucq and Guibert [4]). There is a bijection between Baxter permutations with $k$ ascents and $\ell$ descents, and triples of non-intersecting lattice paths from the points $A_1 = (0, 2)$, $A_2 = (1, 1)$, and $A_3 = (2, 0)$ to $B_1 = (k+2, \ell)$, $B_2 = (k+1, \ell+1)$, and $B_3 = (k, \ell+2)$ equivariantly taking conjugation by $w_0$ to rotation by $180^\circ$.

Felsner, Fusy, Noy, and Orden [6] have additionally shown that this bijection (along with a number of other Baxter objects) are equivariant. One interesting Baxter family not included is $3 \times n$ standard Young tableaux with no consecutive entries in the same row.

Cori, Dulucq, and Viennot [3] begin by working with a larger set of objects, counted not by $B(n)$, but by $c_n^2$, where $c_n = \frac{1}{n+1} \binom{2n}{n}$ is the Catalan number. These larger sets of objects are Shuffle$_{2n}$ (the shuffling of two parenthesis languages), alternating Baxter permutations of length $2n$ (a Baxter permutation $w = w_1w_2\dots w_{2n}$ is alternating if $w_1 > w_2 < w_3 > w_4\dots$), and pairs of complete binary trees with $2n+1$ nodes, and they showed that they were all in bijection. Later, Dulucq and Guibert [4] added a bijection between Shuffle$_{2n}$ and stack words avoiding 22. A stack word is a word in the letters $\{1, 2, 3\}$ such that every letter occurs the same number of times, and for every prefix of the word, one has at least as many 2's as 3's, and at least as many 1's as 2's. A stack word of length $3n$ is equivalent to an encoding of a $3 \times n$ Young tableaux known as a Yamanouchi word, where the $i^{th}$ letter of the word tells you which row $i$ appears in the tableaux. For example, the Yamanouchi word corresponding to the Baxter tableaux appearing in Table 1 is 121321321323. Requiring that the stack word avoid 22 is equivalent to saying the corresponding tableaux has no consecutive entries in the middle row.

It is not immediately clear that all of these maps are necessarily equivariant with respect to the natural involutions. We will show that the original bijections of Cori, Dulucq, and Viennot on the objects

<footnote>(i) Thanks to Jang Soo Kim for helping make this connection</footnote>
counted by $c_n^2$ are equivariant with respect to their involutions. Then an equivariant bijection from the Baxter tableaux (or equivalently, stack words avoiding 11, 22, and 33) to a special subset of pairs of complete binary trees called the twin trees is obtained by restricting the equivariant bijection from stack words avoiding 22 to pairs of complete binary trees. Lastly, we show that the bijection between the twin trees and Baxter permutations is equivariant, making the composite map from Baxter tableaux to Baxter permutations equivariant.

**Theorem 5.** The bijection between alternating Baxter permutations of length $2n$ and $3 \times n$ standard Young tableaux with no consecutive entries in the middle row is equivariant with respect to conjugation by $w_0$ and evacuation.

We suppress the proof of this theorem, as it relies on technical and unenlightening case checking of the bijection between the two objects given by Dulucq and Guibert [4].

**Corollary 6.** The number of alternating Baxter permutations of length $2n$ fixed under conjugation by $w_0$ and the number of $3 \times n$ standard Young tableaux with no consecutive entries in the middle row fixed under evacuation are both equal to $c_n$, the Catalan number.

The proof is omitted in this extended abstract.

**Corollary 7.** The bijection between Baxter permutations with $k$ ascents and $\ell$ descents to $3 \times n$ standard Young tableaux with no consecutive entries in the same row (where $k$ entries in the top row have their successive label in the bottom row, and $\ell + 1$ entries in the top row do not) is equivariant with respect to conjugation by $w_0$ and evacuation.

(sketch). This comes from following a number of bijections of Dulucq and Guibert [4].

First, there is a bijection from Baxter permutations to a subset of the pairs of complete binary trees called the twin trees. These are pairs of complete binary trees whose pattern of left leaves and right leaves read left-to-right (excluding the left-most left leaf and right-most right leaf) are complementary. Reading from left to right, we label left leaves and 0 and right leaves as 1 to produce the leaf code. An example is shown in Figure 1.

There is a canonical bijection between complete binary trees and the truncated trees that are obtained by removing all of the leaves from a complete binary tree. The bijection between Baxter permutations and twin trees consists of taking the increasing and decreasing binary trees [10, §1.2] of a Baxter permutation to get a pair of truncated trees, and then adding on leaves via the canonical bijection to get a pair of twin trees. From this, one can see that a permutation with $k$ ascents will correspond to a pair of twin trees whose left tree has a leaf code with $k$ 0's.

The natural involution on pairs of trees is to do a mirror reflection of each tree, and then swap the left and right trees. Since this map comes from decreasing and increasing trees, it is easy to check it will be equivariant with respect to conjugation by $w_0$ on permutations and the involution on pairs of trees.

Secondly, the bijection from the twin trees to $3 \times n$ standard Young tableaux with no consecutive entries in any row is obtained by just restricting the map from all pairs of complete binary trees to $3 \times n$ standard Young tableaux with no consecutive entries in the middle row. Since that map was equivariant with respect to the involutions, so will the restricted map. $\square$ $\square$
## 2.3 Objects (B) and (C)

There is another class of Baxter objects introduced by Reading called twisted Baxter permutations. While Baxter permutations avoid the patterns 3-14-2 and 2-41-3, twisted Baxter permutations avoid the patterns 3-41-2 and 2-41-3. Even though the two pairs of patterns look similar, it is not immediately obvious that they should be so closely related. Section 8 of Law and Reading's paper provides a bijection between the two that relies on looking at fibers of the lattice congruence $Θ_{3412}$ [9].

We suppress the details in this extended abstract, but one can easily check that this bijection will preserve the number of inverse descents, and will also be equivariant with respect to conjugation by $w_0$.

## 2.4 Objects (C) and (F)

A diagonal rectangulation of size $n$ is a subdivision of an $n \times n$ square into $n$ rectangles (with lattice points for corners) such that the interior of every rectangle intersects a fixed diagonal of the square (see the tables at the end for examples with $n = 4$).

It is a relatively straightforward check to see that the bijection between twisted Baxter permutations and diagonal rectangulations given in Section 6 of Law and Reading [9] preserves the indicated statistic, and will equivariantly take conjugation by $w_0$ to $180^\circ$ rotation. We again have the intermediate object of pairs of twin trees.

For technical reasons, their map from twisted Baxter permutations to pairs of twin trees is equivalent to taking the increasing and decreasing trees of the inverse of the permutation to get truncated twin trees, and then adding leaves to get a pair of twin trees (they respectively call these the *upper* and *lower planar binary trees*). Conjugation by $w_0$ on twisted Baxter permutations will correspond to the same involution on pairs of trees as before. And if a Baxter permutation has $k$ inverse ascents, its inverse will have $k$ ascents, and the increasing tree will have $k$ left leaves (excluding the left-most one), preserving the statistic.

A diagonal rectangulation is made by gluing the two trees together. In particular, one draws the trees so that all the leaves are evenly spaced on the lowest level, and all intersections make right angles. Then the twin tree condition guarantees that if we turn the left tree upside-down, it will match up with the right tree.

<figure><img src="image_3.png" /><figcaption>Fig. 1: Map from Baxter permutations to twin trees, and the corresponding action under involution.</figcaption></figure>
to form a diagonal rectangulation (see Figure 2). It is then obvious that the involution on pairs of trees corresponds to 180° rotation on diagonal rectangulations, and that k left leaves in the left tree (excluding the left-most one) will correspond to the k vertical intersections with the interior of the diagonal.

<figure><img src="image_4.png" /><figcaption>Fig. 2: Map from twisted Baxter permutations to diagonal rectangulations</figcaption></figure>

## 3 Proof of Theorem 2

By Theorem 1, we only have to find the number of objects fixed under involution for one family of Baxter objects. The Baxter family for which this is easiest to do is Baxter plane partitions. MacMahon gave a closed formula for the generating function of plane partitions inside a box weighted by number of boxes.

**Theorem 8** ([11], Theorem 7.21.7). Fix a, b, and c. Then

$$ \sum_{\pi} q^{\lvert\pi\rvert} = \prod_{i=1}^{a} \prod_{j=1}^{b} \prod_{k=1}^{c} \frac{[i+j+k-1]_q}{[i+j+k-2]_q} \qquad (3) $$

where $\pi$ runs over all plane partitions that fit in a $a \times b \times c$ box.

We will write the above sum as $M(a, b, c; q)$. One can check that for Baxter plane partitions, this gives the previously defined q-analogue of $\Theta_{k,l}$.
**Corollary 9.**

$$M(k, \ell, 3; q) = \sum_{\pi} q^{\lvert\pi\rvert} = \frac{\begin{bmatrix} n+1 \\ k \end{bmatrix}_q \begin{bmatrix} n+1 \\ k+1 \end{bmatrix}_q \begin{bmatrix} n+1 \\ k+2 \end{bmatrix}_q}{\begin{bmatrix} n+1 \\ 1 \end{bmatrix}_q \begin{bmatrix} n+1 \\ 2 \end{bmatrix}_q} = \Theta_{k,\ell}(q) \quad (4)$$

where $\pi$ runs over all plane partitions that fit in a $k \times \ell \times 3$ box.

In particular, this tells us that $\Theta_{k,\ell}(q)$ is indeed a polynomial with symmetric, non-negative integer coefficients, which is not immediately obvious from the definition.

Additionally, we have the following special case of a theorem of Stembridge.

**Theorem 10** (Stembridge, Example 2.1, [12]). *The number of self-complementary plane partitions that fit inside an $a \times b \times c$ box is $M(a, b, c; -1)$, that is to say, the generating function for plane partitions in the box weighted by size and then evaluated at $q = -1$.*

By setting $c = 3$, we get the following result.

**Theorem 11.** $\Theta_{k,\ell}^{\circ} = [\Theta_{k,\ell}(q)]_{q=-1}$

Although Theorem 11 follows from Stembridge's result without any further computation, it turns out that it agrees with formulas for $\Theta_{k,\ell}^{\circ}$ given previous by Felsner, Fusy, Orden, and Noy [6], after correcting one of the cases of their formula, and applying a hypergeometric summation, as we explain next.

**Theorem 12.** 1. If $k$ and $\ell$ are odd, then $\Theta_{k,\ell}^{\circ} = 0$

2. If $k$ and $\ell$ are even, with $k = 2\kappa$ and $\ell = 2\lambda$, then for $N = \kappa + \lambda$,

$$\Theta_{2\kappa, 2\lambda}^{\circ} = \sum_{r \ge 0} \frac{2r^3}{(N+1)(N+2)^2} \binom{N+2}{\kappa+1} \binom{N+2}{\kappa-r+1} \binom{N+2}{\kappa+r+1} = \frac{\binom{N+1}{\kappa} \binom{N+1}{\kappa+1} \binom{N}{\kappa}}{(N+1)}$$

3. If $k$ is odd and $\ell$ is even, with $k = 2\kappa + 1$ and $\ell = 2\lambda$, then for $N = \kappa + \lambda$, (ii)

$$\begin{align}
\Theta_{2\kappa+1, 2\lambda}^{\circ} &= \Theta_{2\kappa, 2\lambda}^{\circ} + \sum_{r \ge 1} \frac{(\lambda - r + 1)r(r+1)(2r+1)}{(\kappa + 2 + r)(N+1)(N+2)^2} \binom{N+2}{\kappa+1} \binom{N+2}{\kappa-r+1} \binom{N+2}{\kappa+r+1} \nonumber \\
&= \frac{\binom{N+1}{\kappa} \binom{N+1}{\kappa} \binom{N+1}{\kappa+1}}{(N+1)} \tag{5}
\end{align}$$

4. If $k$ is even and $\ell$ is odd, then switch $k$ and $\ell$ in Equation 5.

(sketch). For assertion 1, when $k$ and $\ell$ are both odd, one can see $\Theta_{k,\ell}^{\circ} = 0$, since for example, looking at the plane partition model, the $k \times \ell \times 3$ box has an odd number of boxes, so the size of any plane partition in that box must have opposite parity of its complement. Correspondingly, one can check that $[\Theta_{k,\ell}(q)]_{q=-1} = 0$. In this case, the denominator of Equation (2) only has one factor of $1+q$, coming

<footnote>(ii) This corrects Proposition 7.4, part iii in Felsner, Fusy, Orden, and Noy</footnote>
from $\begin{bmatrix} n+1 \\ 1 \end{bmatrix}_q$, whereas the numerator will have two factors of $(1+q)$, coming from each of $\begin{bmatrix} n+1 \\ k \end{bmatrix}_q$ and $\begin{bmatrix} n+1 \\ k+2 \end{bmatrix}_q$.

For assertion 2, when $k$ and $\ell$ are both even, the summation is (after factoring out the constant term) the hypergeometric series

$$ {}_5F_4 \begin{bmatrix} 2 & 2 & 2 & -\kappa, & -\lambda \\ 1 & 1 & \kappa+3 & \lambda+3 & 1 \end{bmatrix}, $$

where we recall that a hypergeometric series with parameters $a_1, \dots, a_r, b_1, \dots, b_s$ is defined to be

$$ {}_rF_s \begin{bmatrix} a_1 & a_2 & \dots & a_r \\ b_1 & b_2 & \dots & b_s \end{bmatrix} z = \sum_{n=1}^{\infty} \frac{(a_1)_n \dots (a_r)_n}{(b_1)_n \dots (b_s)_n} z^n, $$

for $(x)_n = x(x-1)\dots(x-n+1)$.

This hypergeometric series can be evaluated using the formula for a well-poised ${}_5F_4$ [1, (4.4.1) p.27],

$$ {}_5F_4 \begin{bmatrix} a & \frac{1}{2}a+1 & c & d & e \\ & \frac{1}{2}a & 1+a-c & 1+a-d & 1+a-e \end{bmatrix} \quad (6) \\ = \frac{\Gamma(1+a-c)\Gamma(1+a-d)\Gamma(1+a-e)\Gamma(1+a-c-d-e)}{\Gamma(1+a)\Gamma(1+a-d-e)\Gamma(1+a-c-e)\Gamma(1+a-c-d)} $$

by choosing $a=c=2$, $d=-\kappa$, and $e=-\lambda$.

For assertion 3, when $k$ is odd and $\ell$ is even, the summation is (again, after factoring out the constant term) the hypergeometric series

$$ {}_4F_3 \begin{bmatrix} 3, & 5/2, & 1-\lambda, & -\kappa; \\ & 3/2, & \lambda+3, & \kappa+4 \end{bmatrix} $$

which can also be evaluated using Equation (6), but with choice of parameters $a=3$, $c=1-\lambda$, $d=-\kappa$, and $e=2$ (note that as $e=1+a-e$, the ${}_5F_4$ reduces to a ${}_4F_3$).

Lastly, for assertion 4, we exploit natural symmetry that forces $\Theta_{k,\ell}^{\phi} = \Theta_{\ell,k}^{\phi}$. $\square$ $\square$

# 4 A possible q-Baxter number

We have a $q$-analog for $\Theta_{k,\ell}$, and we would like to extend it to a $q$-analog for Baxter numbers. A natural way in which one can generalize is inspired by Hoggatt sums [7]. Let $H(m, k, \ell)$ be the number of plane partitions that fit in a $k \times \ell \times m$ box, which we will call the *MacMahon numbers*. Via MacMahon's plane partition formula given in Equation (3), these can be simply expressed as

$$ H(m, k, \ell) = \frac{\prod_{i=0}^{m-1} \binom{k+\ell}{k+i}}{\prod_{j=1}^{m-1} \binom{k+\ell}{j}}. \qquad (7) $$

We also consider a natural $q$-shift of MacMahon's formula,

$$ H(m, k, \ell; q) = q^{m \binom{k+1}{2}} \sum_{\pi} q^{\lvert \pi \rvert}, \qquad (8) $$
where we sum over all plane partitions $\pi$ in a $k \times \ell \times m$ box. Note that $H(m, k, \ell, 1) = H(m, k, \ell)$.

We will define the *Hoggatt sum* and *q-Hoggatt sum* to respectively be

$$H(n, m) = \sum_{k+\ell=n} H(m, k, \ell)$$

$$H(n, m; q) = \sum_{k+\ell=n} H(m, k, \ell; q)$$

**Proposition 13.** *H(n, m; q) has symmetric coefficients as a polynomial in q.*

This fact is elementary to prove, and the proof will be suppressed in this extended abstract.

For $m = 1$, the MacMahon numbers are $H(1, k, \ell) = \binom{k+\ell}{k}$, the binomial coefficients, with $q$-analogue $H(1, k, \ell; q) = q^{\binom{k+1}{2}} \begin{bmatrix} k+\ell \\ k \end{bmatrix}_q$. The Hoggatt sum is $H(n, 1) = 2^n$, and the $q$-Hoggatt sum is $H(n, 1; q) = \sum_{k=0}^n q^{\binom{k+1}{2}} \begin{bmatrix} n \\ k \end{bmatrix}_q = (-q; q)_{n+1} = (1+q)(1+q^2)\dots(1+q^n)$.

For $m = 2$, the MacMahon numbers are $H(2, k, \ell) = \frac{1}{k+\ell} \binom{k+\ell}{k} \binom{k+\ell}{k+1}$, the Narayana numbers, with $q$-analogue $H(k, \ell, 2; q) = \frac{q^{k+2+k}}{[k+\ell]_q} \begin{bmatrix} k+\ell \\ k \end{bmatrix}_q \begin{bmatrix} k+\ell \\ k+1 \end{bmatrix}_q$ the $q$-Narayana numbers. The Hoggatt sum is $H(n, 2) = \frac{1}{n+1} \binom{2n}{n}$, the Catalan number, whereas the $q$-Hoggatt sum is $H(n, 2; q) = \frac{1}{[n+1]_q} \begin{bmatrix} 2n \\ n \end{bmatrix}_q$, the $q$-Catalan number. [8]

For $m = 3$, the MacMahon numbers are $H(3, k, \ell) = \Theta_{k,\ell}$, with $q$-analogue $H(3, k, \ell; q) = \Theta_{k,\ell}(q)$. The Hoggatt sums are $H(n, 3) = B(n+1)$, the Baxter number, and so one might consider the third $q$-Hoggatt sum

$$H(n, 3; q) = \sum_{k+\ell=n} q^{3\binom{k+1}{2}} \Theta_{k,\ell}(q) \qquad (9)$$

as a $q$-Baxter number. However, we do not know if it has any nice combinatorial interpretations like the cases $m = 1, 2$. Also, it is not known whether $H(4, k, \ell; q)$ or $H(n, 4; q)$ has any nice combinatorial interpretation outside of plane partitions, as for $m \le 3$.

<caption>**Tab. 1:** Baxter objects of order $(k, \ell) = (3, 0)$</caption>

$$\begin{align*} \Theta_{k,\ell}(q) &= 1 \\ \Theta_{k,\ell}(1) &= 1 \\ \Theta_{k,\ell}(-1) &= 1 \end{align*}$$

<table><thead><tr><th>Baxter Permutations</th><th>Twisted Baxter Permutations</th><th>Baxter Paths</th><th>Baxter Tableaux</th><th>Diagonal Rectangulations</th><th>Baxter Plane Partitions</th></tr></thead><tbody><tr><td>1234<br>○</td><td>1234<br>○</td><td>○</td><td><table><tr><td>1</td><td>3</td><td>6</td><td>9</td></tr><tr><td>2</td><td>5</td><td>8</td><td>11</td></tr><tr><td>4</td><td>7</td><td>10</td><td>12</td></tr></table><br>○</td><td>○</td><td>○</td></tr><tr><td></td><td></td><td></td><td></td><td></td><td>○</td></tr></tbody></table>
<table><caption>**Tab. 2:** Baxter objects of order $(k, \ell) = (2, 1)$
$$ \Theta_{k,\ell}(q) = 1 + q + 2q^2 + 2q^3 + 2q^4 + q^5 + q^6 $$
$$ \Theta_{k,\ell}(1) = 10 $$
$$ \Theta_{k,\ell}(-1) = 2 $$</caption><thead><tr><th>Baxter<br>Permutations</th><th>Twisted Baxter<br>Permutations</th><th>Baxter<br>Paths</th><th>Baxter<br>Tableaux</th><th>Diagonal<br>Rectangulations</th><th>Baxter Plane<br>Partitions</th></tr></thead><tbody><tr><td>1243<br>↓<br>2134</td><td>1243<br>↓<br>2134</td><td>↓<br>↓<br>↓</td><td>1 3 6 9<br>2 5 7 11<br>4 8 10 12<br>↓<br>↓<br>↓</td><td>↓<br>↓<br>↓</td><td>3 3<br>↓<br>0 0</td></tr><tr><td>1342<br>↓<br>3124</td><td>1342<br>↓<br>3124</td><td>↓<br>↓<br>↓</td><td>1 3 6 9<br>2 4 8 11<br>5 7 10 12<br>↓<br>↓<br>↓</td><td>↓<br>↓<br>↓</td><td>3 2<br>↓<br>1 0</td></tr><tr><td>↓</td><td>↓</td><td>↓</td><td>↓</td><td>↓</td><td>↓</td></tr><tr><td>1423<br>↓<br>2314</td><td>1423<br>↓<br>2314</td><td>↓<br>↓<br>↓</td><td>1 3 5 7<br>2 6 9 11<br>4 8 10 12<br>↓<br>↓<br>↓</td><td>↓<br>↓<br>↓</td><td>3 1<br>↓<br>2 0</td></tr><tr><td>2341<br>↓<br>4123</td><td>2341<br>↓<br>4123</td><td>↓<br>↓<br>↓</td><td>1 4 6 9<br>2 5 8 11<br>3 7 10 12<br>↓<br>↓<br>↓</td><td>↓<br>↓<br>↓</td><td>2 2<br>↓<br>1 1</td></tr><tr><td>1324<br>○</td><td>1324<br>○</td><td>○<br>○<br>○</td><td>1 3 5 7<br>2 4 9 11<br>6 8 10 12<br>○<br>○<br>○</td><td>○<br>○<br>○</td><td>3 0<br>○</td></tr><tr><td>3412<br>○</td><td>3142<br>○</td><td>○<br>○<br>○</td><td>1 3 7 9<br>2 5 8 11<br>4 6 10 12<br>○<br>○<br>○</td><td>○<br>○<br>○</td><td>2 1<br>○</td></tr></tbody></table>
<table><caption>**Tab. 3:** Baxter objects of order $(k, \ell) = (1, 2)$
$$ \Theta_{k,\ell}(q) = 1 + q + 2q^2 + 2q^3 + 2q^4 + q^5 + q^6 $$
$$ \Theta_{k,\ell}(1) = 10 $$
$$ \Theta_{k,\ell}(-1) = 2 $$</caption><thead><tr><th>Baxter<br>Permutations</th><th>Twisted Baxter<br>Permutations</th><th>Baxter<br>Paths</th><th>Baxter<br>Tableaux</th><th>Diagonal<br>Rectangulations</th><th>Baxter Plane<br>Partitions</th></tr></thead><tbody><tr><td>1432<br>↓<br>3214</td><td>1432<br>↓<br>3214</td><td>↓<br>↓<br>↓</td><td><table><tr><td>1</td><td>3</td><td>6</td><td>9</td></tr><tr><td>2</td><td>4</td><td>7</td><td>11</td></tr><tr><td>5</td><td>8</td><td>10</td><td>12</td></tr></table><br>↓<br><table><tr><td>1</td><td>3</td><td>5</td><td>8</td></tr><tr><td>2</td><td>6</td><td>9</td><td>11</td></tr><tr><td>4</td><td>7</td><td>10</td><td>12</td></tr></table></td><td>↓<br>↓<br>↓</td><td>↓<br>↓<br>↓</td><td>2<br>2<br>↓<br>1<br>1</td></tr><tr><td>2431<br>↓<br>4213</td><td>2431<br>↓<br>4213</td><td>↓<br>↓<br>↓</td><td><table><tr><td>1</td><td>4</td><td>6</td><td>9</td></tr><tr><td>2</td><td>5</td><td>7</td><td>11</td></tr><tr><td>3</td><td>8</td><td>10</td><td>12</td></tr></table><br>↓<br><table><tr><td>1</td><td>3</td><td>5</td><td>10</td></tr><tr><td>2</td><td>6</td><td>8</td><td>11</td></tr><tr><td>4</td><td>7</td><td>9</td><td>12</td></tr></table></td><td>↓<br>↓<br>↓</td><td>↓<br>↓<br>↓</td><td>3<br>2<br>↓<br>1<br>0</td></tr><tr><td>3241<br>↓<br>4132</td><td>3241<br>↓<br>4132</td><td>↓<br>↓<br>↓</td><td><table><tr><td>1</td><td>4</td><td>6</td><td>8</td></tr><tr><td>2</td><td>5</td><td>9</td><td>11</td></tr><tr><td>3</td><td>7</td><td>10</td><td>12</td></tr></table><br>↓<br><table><tr><td>1</td><td>3</td><td>6</td><td>10</td></tr><tr><td>2</td><td>4</td><td>8</td><td>11</td></tr><tr><td>5</td><td>7</td><td>9</td><td>12</td></tr></table></td><td>↓<br>↓<br>↓</td><td>↓<br>↓<br>↓</td><td>3<br>1<br>↓<br>2<br>0</td></tr><tr><td>3421<br>↓<br>4312</td><td>3421<br>↓<br>4312</td><td>↓<br>↓<br>↓</td><td><table><tr><td>1</td><td>4</td><td>7</td><td>9</td></tr><tr><td>2</td><td>5</td><td>8</td><td>11</td></tr><tr><td>3</td><td>6</td><td>10</td><td>12</td></tr></table><br>↓<br><table><tr><td>1</td><td>3</td><td>7</td><td>10</td></tr><tr><td>2</td><td>5</td><td>8</td><td>11</td></tr><tr><td>4</td><td>6</td><td>9</td><td>12</td></tr></table></td><td>↓<br>↓<br>↓</td><td>↓<br>↓<br>↓</td><td>3<br>3<br>↓<br>0<br>0</td></tr><tr><td>2143<br>○</td><td>2143<br>○</td><td>○</td><td><table><tr><td>1</td><td>3</td><td>6</td><td>8</td></tr><tr><td>2</td><td>4</td><td>9</td><td>11</td></tr><tr><td>5</td><td>7</td><td>10</td><td>12</td></tr></table><br>○<br><table><tr><td>1</td><td>4</td><td>6</td><td>10</td></tr><tr><td>2</td><td>5</td><td>8</td><td>11</td></tr><tr><td>3</td><td>7</td><td>9</td><td>12</td></tr></table></td><td>○<br>○<br>○</td><td>○<br>○<br>○</td><td>2<br>1<br>○</td></tr><tr><td>4231<br>○</td><td>4231<br>○</td><td>○</td><td><table><tr><td>1</td><td>4</td><td>6</td><td>10</td></tr><tr><td>2</td><td>5</td><td>8</td><td>11</td></tr><tr><td>3</td><td>7</td><td>9</td><td>12</td></tr></table><br>○<br><table><tr><td>1</td><td>4</td><td>6</td><td>10</td></tr><tr><td>2</td><td>5</td><td>8</td><td>11</td></tr><tr><td>3</td><td>7</td><td>9</td><td>12</td></tr></table></td><td>○<br>○<br>○</td><td>○<br>○<br>○</td><td>3<br>0<br>○</td></tr></tbody></table>
<caption>Tab. 4: Baxter objects of order $(k, \ell) = (0, 3)$</caption>

$$ 
\begin{aligned}
\Theta_{k,\ell}(q) &= 1 \\
\Theta_{k,\ell}(1) &= 1 \\
\Theta_{k,\ell}(-1) &= 1
\end{aligned}
 $$

<table><thead><tr><th>Baxter Permutations</th><th>Twisted Baxter Permutations</th><th>Baxter Paths</th><th>Baxter Tableaux</th><th>Diagonal Rectangulations</th><th>Baxter Plane Partitions</th></tr></thead><tbody><tr><td>4321<br> men</td><td>4321<br> men</td><td>men</td><td>1 4 7 10<br>2 5 8 11<br>3 6 9 12</td><td>men</td><td>0<br> men</td></tr></tbody></table>

Acknowledgements

The author would like to thank Nathan Reading, Jang Soo Kim for helping make the connection to plane partitions, Dennis Stanton for helping with hypergeometric series references, and to his adviser Vic Reiner for suggesting the problem and for numerous helpful discussions.

References

[1] W. Bailey. *Generalized Hypergeometric Series*. Cambridge University Press, 1935.

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

[3] R. Cori, S. Dulucq, and G. Viennot. Shuffle of parenthesis systems and Baxter permutations. *J. Comb. Theory, Ser. A*, 43:1–22, 1986.

[4] S. Dulucq and O. Guibert. Stack words, standard permutations, and Baxter permutations. *Discrete Mathematics*, 157:91–106, 1996.

[5] S. Dulucq and O. Guibert. Baxter permutations. *Discrete Mathematics*, 180:143–156, 1998.

[6] S. Felsner, E. Fusy, M. Noy, and D. Orden. Bijections for Baxter families and related objects. *J. Comb. Theory, Ser. A*, 118(3):993–1020, 2011.

[7] D. Fielder and C. Alford. On a conjecture by Hoggatt with extensions to Hoggatt sums and Hoggatt triangles. *The Fibonacci Quarterly*, 27(2):160–168, May 1989.

[8] J. Fürlinger and J. Hofbauer. q-catalan numbers. *J. Comb. Theory, Ser. A*, 2:248–264, 1985.

[9] S. Law and N. Reading. The Hopf algebra of diagonal rectangulations. *J. Comb. Theory, Ser. A*, 2011. To appear.

[10] R. Stanley. *Enumerative Combinatorics, Volume 1*. Cambridge University Press, 2nd edition, 2000.

[11] R. Stanley. *Enumerative Combinatorics, Volume 2*. Cambridge University Press, 2001.
[12] J. Stembridge. On minuscule representations, plane partitions, and involutions in complex Lie groups. *Duke Mathematics Journal*, 73(2):469–490, 1994.