% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P2.48}{22(2)}{2015} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins \usepackage{mathrsfs} \usepackage{url} \usepackage{verbatim} \input xy \xyoption{all} \usepackage{graphicx} \usepackage{tikz} \usepackage{tkz-graph} \usepackage{multicol} \usepackage{enumerate} \usepackage{mathtools} \usepackage{url} \usepackage{hyperref} \usepackage{breakurl} \allowdisplaybreaks[1] \usepackage{mathdots} \newcommand\subdot{\mathrel{\ooalign{$\subseteq$\cr \hidewidth\hbox{\scalebox{1.5}{$\cdot\mkern1mu$}}\cr}}} %%%%% For bibliography typesetting... ignore underfull hboxes \usepackage{etoolbox} \apptocmd{\sloppy}{\hbadness 10000\relax}{}{} % Theorem environments with italic font \newtheorem{thm}{Theorem}[section] \newtheorem{lemma}[thm]{Lemma} \newtheorem{claim}[thm]{Claim} \newtheorem{cor}[thm]{Corollary} \newtheorem{prop}[thm]{Proposition} \newtheorem{conj}[thm]{Conjecture} \newtheorem{question}[thm]{Question} \newtheorem{fact}[thm]{Fact} % Theorem environments with roman font (use lower-case version in body % of text, e.g., \begin{example} rather than \begin{Example}) \newtheorem{Definition}[thm]{Definition} \newenvironment{definition} {\begin{Definition}\rm}{\end{Definition}} \newtheorem{Example}[thm]{Example} \newenvironment{example} {\begin{Example}\rm}{\end{Example}} \newtheorem{Remark}[thm]{Remark} \newenvironment{remark} {\begin{Remark}\rm}{\end{Remark}} \numberwithin{equation}{section} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf A note on statistical averages for oscillating tableaux} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Sam Hopkins \qquad Ingrid Zhang\\ \small Department of Mathematics\\[-0.8ex] \small Massachusetts Institute of Technology\\[-0.8ex] \small Cambridge MA, 02139, U.S.A. \\ \small\tt \{shopkins,ingridz\}@mit.edu\\ } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Aug 28, 2014}{May 28, 2015}{Jun 15, 2015}\\ \small Mathematics Subject Classifications: 05A17, 05E18} \begin{document} \maketitle % E-JC papers must include an abstract. The abstract should consist of a % succinct statement of background followed by a listing of the % principal new results that are to be found in the paper. The abstract % should be informative, clear, and as complete as possible. Phrases % like "we investigate..." or "we study..." should be kept to a minimum % in favor of "we prove that..." or "we show that...". Do not % include equation numbers, unexpanded citations (such as "[23]"), or % any other references to things in the paper that are not defined in % the abstract. The abstract will be distributed without the rest of the % paper so it must be entirely self-contained. \begin{abstract} Oscillating tableaux are certain walks in Young's lattice of partitions; they generalize standard Young tableaux. The shape of an oscillating tableau is the last partition it visits and the length of an oscillating tableau is the number of steps it takes. We define a new statistic for oscillating tableaux that we call weight: the weight of an oscillating tableau is the sum of the sizes of all the partitions that it visits. We show that the average weight of all oscillating tableaux of shape $\lambda$ and length $|\lambda|+2n$ (where $|\lambda|$ denotes the size of $\lambda$ and $n \in \mathbb{N}$) has a surprisingly simple formula: it is a quadratic polynomial in $|\lambda|$ and $n$. Our proof via the theory of differential posets is largely computational. We suggest how the homomesy paradigm of Propp and Roby may lead to a more conceptual proof of this result and reveal a hidden symmetry in the set of perfect matchings. \end{abstract} % keywords are optional \bigskip\noindent \textbf{Keywords:} oscillating tableaux; homomesy \section{Introduction} In this note, we follow the standard notation for partitions as laid out in~\cite[\S7.2]{stanley2}. Recall that Young's lattice is the poset of all partitions partially ordered by inclusion of Young diagrams. We write $\mu \subdot \lambda$ to mean that $\lambda$ covers $\mu$ in Young's lattice; that is, we write~$\mu \subdot \lambda$ to mean that the Young diagram of $\lambda$ is obtained from that of $\mu$ by the addition of a box. A \emph{walk in (the Hasse diagram of) Young's lattice} is a sequence of partitions $(\lambda^{0},\lambda^{1},\ldots,\lambda^{l})$ such that for all $1 \leq i \leq l$ we have $\lambda^{i-1} \subdot \lambda^{i}$ or~$\lambda^{i} \subdot \lambda^{i-1}$. An \emph{oscillating tableau of shape $\lambda$ and length $l$} is a walk $T = (\lambda^{0},\lambda^{1},\ldots,\lambda^{l})$ in Young's lattice such that $\lambda^{0} = \emptyset$ and $\lambda^{l} = \lambda$. We use $\mathcal{OT}(\lambda,l)$ to denote the set of oscillating tableaux of shape $\lambda$ and length~$l$. Recall that $|\lambda|$ denotes the size of $\lambda$. Oscillating tableaux are a generalization of standard Young tableaux (SYT): it is not hard to see that $\#\mathcal{OT}(\lambda,|\lambda|) = f^{\lambda}$, the number of SYT of shape $\lambda$. The numbers $f^{\lambda}$ are easily computed thanks to the famous hook-length formula~\cite[Corollary 7.21.6]{stanley2}. In fact, the number of oscillating tableaux of arbitrary shape and length may be expressed in terms of these $f^{\lambda}$. \begin{thm} \label{thm:count} Let $|\lambda|=k$. Then for all $n \in \mathbb{N}$, \[\#\mathcal{OT}(\lambda,k+2n) = \binom{2n+k}{k}(2n-1)!! f^{\lambda}.\] On the other hand, if $l \neq k + 2n$ for some $n \in \mathbb{N}$ then $\#\mathcal{OT}(\lambda,l) = 0$. \end{thm} Above, $(2n-1)!! := 1\cdot3\cdot5\cdots(2n-1)$, which is $1$ if $n=0$. The last sentence in Theorem~\ref{thm:count} is clear because if $(\lambda^{0},\ldots,\lambda^{l})$ is a walk in Young's lattice then~$|\lambda^{l}| \leq |\lambda^{0}| + l$ and~$|\lambda^{l}| - |\lambda^{0}| \equiv l \bmod 2$. Several different approaches have been developed to prove this theorem. A bijective proof is given in~\cite[Lemma 8.7]{sundaram}. Roby~\cite[\S4.2]{roby} explains how the theory of growth diagrams, initiated by Fomin~\cite{fomin}, also yields a bijective proof. Another elegant approach to this formula is via the theory of differential posets developed by Stanley~\cite{stanley1}~\cite[Theorem 8.7]{stanley3}; this is the approach we will follow in investigating certain statistical averages for oscillating tableaux. To some extent, oscillating tableaux have been studied in the context of combinatorial statistics; for example, Chen~et.~al.~\cite{chen} used tableaux to prove the symmetry of maximal crossing number and maximal nesting number in set partitions. Here we are interested in a statistic on tableaux that we term weight. To our knowledge this statistic has not been explored in previous research. It turns out that there is a surprisingly simple formula for the average weight across all oscillating tableaux of given shape and length. For~$T \in \mathcal{OT}(\lambda,l)$, define the \emph{weight} of $T$, denoted $\mathrm{wt}(T)$, to be the sum of the sizes of all partitions that $T$ visits; that is, if $T = (\lambda^{0},\ldots,\lambda^{l})$ then we set~$\mathrm{wt}(T) := \sum_{i=0}^{l} |\lambda^{i}|$. \begin{thm} \label{thm:main} Let $|\lambda| = k$. Then for all $n \in \mathbb{N}$, \[ \frac{1}{\# \mathcal{OT}(\lambda,k+2n)} \sum_{T \in \mathcal{OT}(\lambda,k+2n)} \mathrm{wt}(T) = \frac{1}{6}(4n^2 + 3k^2 + 8 kn + 2n +3k).\] \end{thm} If we instead calculate the average size of a partition in a uniformly random oscillating tableau of given shape and length, we arrive at the following extremely simple formula. \begin{cor} \label{cor:main} Let $|\lambda| = k$. Then for all $n \in \mathbb{N}$, \[ \frac{1}{\# \mathcal{OT}(\lambda,k+2n)\cdot(2n+k+1)} \sum_{T \in \mathcal{OT}(\lambda,k+2n)} \mathrm{wt}(T) = \frac{n}{3} + \frac{k}{2}.\] \end{cor} The fact that the average in Theorem~\ref{thm:main} depends only on $k$ and $n$, and not $\lambda$, is conceivable in light of Theorem~\ref{thm:count}, which says that the dependence of~$\#\mathcal{OT}(\lambda,k+2n)$ on~$\lambda$ is slight. Still, it is unclear why this average should be a polynomial in $k$ and $n$ and why there should be a constant $\kappa$ such that $\kappa$ times this average is integral for all $\lambda$ and all $n$. Note that \[ \frac{1}{2}(4n^2 + 3k^2 + 8 kn + 2n +3k) = (n+(k+1)/2)(2n+3k)\] is integral for all $n,k \in \mathbb{N}$, so we may take $\kappa = 3$. It is especially unclear why such a small choice of $\kappa$ should work. The proof of Theorem~\ref{thm:main} we give in Section~\ref{sec:proof}, essentially a mysterious computation using differential poset operators, is unilluminating in this regard. In Section~\ref{sec:homomesy} we suggest how the recent homomesy paradigm of Propp and Roby~\cite{propp} might lead to a more explanatory proof of Theorem~\ref{thm:main}. Homomesy says, roughly, that ``small denominators in statistical averages of combinatorial objects should be explained by group actions.'' The possibility of such a proof points towards a hidden $\mathfrak{S}_3$-symmetry in the set of perfect matchings, as well as potentially the first instance of homomesy involving a non-cyclic group. (The potential for a non-cyclic homomesy arises from the three natural statistics for perfect matchings: number of crossings, number of nestings, and number of alignments. These statistics are not symmetrically distributed but may nevertheless be simultaneously homomesic under an $\mathfrak{S}_3$-action.) One might hope to extend Theorem~\ref{thm:main} to skew oscillating tableaux. A \emph{skew oscillating tableau of shape $\lambda/\mu$ and length $l$} is a walk $T = (\lambda^{0},\lambda^{1},\ldots,\lambda^{l})$ in Young's lattice such that~$\lambda^{0} = \mu$ and $\lambda^{l} = \lambda$. See~\cite[Corollary 4.2.11]{roby} for a formula enumerating such tableaux. However, computation carried out with Sage mathematical software~\cite{sage-combinat} suggests that there is not as simple a formula for the average weight of such tableaux for arbitrary~$\mu$; in particular, it appears that the denominator of the average is unbounded in this case. \medskip \section{Proof of Theorem~\ref{thm:main}} \label{sec:proof} To prove Theorem~\ref{thm:main}, we apply the theory of differential posets~\cite{stanley1}~\cite[Chapter 8]{stanley3}. Let~$V$ be the vector space of linear combinations of partitions and define two linear operators~$U,D\colon V \to V$ by \begin{align*} U(\mu) &:= \sum_{\mu \subdot \nu} \nu; \\ D(\mu) &:= \sum_{\nu \subdot \mu} \nu. \end{align*} These operators (which multiply right-to-left) satisfy the fundamental commutation identity~$DU - UD = I$. Following Stanley~\cite[Chapter 8]{stanley3}, define the numbers $b_{ij}(l) \in \mathbb{Z}$ by~$\left(U + D\right)^{l} = \sum_{i,j\geq 0} {b}_{ij}(l) U^iD^j$. Lemma 8.6 of~\cite{stanley3} shows that~$b_{i0}(l) = \binom{l}{i} (l-i-1)!!$ when $l-i$ is even. We basically mimic the proof of Lemma~8.6, but we expand a slightly more complicated expression that keeps track of tableaux weights. So let us similarly define $p_{ij}(l) \in \mathbb{Z}[x,x^{-1},y,y^{-1}]$ by \[ \left(y^{x D_x}xU + y^{x D_x}x^{-1}D\right)^{l} = \sum_{i,j\geq 0} p_{ij}(l) U^iD^j\] where $y^{x D_x}\colon \mathbb{Z}[x,x^{-1}] \to \mathbb{Z}[x,x^{-1},y,y^{-1}]$ is the $\mathbb{Z}$-linear map of rings $y^{x D_x}(x^n) := x^ny^n$. It is clear that the $p_{ij}(l)$ exist and are well defined. In addition, $p_{ij}(l) = x^{i-j}q_{ij}(l)$ for some unique $q_{ij}(l) \in \mathbb{Z}[y,y^{-1}]$. We adopt the shorter notation $\mathcal{T} := \mathcal{OT}(\lambda,k+2n)$. For~$v \in V$ and $\lambda$ a partition we use $[\lambda]v$ to denote the coefficient of $\lambda$ in $v$. Recall that~$\#\mathcal{T} = [\lambda] \left(U + D\right)^{k+2n} \cdot \, \emptyset$ because the coefficient of any partition $\mu$ in $ \left(U + D\right)^{k+2n} \cdot \, \emptyset$ is the number of ways we can take $k+2n$ steps (each either up or down) in Young's lattice from $\emptyset$ to arrive at $\mu$. Similarly, we have \[ \sum_{T \in \mathcal{T}} \mathrm{wt}(T) = [\lambda] \frac{\partial }{\partial y}\left(y^{x D_x}xU + y^{x D_x}x^{-1}D\right)^{k+2n}\bigg\rvert_{x=1,y=1} \cdot \, \emptyset. \] Here $x$ marks the size of the partition and $y$ marks the accumulated weight of the tableaux. Thus, defining $c_{ij}(l) \in \mathbb{Z}$ by~$c_{ij}(l) := \frac{\partial}{\partial y} (q_{ij}(l))\big\rvert_{y=1}$, we have $\# \mathcal{T} = b_{k,0}(k+2n)f^{\lambda}$ and~$\sum_{T \in \mathcal{T}} \mathrm{wt}(T) = c_{k,0}(k+2n) f^{\lambda}$. Theorem~\ref{thm:main} is therefore equivalent to \begin{equation} \frac{c_{k0}(k+2n)}{b_{k0}(k+2n)} = \frac{1}{3}\left(n+\frac{k+1}{2}\right)(2n+3k) \label{eqn:key} \end{equation} for all $k,n \geq 0$. Note that $DU - UD = I$ implies that $DU^{i} = U^{i}D + iU^{i-1}$ for all $i \geq 0$ (see~\cite[(8.6)]{stanley3}). From this it follows that \begin{align*} \sum_{i,j\geq 0} x^{i-j}q_{ij}(l+1) U^iD^j &= \left(y^{x D_x}xU + y^{x D_x}x^{-1}D\right) \sum_{i,j\geq 0} x^{i-j} q_{ij}(l) U^iD^j \\ &= \sum_{i,j \geq 0} x^{i-j+1}y^{i-j+1}q_{ij}(l) U^{i+1}D^j + x^{i-j-1}y^{i-j-1}q_{ij}(l) DU^{i}D^j \\ &= \sum_{i,j \geq 0} x^{i-j} y^{i-j}(q_{i-1,j}(l) + q_{i,j-1}(l-1) + (i+1)q_{i+1,j}(l-1)) U^{i}D^{j}. \end{align*} Equating the coefficients of $U^iD^j$ on both sides shows that the polynomials $q_{ij}(l)$ satisfy the recurrence \[ q_{ij}(l+1) = y^{i-j}(q_{i-1,j}(l) + q_{i,j-1}(l) + (i+1)q_{i+1,j}(l)).\] In particular, $q_{i0}(l+1) = y^{i}(q_{i-1,0}(l) + (i+1)q_{i+1,j}(l))$. Since~$q_{ij}(l)\big\rvert_{y=1} = b_{ij}(l)$, we also have the following recurrence in the $c$ numbers: \begin{equation} c_{i0}(l+1) = c_{i-1,0}(l) + (i+1)c_{i+1,0}(l)+ib_{i-1,0}(l) + i(i+1)b_{i+1,0}(l). \label{eqn:crecur} \end{equation} We will now prove that~(\ref{eqn:key}) holds by induction on $k+2n$. The base case of this induction is when $k = n = 0$. In this case,~(\ref{eqn:key}) holds because $c_{00}(0) = 0$. So now assume that at least one of $k$ or $n$ is strictly greater than zero and that~(\ref{eqn:key}) holds for smaller values of~$k+2n$. Then by~(\ref{eqn:crecur}), our inductive hypothesis, and~\cite[Lemma 8.6]{stanley3} we have \begin{align*} c_{k0}(k+2n) = \, &c_{k-1,0}(k-1+2n) +kb_{k-1,0}(k-1+2n) \\ &+ (k+1)c_{k+1,0}(k+1+2(n-1)) + k(k+1)b_{k+1,0}(k-1+2n)\\ =&\left(\frac{(n+\frac{k}{2})(2n+3(k-1))}{3}+k\right)b_{k-1,0}(k-1+2n) \\ &+ \left(\frac{(n-1+\frac{k+2}{2})(2(n-1)+3(k+1))}{3} + k\right)(k+1)b_{k+1,0}(k-1+2n) \\ =& \left( \frac{(n+\frac{k+1}{2})(2n+3k)}{3} -\frac{4}{3}n\right)b_{k-1,0}(k-1+2n) \\ &+ \left(\frac{(n+\frac{k+1}{2})(2n+3k)}{3} +\frac{2}{3}k\right)(k+1)b_{k+1,0}(k-1+2n) \\ =& \left(\frac{(n+\frac{k+1}{2})(2n+3k)}{3}\right) (b_{k-1,0}(k-1+2n) +(k+1)b_{k+1,0}(k-1+2n) ) \\ &+ \frac{2}{3} \Big(k(k+1)b_{k+1,0}(k-1+2n) -2nb_{k-1,0}(k-1+2n)\Big) \\ =& \left(\frac{(n+\frac{k+1}{2})(2n+3k)}{3}\right) b_{k,0}(k+2n) \\ &+ \frac{2}{3} \left( k(k+1)\binom{k-1+2n}{k+1}(2n-3)!! - 2n\binom{k-1+2n}{k-1}(2n-1)!!\right) \\ =& \left(\frac{(n+\frac{k+1}{2})(2n+3k)}{3} \right) b_{k,0}(k+2n). \end{align*} So~(\ref{eqn:key}) holds for $k$ and $n$. This completes the proof. \section{A better proof through homomesy?} \label{sec:homomesy} In the study of statistics on combinatorial objects, Propp and Roby~\cite{propp} recently introduced the paradigm of homomesy. \begin{definition} Let $\mathbf{k}$ be a field of characteristic zero. We say that the statistic $f:\mathcal{S} \to \mathbf{k}$ on a set of combinatorial objects $\mathcal{S}$ is \emph{homomesic} with respect to the action of a group~$G$ on~$\mathcal{S}$ if there is some $c \in \mathbf{k}$ such that~$\frac{1}{\#\mathcal{O}} \sum_{s \in \mathcal{O}} f(s) = c$ for each $G$-orbit $\mathcal{O}$. In other words, we say the statistic is homomesic with respect to $G$ if the average of $f$ is the same for each $G$-orbit. In this case we also say the triple $(\mathcal{S},G,f)$ exhibits homomesy. \end{definition} Propp and Roby point out how, like the cyclic-sieving phenomenon, the homomesy phenomenon is widespread in algebraic and enumerative combinatorics. Past research on homomesy has in general restricted to the case $G = \langle \varphi \rangle$ where $\varphi\colon \mathcal{S} \to \mathcal{S}$ is some combinatorially-meaningful procedure such as rowmotion in order ideals of posets~\cite{propp}~\cite{einstein} or promotion of Young tableaux~\cite{bloom}. The goal in such settings is to find natural statistics on $\mathcal{S}$ that are homomesic with respect to $\varphi$. However, we could take a different perspective whereby we have a certain statistic $f$ we want to understand better and search for some group~$G$ so that~$(\mathcal{S},f,G)$ exhibits homomesy. Of course, this is always possible by taking~$G$ to be the group of all invertible maps $\mathcal{S} \to \mathcal{S}$; but this is a trivial case in which there is only one $G$-orbit. The goal is to find a group $G$ of small size whose action explains an otherwise mysteriously small denominator in the average of the statistic across all of $\mathcal{S}$. If $f(\mathcal{S}) \subseteq \mathbb{Z}$ then this denominator is bounded by the order of $G$. In order to give a better proof of Theorem~\ref{thm:main} we would want to construct an action of~$C_3$, the cyclic group of order~$3$, on~$\mathcal{OT}(\lambda,k+2n)$ such that $\mathrm{wt}(\cdot)$ is homomesic with respect to this action. We might want this action to be free so that the size of each orbit is $3$; if so, we should assume $n \geq 2$ so that~$\#\mathcal{OT}(\lambda,k+2n)$ is always divisible by $3$. In this case we would want to prove that for each $C_3$-orbit $\mathcal{O}$ we have $\sum_{T \in \mathcal{O}} \mathrm{wt}(T) = \frac{1}{2} (4n^2 + 3k^2 + 8kn + 2n + 3k)$. We can make this request for a free cyclic action more precise via the relationship between oscillating tableaux and perfect matchings. We need to establish some preliminaries before we can state this relationship precisely in Theorem~\ref{thm:rs}. A \emph{perfect matching of $[2n]$} is a partition of the set $[2n] := \{1,2,\ldots,2n\}$ into pairs. Denote the set of perfect matchings of $[2n]$ by~$\mathcal{M}_{n}$. Let $M \in \mathcal{M}_n$ and choose~$p = \{\alpha,\beta\}$ and~$q = \{\gamma,\delta\} \in M$. Assume that~$\alpha<\beta$, $\gamma<\delta$ and~$\beta < \delta$. Then we say that $\{p,q\}$ is a \emph{crossing} of $M$ if~$\alpha < \gamma < \beta < \delta$. We say it is a \emph{nesting} if~$\gamma < \alpha < \beta <\delta$. Finally, we say it is an \emph{alignment} if it is neither a crossing nor a nesting. We will denote the number of crossings, nestings, and alignments of~$M$ by $\mathrm{cross}(M)$, $\mathrm{nest}(M)$, and $\mathrm{align}(M)$ respectively. Recall that a \emph{Dyck path of semilength $n$} is a lattice path in $\mathbb{Z}^2$ from $(0,0)$ to $(n,n)$ consisting of $n$ north steps of the form $(0,1)$ and $n$ east steps of the form $(1,0)$ that never goes below the diagonal $x=y$. Let~$\mathcal{D}_n$ denote the set of Dyck paths of semilength~$n$. We identify a Dyck path $D \in \mathcal{D}_n$ with its Dyck word, which is the binary word of length~$2n$ whose $i$th letter is $1$ if the $i$th step of $D$ is north and $0$ if it is east. The \emph{area} of $D \in \mathcal{D}_n$, denoted $\mathrm{area}(D)$, is the number of complete boxes of unit size below~$D$ and above the diagonal $x = y$. So for instance $\mathrm{area}(101010) = 0$, $\mathrm{area}(101100) = 1$, and~$\mathrm{area}(111000) = 3$. For $M \in \mathcal{M}_n$ and $\{i,j\} \in M$, if $i < j$ then we say $i$ is an \emph{opener} in~$M$ and $j$ is a \emph{closer} in~$M$. There is a natural surjection $\mathcal{M}_n \twoheadrightarrow \mathcal{D}_n$ given by~$M \mapsto D_M$ where the $i$th letter of $D_M$ is~$1$ if $i$ is an opener in $M$ and~$0$ if~$i$ is a closer in $M$. There is also a natural surjection $\mathcal{OT}(\emptyset,2n) \twoheadrightarrow \mathcal{D}_n$ given by $T = (\lambda^{0},\ldots,\lambda^{2n}) \mapsto D_T$ where the $i$th letter of $D_T$ is~$1$ if $\lambda^{i-1} \subdot \lambda^{i}$ and $0$ if $\lambda^{i} \subdot \lambda^{i-1}$. \begin{thm} \label{thm:rs} There is a bijection $RS\colon \mathcal{M}_n \xrightarrow{\sim} \mathcal{OT}(\emptyset,2n)$ such that $D_M = D_{RS(M)}$ for all~$M \in \mathcal{M}_n$. \end{thm} This bijection is due to Richard Stanley; but we call it $RS$ also because it is an extension of Robinson-Schensted insertion. A description of the bijection is given in~\cite[Lemma 8.3]{sundaram}. See also~\cite[\S5]{chen}. In light of Theorem~\ref{thm:rs} it makes sense to ask how the statistic weight for oscillating tableaux translates to perfect matchings. That question is answered by the following proposition. \begin{prop} \label{prop:stats} \hspace{2em} \begin{enumerate}[(a)] \item For all $M \in \mathcal{M}_n$ we have $\mathrm{align}(M) = \binom{n}{2} - \mathrm{area}(D_M)$. \item For all $T \in \mathcal{OT}(\emptyset,2n)$ we have $\mathrm{wt}(T) = 2\cdot\mathrm{area}(D_T) + n$. \end{enumerate} Thus for all $M \in \mathcal{M}_n$ we have $\mathrm{wt}(RS(M)) = n + 2\left(\binom{n}{2}-\mathrm{align}(M)\right)$. \end{prop} \noindent \emph{Proof}: Let $D \in \mathcal{D}_n$. For $1 \leq i \leq 2n$ define $b_i(D)$ to be the number of $1$s minus the number of $0$s in the subword consisting of the first $i$ letters of $D$. For $1 \leq i \leq n$ define $a_i(D) := b_j$ where $j$ is the position of the $i$th $0$ in $D$. If $T = (\lambda^{0},\ldots,\lambda^{2n})$ then~$b_i(D_T) = |\lambda^{i}|$ and therefore $\mathrm{wt}(T) = \sum_{i=1}^{2n} b_i(D_T)$. We also claim that $\mathrm{cross}(M) + \mathrm{nest}(M) = \sum_{i=1}^{n} a_i(D_M)$. This is because if the position of the $i$th $0$ in $D_M$ is $\beta$ and $\{\alpha,\beta\} \in M$ then \begin{align*} a_i(D_M) &= \# \{\{\gamma,\delta\} \in M\colon \gamma < \delta \textrm{ and } \gamma < \beta\} - \#\{\{\gamma,\delta\} \in M\colon \gamma < \delta \leq \beta\} \\ &= \# \{\{\gamma,\delta\} \in M \colon \alpha < \gamma < \beta < \delta \textrm{ or } \gamma < \alpha < \beta < \delta\}. \end{align*} Then~$\mathrm{align}(M) = \binom{n}{2} - \sum_{i=1}^{n} a_i(D_M)$ because $\mathrm{cross}(M) + \mathrm{nest}(M) + \mathrm{align}(M) = \binom{n}{2}$ for any~$M \in \mathcal{M}_n$. So the proposition amounts to showing~$\sum_{i=1}^{n} a_i(D) = \mathrm{area}(D)$ and~$\sum_{i=1}^{2n} b_i(D) = 2\mathrm{area}(D) + n$ for any $D \in \mathcal{D}_n$. This is true because it is true when~$D = 1010\cdots10$ and it remains true after replacing a consecutive subword of $01$ by $10$ in any Dyck word. $\square$ Moreover, for any four fixed positions~$\alpha < \beta < \gamma < \delta \in [2n]$ it is equally likely that these positions participate in a crossing, nesting, or alignment of a uniformly random matching $M \in \mathcal{M}_n$. Then by linearity of expectation the average number of alignments among all matchings is given by~$\frac{1}{\#\mathcal{M}_n} \sum_{M \in \mathcal{M}_n} \mathrm{align}(M) = \frac{1}{3}\binom{n}{2}$. This fact together with Theorem~\ref{thm:rs} and Proposition~\ref{prop:stats} yields Theorem~\ref{thm:main} in the case where $\lambda = \emptyset$. It also suggests that to find a~$C_3$ action on~$\mathcal{OT}(\lambda,k+2n)$ that exhibits homomesy with $\mathrm{wt}(\cdot)$ we could start by looking for a $C_3$ action on $\mathcal{M}_n$ that exhibits homomesy with~$\mathrm{align}(\cdot)$. Presumably it would be easy to find such an action if the statistics $\mathrm{cross}(\cdot)$, $\mathrm{nest}(\cdot)$, and~$\mathrm{align}(\cdot)$ were symmetrically distributed. However, this is not the case. That is, it is not true in general that \begin{align} \label{eqn:dist} \sum_{M \in \mathcal{M}_{n}} x_1^{\mathrm{cross}(M)}x_2^{\mathrm{nest}(M)}x_3^{\mathrm{align}(M)} = \sum_{M \in \mathcal{M}_{n}} x_{\omega(1)}^{\mathrm{cross}(M)}x_{\omega(2)}^{\mathrm{nest}(M)}x_{\omega(3)}^{\mathrm{align}(M)} \end{align} for all $\omega \in \mathfrak{S}_3$, the symmetric group on $3$ letters. Nevertheless, de M\'{e}dicis and Viennot~\cite{demedicis} define a certain involution, let us call it $\sigma\colon \mathcal{M}_n \to \mathcal{M}_n$, such that $\mathrm{cross}(M) = \mathrm{nest}(\sigma(M))$ and~$\mathrm{nest}(M) = \mathrm{cross}(\sigma(M))$ for all $M \in \mathcal{M}_n$. (See~\cite{kasraoui} for a description of this involution in English as well as a generalization to arbitrary set partitions.) As an aside, we remark that there is another natural involution $c\colon \mathcal{OT}(\emptyset,2n) \to \mathcal{OT}(\emptyset,2n)$ that can be transferred to perfect matchings via $RS$ given by $c(\lambda^{0},\ldots,\lambda^{2n}) := ((\lambda^{0})',(\lambda^{1})',\ldots,(\lambda^{2n})')$ where $\lambda'$ denotes the conjugate of $\lambda$. It is this conjugation symmetry that Chen~et.~al.~\cite{chen} exploit in studying maximal crossing and maximal nesting numbers in perfect matchings and set partitions. Note that $c$ is not the same as $\sigma$. One way to understand their relationship is by restricting to permutations. The set of $M \in \mathcal{M}_n$ with $D_M = 11\cdots 100\cdots 0$ is in bijection with $\mathfrak{S}_n$ by the map $M \mapsto \omega_M$ where $\omega_M(j) = i$ if $\{i,j+n\} \in M$. For all such $M$ we have $\omega_{c(M)} = \omega_{M}^{-1}$ while $\omega_{\sigma(M)} = \omega_{M}^{\mathrm{rev}}$. At least since the fundamental work of Simion and Schmidt~\cite{simion} it has been known that inversion and reversing are symmetries of the permutation pattern containment poset and from the work of Smith~\cite{smith} it follows that these involutions generate the group of all symmetries of this poset (which is isomorphic to the dihedral group of order eight). Researchers such as Bloom and Elizalde~\cite{bloom2} have considered pattern containment among perfect matchings. It would be interesting to describe all the symmetries of the perfect matching pattern containment poset, especially in relation to the maps $c$ and $\sigma$. At any rate, the involution $\sigma$ of de M\'{e}dicis and Viennot~\cite{demedicis} shows that~(\ref{eqn:dist}) holds for permutations~$\omega \in \mathfrak{S}_3$ with $\omega(3)=3$. It also suggests that $\mathrm{cross}(\cdot)$, $\mathrm{nest}(\cdot)$, and $\mathrm{align}(\cdot)$ may posses a $\mathfrak{S}_3$ symmetry in spite of not being symmetrically distributed because we could find some $\tau\colon \mathcal{M}_n \to \mathcal{M}_n$ of order $3$ such that $\mathrm{align}(\cdot)$ is homomesic with respect to~$\tau$. If we were to set~$G := \langle \sigma, \tau \rangle$ we would get that all three of the statistics $\mathrm{cross}(\cdot)$, $\mathrm{nest}(\cdot)$, and~$\mathrm{align}(\cdot)$ are homomesic with respect to the action of $G$. And if $(\sigma\tau)^2 = \mathrm{id}$ then~$G \simeq \mathfrak{S}_3$. To our knowledge, such a $\mathfrak{S}_3$ action would be the first instance of homomesy involving a non-cyclic group. Constructing such a~$\tau$ remains an open problem. But it is useful to know, as Theorem~\ref{thm:main} suggests, that~$\tau$ ought to make sense at the more general level of oscillating tableaux of arbitrary shape as well. \subsection*{Acknowledgements} This research was carried out at MIT as part of the RSI summer mathematics research program for high school students. The first author was the mentor of the second author. We thank Richard Stanley for some helpful questions and comments. We also thank Tanya Khovanova for proofreading and comments about the exposition. Finally, we thank the anonymous referee for a careful reading and many thoughtful comments. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % \bibliographystyle{plain} % \bibliography{myBibFile} % If you use BibTeX to create a bibliography % then copy and past the contents of your .bbl file into your .tex file \begin{thebibliography}{10} \bibitem{bloom2} Jonathan Bloom and Sergi Elizalde. \newblock Pattern avoidance in matchings and partitions. \newblock {\em Electron. J. Combin.}, 20(2):\#P5, 38, 2013. \bibitem{bloom} Jonathan Bloom, Oliver Pechenik, and Dan Saracino. \newblock A homomesy conjecture of {J}. {P}ropp and {T}. {R}oby. Preprint, 2013. \newblock \arxiv{1308.0546} \bibitem{chen} William Y.~C. Chen, Eva Y.~P. Deng, Rosena R.~X. Du, Richard~P. Stanley, and Catherine~H. Yan. \newblock Crossings and nestings of matchings and partitions. \newblock {\em Trans. Amer. Math. Soc.}, 359(4):1555--1575, 2007. \bibitem{demedicis} Anne de~M{\'e}dicis and Xavier~G. Viennot. \newblock Moments des {$q$}-polyn{\^ o}omes de {L}aguerre et la bijection de {F}oata-{Z}eilberger. \newblock {\em Adv. in Appl. Math.}, 15(3):262--304, 1994. \bibitem{einstein} David Einstein and James Propp. \newblock Piecewise-linear and birational toggling. \newblock {\em DMTCS Proc.}, 2014. \newblock FPSAC 2014, Chicago, Illinois. \bibitem{fomin} S.~V. Fomin. \newblock The generalized {R}obinson-{S}chensted-{K}nuth correspondence. \newblock {\em Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI)}, 155(Differentsialnaya Geometriya, Gruppy Li i Mekh. VIII):156--175, 195, 1986. \bibitem{kasraoui} Anisse Kasraoui and Jiang Zeng. \newblock Distribution of crossings, nestings and alignments of two edges in matchings and partitions. \newblock {\em Electron. J. Combin.}, 13:\#R33, 2006. \bibitem{propp} James Propp and Tom Roby. \newblock Homomesy in products of two chains. \newblock {\em DMTCS Proc.}, AS:975--986, 2013. \newblock FPSAC 2013, Paris, France. \bibitem{roby} Tom Roby. \newblock {\em Applications and extensions of {F}omin's generalization of the {R}obinson-{S}chensted correspondence to differential posets}. \newblock ProQuest LLC, Ann Arbor, MI, 1991. \newblock Thesis (Ph.D.)--Massachusetts Institute of Technology. \bibitem{sage-combinat} The {S}age-{C}ombinat community. \newblock {S}age-{C}ombinat: enhancing {S}age as a toolbox for computer exploration in algebraic combinatorics, 2008. \newblock {\tt http://combinat.sagemath.org}. \bibitem{simion} Rodica Simion and Frank~W. Schmidt. \newblock Restricted permutations. \newblock {\em European J. Combin.}, 6(4):383--406, 1985. \bibitem{smith} Rebecca Smith. \newblock Permutation reconstruction. \newblock {\em Electron. J. Combin.}, 13:\#N11, 2006. \bibitem{stanley1} Richard~P. Stanley. \newblock Differential posets. \newblock {\em J. Amer. Math. Soc.}, 1(4):919--961, 1988. \bibitem{stanley2} Richard~P. Stanley. \newblock {\em Enumerative combinatorics. {V}ol. 2}, volume~62 of {\em Cambridge Studies in Advanced Mathematics}. \newblock Cambridge University Press, Cambridge, 1999. \newblock With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. \bibitem{stanley3} Richard~P. Stanley. \newblock {\em Algebraic combinatorics}. \newblock Undergraduate Texts in Mathematics. Springer, New York, 2013. \newblock Walks, trees, tableaux, and more. \bibitem{sundaram} Sheila Sundaram. \newblock {\em On the combinatorics of representations of $Sp(2n,C)$}. \newblock ProQuest LLC, Ann Arbor, MI, 1986. \newblock Thesis (Ph.D.)--Massachusetts Institute of Technology. \end{thebibliography} \end{document}