\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\usepackage{subcaption}
\usepackage{ytableau}
\usepackage{tikz}
\usetikzlibrary{arrows,shapes,positioning,decorations.markings,decorations.pathreplacing}
\tikzset{->-/.style={decoration={
markings,
mark=at position .5 with {\arrow{>}}},postaction={decorate}}}
\usepackage{array}
\newcolumntype{C}[1]{>{\centering\let\newline\\\arraybackslash\hspace{0pt}}m{#1}}
\renewcommand{\arraystretch}{1}
\setlength{\tabcolsep}{3pt}
\newcolumntype{?}{!{\vrule width 3pt}}
\def\Z{\mathbb{Z}}
\def\N{\mathbb{N}}
\def\Q{\mathbb{Q}}
\def\C{\mathbb{C}}
\newcommand\floor[1]{\lfloor#1\rfloor}
\DeclareMathOperator{\svt}{\mathbb{S}}
\DeclareMathOperator{\jdq}{Jdq}
\DeclareMathOperator{\im}{Im}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf Jeu de Taquin of Set-Valued Young Tableaux
}
\vskip 1cm
\large
Paul Drube and Nichole Smith\\
Department of Mathematics and Statistics\\
Valparaiso University\\
Valparaiso, IN 46383\\
USA\\
\href{mailto:paul.drube@valpo.edu}{\tt paul.drube@valpo.edu} \\
\href{mailto:nichole.smith@valpo.edu}{\tt nichole.smith@valpo.edu}
\end{center}
\begin{abstract}
{\it Jeu de taquin\/} is a well-known operation on standard Young tableaux that may be used to define an equivalence relation on tableaux of any fixed rectangular shape. Via the well-studied bijection between two-row standard Young tableaux and non-crossing matchings, jeu de taquin is known to correspond to rotation of the associated matching by one strand. In this paper, we adapt jeu de taquin to standard set-valued Young tableaux --- a generalization of standard Young tableaux where cells contain unordered sets of integers. Our modified jeu de taquin operation is shown to correspond to to rotation of various classes of non-crossing matchings by one strand. In the case corresponding to $k$-equal non-crossing matchings, closed formulas are derived for the number of jeu de taquin equivalence classes of standard set-valued Young tableaux.
\end{abstract}
\section{Introduction: jeu de taquin of Young tableaux}
\label{sec: intro}
Let $\lambda = (\lambda_1,\ldots,\lambda_m)$ be a non-increasing integer partition of $n$. A Young diagram (Ferrers diagram) $Y$ of shape $\lambda$ is a left-aligned array of cells such that there are precisely $\lambda_i$ cells in the $i^{th}$ row of $Y$. An assignment of $[n] = \lbrace 1,\ldots,n \rbrace$ to the cells $Y$ produces what is known as a Young tableau of shape $\lambda$. A Young tableau $T$ is column-standard if entries increase from top to bottom down every column, and is row-standard if entries increase from left to right across each row. If a Young tableau is both column-standard and row-standard, it is referred to as a standard Young tableau. We establish $S(\lambda)$ as notation for the set of all standard Young tableaux of shape $\lambda$; for the $m$-row rectangular shape $\lambda = (n,\ldots,n)$ we use the condensed notation $S(n^m)$. Comprehensive introductions to Young tableaux have been given by Fulton \cite{Fulton} and Stanley \cite{Stanley2}
For any shape $\lambda$, one may define a bijection $p : S(\lambda) \rightarrow S(\lambda)$ that adapts Sch\"utzenberger's ``jeu de taquin'' promotion action on posets \cite{Schutzenberger}. For $T \in S(\lambda)$, where $\lambda \vdash n$, we construct $p(T)$ as follows:
\begin{enumerate}
\item Delete the entry of $T$ at position $(1,1)$ and renumber the remaining entries of $T$ by $x \mapsto x-1$, producing a skew standard Young tableaux to which Sch\"utzenberger's original operation applies.
\item Proceed through Sch\"utzenberger's algorithm by recursively identifying the smaller of the two entries directly to the right and directly below the single vacated cell, and then sliding that smaller entry into the vacated cell (producing another vacated cell elsewhere).
\item Repeat the process of Step \#2 until the single vacated cell is located in a lower-right corner. Then fill the vacated cell in the lower-right corner of the resulting tableau with $n$.
\end{enumerate}
See Figure \ref{fig: JDQ example} for an example of $p$. Note that $p$ has already been applied to various classes of tableaux by Shimozono \cite{Shimozono}, Stembridge \cite{Stembridge}, Rhoades \cite{Rhoades}, and Petersen, Pylyavskyy, and Rhoades \cite{PPR}. For a recent generalization of the promotion operation that is entirely distinct from the generalization of this paper, see the work of Pechenik on promotion in increasing tableaux \cite{Pechenik1,Pechenik2}.
\begin{figure}[ht!]
\centering
\scalebox{.87}{
\begin{ytableau}
1 & 3 & 4 \\
2 & 5 \\
6 & 7
\end{ytableau}
\hspace{.02in}
\raisebox{-16pt}{\scalebox{2.2}{$\Rightarrow$}}
\hspace{.02in}
\begin{ytableau}
\ & 2 & 3 \\
1 & 4 \\
5 & 6
\end{ytableau}
\hspace{.02in}
\raisebox{-16pt}{\scalebox{2.2}{$\Rightarrow$}}
\hspace{.02in}
\begin{ytableau}
1 & 2 & 3 \\
\ & 4 \\
5 & 6
\end{ytableau}
\hspace{.02in}
\raisebox{-16pt}{\scalebox{2.2}{$\Rightarrow$}}
\hspace{.02in}
\begin{ytableau}
1 & 2 & 3 \\
4 & \ \\
5 & 6
\end{ytableau}
\hspace{.02in}
\raisebox{-16pt}{\scalebox{2.2}{$\Rightarrow$}}
\hspace{.02in}
\begin{ytableau}
1 & 2 & 3 \\
4 & 6 \\
5 & \
\end{ytableau}
\hspace{.02in}
\raisebox{-16pt}{\scalebox{2.2}{$\Rightarrow$}}
\hspace{.02in}
\begin{ytableau}
1 & 2 & 3 \\
4 & 6 \\
5 & 7
\end{ytableau}}
\caption{The map $p: S(\lambda) \rightarrow S(\lambda)$ applied to $T \in S(\lambda)$ with $\lambda = (3,2,2)$.}
\label{fig: JDQ example}
\end{figure}
In a slight abuse of terminology, we refer to $p: S(\lambda) \rightarrow
S(\lambda)$ as {\it jeu de taquin}. Associated with this operation is an
equivalence relation $\sim_p$ whereby $T_1,T_2 \in S(\lambda)$ satisfy
$T_1 \sim_p T_2$ if and only if $p^k(T_1) = T_2$ for some $k \in \Z$.
In this situation we say that $T_1$ and $T_2$ are jeu de taquin
equivalent. We use $\widetilde{S}(\lambda)$ to denote the set of jeu
de taquin equivalence classes in $S(\lambda)$.
For $\lambda = n^2$ it is well-known that $| S(n^2) | = C_n$, where $C_n = \frac{1}{n+1} \binom{2n}{n}$ is the $n^{th}$ Catalan number. This places $S(n^2)$ in bijection with the hundreds of combinatorial interpretations of $C_n$ compiled by Stanley \cite{StanleyC}. Relevant to this discussion is the bijection $\phi$ between $S(n^2)$ and the set $\mathcal{M}_n$ of non-crossing matchings on $2n$ points, which associates first-row entries of $T \in S(n^2)$ with left endpoints of half-circles in $\phi(T) \in \mathcal{M}_n$ and second-row entries of $T$ with right endpoints of half-circles in $\phi(T)$.
Now consider a pair of tableaux $T,p(T) \in S(n^2)$ that are related by a single jeu de taquin. As noted by Petersen, Pylyavskyy, and Rhoades \cite{PPR}, the associated non-crossing matchings $\phi(T),\phi(p(T)) \in \mathcal{M}_n$ are related via ``rotation" by the leftmost strand in $\phi(T)$ over the top of the matching. It quickly follows that the jeu de taquin equivalence classes of $\widetilde{S}(n^2)$ are in bijection with the set $\widetilde{\mathcal{M}}_n$ of ``circular non-crossing matchings" on $2n$ points: noncrossing partitions of $[2n]$ into $n$ blocks of size $2$ ($2$-equal noncrossing partitions), modulo rotation by multiples of $\pi/n$ radians when its endpoints are evenly spaced about the unit circle. See Figure \ref{fig: jdq equals matching rotation} for an example of these phenomena.
\begin{figure}[ht!]
\begin{subfigure}[b]{0.27\textwidth}
\centering
\scalebox{.92}{
\begin{ytableau}
1 & 3 & 4 & 6 \\
2 & 5 & 7 & 8
\end{ytableau}}
\vspace{.15in}
\raisebox{5pt}{$\phi$} \scalebox{2.25}{$\downarrow$}
\vspace{.15in}
\begin{tikzpicture}
[scale=.51,auto=left,every node/.style={circle,fill=black,inner sep=1.3pt}]
\node[inner sep=0pt] (left) at (.5,0) {};
\node[inner sep=0pt] (right) at (8.5,0) {};
\draw[thick] (left) to (right);
\draw[thick,red] (2,0) arc (0:180:.5);
\draw[thick] (5,0) arc (0:180:.5);
\draw[thick] (7,0) arc (0:180:.5);
\draw[thick, bend right=75] (8,0) to (3,0);
\node (1) at (1,0) {};
\node (2) at (2,0) {};
\node (3) at (3,0) {};
\node (4) at (4,0) {};
\node (5) at (5,0) {};
\node (6) at (6,0) {};
\node (7) at (7,0) {};
\node (8) at (8,0) {};
\node[fill=none] (1l) at (1,-.5) {1};
\node[fill=none] (2l) at (2,-.5) {2};
\node[fill=none] (3l) at (3,-.5) {3};
\node[fill=none] (4l) at (4,-.5) {4};
\node[fill=none] (5l) at (5,-.5) {5};
\node[fill=none] (6l) at (6,-.5) {6};
\node[fill=none] (7l) at (7,-.5) {7};
\node[fill=none] (8l) at (8,-.5) {8};
\end{tikzpicture}
\end{subfigure}
\begin{subfigure}[b]{0.1\textwidth}
\centering
\scalebox{2.25}{$\longrightarrow$} \raisebox{12pt}{\kern-27pt$p$}
\hspace{.2in}
\vspace{.8in}
\raisebox{16pt}{\scalebox{2.25}{$\longrightarrow$} \raisebox{16pt}{\kern-43ptrotation}\hspace{.03in}}
\end{subfigure}
\begin{subfigure}[b]{0.27\textwidth}
\centering
\scalebox{.92}{
\begin{ytableau}
1 & 2 & 3 & 5 \\
4 & 6 & 7 & 8
\end{ytableau}}
\vspace{.15in}
\raisebox{5pt}{$\phi$} \scalebox{2.25}{$\downarrow$}
\vspace{.0in}
\begin{tikzpicture}
[scale=.51,auto=left,every node/.style={circle,fill=black,inner sep=1.3pt}]
\node[inner sep=0pt] (left) at (.5,0) {};
\node[inner sep=0pt] (right) at (8.5,0) {};
\draw[thick] (left) to (right);
\draw[thick,red, bend right=75] (8,0) to (1,0);
\draw[thick] (4,0) arc (0:180:.5);
\draw[thick] (6,0) arc (0:180:.5);
\draw[thick, bend right=75] (7,0) to (2,0);
\node (1) at (1,0) {};
\node (2) at (2,0) {};
\node (3) at (3,0) {};
\node (4) at (4,0) {};
\node (5) at (5,0) {};
\node (6) at (6,0) {};
\node (7) at (7,0) {};
\node (8) at (8,0) {};
\node[fill=none] (1l) at (1,-.5) {1};
\node[fill=none] (2l) at (2,-.5) {2};
\node[fill=none] (3l) at (3,-.5) {3};
\node[fill=none] (4l) at (4,-.5) {4};
\node[fill=none] (5l) at (5,-.5) {5};
\node[fill=none] (6l) at (6,-.5) {6};
\node[fill=none] (7l) at (7,-.5) {7};
\node[fill=none] (8l) at (8,-.5) {8};
\end{tikzpicture}
\end{subfigure}
\begin{subfigure}[b]{0.34\textwidth}
\centering
\hspace{.45in}
\raisebox{34pt}{
\begin{tikzpicture}
[scale=1.2,auto=left,every node/.style={circle,inner sep=0pt}]
\draw (0,0) circle (1cm);
\draw[thick, bend right=40] (140:1) to (40:1);
\draw[thick, bend right=40] (165:1) to (15:1);
\draw[thick, bend right=60] (340:1) to (280:1);
\draw[thick, bend right=60] (260:1) to (200:1);
\end{tikzpicture}}
\end{subfigure}
\caption{A pair of tableaux $T,p(T) \in S(n^2)$ and their associated non-crossing matchings. On the right is the circular non-crossing matching in $\widetilde{\mathcal{M}}_4$ to which both tableaux correspond.}
\label{fig: jdq equals matching rotation}
\end{figure}
The jeu de taquin equivalence classes of $\widetilde{S}(n^2)$ may be enumerated via several techniques that already appear in the literature. The earliest such enumeration was given by Goldbach and Tijdeman \cite{GT}, who directly counted the number of circular non-crossing matchings fixed by an arbitrary rotation and applied Burnside's lemma to give
\begin{equation}
\label{eq: Goldbach and Tijdeman k=2}
| \widetilde{\mathcal{M}}_n | = \frac{1}{2n} \left( \sum_{d|n} \varphi(n/d) \binom{2d}{d} \right) - \frac{1}{2}C_n + \frac{1}{2} C_{(n-1)/2} .
\end{equation}
In Eq.\ \eqref{eq: Goldbach and Tijdeman k=2}, $\varphi$ represents Euler's totient function and the final term on the right is taken to be zero if the subscript is not an integer.
Working within the more general setting of rational Catalan combinatorics, Bodnar and Rhoades \cite{BR} showed that the aforementioned rotational action on non-crossing matchings provides an example of the cyclic sieving phenomenon. This allows for a much easier enumeration of circular non-crossing matchings fixed by an arbitrary rotation, via the evaluation of $q$-Catalan numbers at an appropriate root of unity.
The goal of this paper is to explore a generalization of the jeu de taquin promotion operator to standard set-valued Young tableaux. In Section \ref{sec: set-valued tableaux}, we define set-valued jeu de taquin and look to generalize the phenomenon of Figure \ref{fig: jdq equals matching rotation} to the most general setting in which there exists a straightforward bijection between noncrossing partitions and standard set-valued Young tableaux. That phenomenon admits a direct analogue in the case of set-valued tableaux with shape $\lambda=n^2$ and row-constant density (Theorem \ref{thm: jdq equals rotation, k-Catalan}). Generalizing the phenomenon of Figure \ref{fig: jdq equals matching rotation} to arbitrary tableaux of shape $\lambda=n^2$ is only possible after we define a slight modification of our jeu de taquin operator that we refer to as ``rotational jeu de taquin" (Theorem \ref{thm: rotational jdq equals rotation}). Section \ref{sec: enumeration} is dedicated to the enumeration of jeu de taquin equivalence classes of set-valued tableaux in the case of row-constant density. This results in a one-parameter generalization of Eq.\ \eqref{eq: Goldbach and Tijdeman k=2} that counts circular $k$-equal noncrossing partitions for any $k \geq 2$ (Theorem \ref{thm: circular k-point matching enumeration}) as well as an equivalent formula obtained via cyclic sieving (Theorem \ref{thm: enumeration, cyclic sieving}). It should be noted that, in the case of rational noncrossing partitions, our constructions are outwardly similar to yet subtly different from the approach of Armstrong, Rhoades, and Williams \cite{ARW}, which does not involve the associated tableaux.
\section{Jeu de taquin of standard set-valued Young tableaux}
\label{sec: set-valued tableaux}
Let $Y$ be a Young diagram of shape $\lambda$. For any collection of positive integers $\rho =\lbrace \rho_{i,j} \rbrace$ such that $\sum_{i,j} \rho_{i,j} = m$, a set-valued Young tableau of shape $\lambda$ and density $\rho$ is a map from $[m]$ to the cells of $Y$ such that the cell at position $(i,j)$ receives precisely $\rho_{i,j}$ integers. A standard set-valued Young tableau is a set-valued Young tableau with the added conditions that every integer at position $(i,j)$ is smaller than every integer at positions $(i+1,j)$ and $(i,j+1)$. We use $\svt(\lambda,\rho)$ to denote the set of all standard set-valued Young tableaux of shape $\lambda$ and density $\rho$. If $\sum_{i,j} \rho_{i,j} = m$, we adopt the notation $| \rho | = m$. See Figure \ref{fig: basic set-valued tableaux example} for an illustration of $\svt(\lambda,\rho)$ when $\lambda = (2,2)$.
\begin{figure}[ht!]
\centering
\scalebox{.92}{
\setlength{\tabcolsep}{2.5pt}
\begin{tabular}{|>{$}c<{$}|>{$}c<{$}|>{$}c<{$}|}
\hline
1 \kern+3pt 2 \kern+3pt 3 & 4 \kern+3pt 5 \kern+3pt 6 \\ \hline
7 \kern+3pt 8 & 9 \kern+3pt 10 \\ \hline
\end{tabular}
\hspace{.3in}
\begin{tabular}{|>{$}c<{$}|>{$}c<{$}|>{$}c<{$}|}
\hline
1 \kern+3pt 2 \kern+3pt 3 & 4 \kern+3pt 5 \kern+3pt 7 \\ \hline
6 \kern+3pt 8 & 9 \kern+3pt 10 \\ \hline
\end{tabular}
\hspace{.3in}
\begin{tabular}{|>{$}c<{$}|>{$}c<{$}|>{$}c<{$}|}
\hline
1 \kern+3pt 2 \kern+3pt 3 & 4 \kern+3pt 5 \kern+3pt 8 \\ \hline
6 \kern+3pt 7 & 9 \kern+3pt 10 \\ \hline
\end{tabular}
\hspace{.3in}
\begin{tabular}{|>{$}c<{$}|>{$}c<{$}|>{$}c<{$}|}
\hline
1 \kern+3pt 2 \kern+3pt 3 & 4 \kern+3pt 6 \kern+3pt 7 \\ \hline
5 \kern+3pt 8 & 9 \kern+3pt 10 \\ \hline
\end{tabular}
\hspace{.3in}
\begin{tabular}{|>{$}c<{$}|>{$}c<{$}|>{$}c<{$}|}
\hline
1 \kern+3pt 2 \kern+3pt 3 & 4 \kern+3pt 6 \kern+3pt 8 \\ \hline
5 \kern+3pt 7 & 9 \kern+3pt 10 \\ \hline
\end{tabular}
}
\vspace{.2in}
\scalebox{.92}{
\setlength{\tabcolsep}{2.5pt}
\begin{tabular}{|>{$}c<{$}|>{$}c<{$}|>{$}c<{$}|}
\hline
1 \kern+3pt 2 \kern+3pt 3 & 4 \kern+3pt 7 \kern+3pt 8 \\ \hline
5 \kern+3pt 6 & 9 \kern+3pt 10 \\ \hline
\end{tabular}
\hspace{.3in}
\begin{tabular}{|>{$}c<{$}|>{$}c<{$}|>{$}c<{$}|}
\hline
1 \kern+3pt 2 \kern+3pt 3 & 5 \kern+3pt 6 \kern+3pt 7 \\ \hline
4 \kern+3pt 8 & 9 \kern+3pt 10 \\ \hline
\end{tabular}
\hspace{.3in}
\begin{tabular}{|>{$}c<{$}|>{$}c<{$}|>{$}c<{$}|}
\hline
1 \kern+3pt 2 \kern+3pt 3 & 5 \kern+3pt 6 \kern+3pt 8 \\ \hline
4 \kern+3pt 7 & 9 \kern+3pt 10 \\ \hline
\end{tabular}
\hspace{.3in}
\begin{tabular}{|>{$}c<{$}|>{$}c<{$}|>{$}c<{$}|}
\hline
1 \kern+3pt 2 \kern+3pt 3 & 5 \kern+3pt 7 \kern+3pt 8 \\ \hline
4 \kern+3pt 6 & 9 \kern+3pt 10 \\ \hline
\end{tabular}
\hspace{.3in}
\begin{tabular}{|>{$}c<{$}|>{$}c<{$}|>{$}c<{$}|}
\hline
1 \kern+3pt 2 \kern+3pt 3 & 6 \kern+3pt 7 \kern+3pt 8 \\ \hline
4 \kern+3pt 5 & 9 \kern+3pt 10 \\ \hline
\end{tabular}
}
\caption{The set $\svt(\lambda,\rho)$ of standard set-valued Young tableaux with $\lambda = (2,2)$ and row-constant density $\rho$ with $\rho_{1,j} = 3$, $\rho_{2,j} = 2$.}
\label{fig: basic set-valued tableaux example}
\end{figure}
Standard set-valued Young tableaux were originally defined by Buch \cite{Buch} in his work on the K-theory of Grassmanians, and were later used by Heubach, Li, and Mansour \cite{HLM} to provide a new combinatorial interpretation of the $k$-Catalan numbers. Those results were extended by the first author \cite{Drube}, who used set-valued tableaux with $\lambda = n^2$ to give new combinatorial interpretations of the Raney numbers, the rational Catalan numbers, and the solution to the $(s,t)$-tennis ball problem.
The jeu de taquin operation admits a straightforward generalization $p: \svt(\lambda,\rho) \rightarrow \svt(\lambda,\rho)$ to set-valued tableaux of any shape and density. Given $T \in \svt(\lambda,\rho)$, where $| \rho | = m$, obtain $p(T)$ as follows:
\begin{enumerate}
\item Delete the smallest integer at position $(1,1)$, and renumber remaining entries by $x \mapsto x-1$.
\item Recursively identify the sole cell $(i,j)$ in the resulting tableau $T'\in \svt(\lambda,\rho')$ whose density $\rho'_{i,j}$ satisfies $\rho'_{i,j} = \rho_{i,j} - 1$. Then identify the smallest integer between the cells at $(i,j+1)$ and $(i+1,j)$, and slide that entry to $(i,j)$. This yields an ``under-weighted" cell at either $(i+1,j)$ or $(i,j+1)$.
\item Repeat Step \#2 until obtaining a set-valued tableau whose sole cell satisfying $\rho'_{i,j} = \rho_{i,j} - 1$ lies in a lower-right corner. Then add $m$ to the set of integers at this lower-right cell.
\end{enumerate}
In analogy with Section \ref{sec: intro}, we refer to the map $p : \svt(\lambda,w) \rightarrow \svt(\lambda,w)$ as \textit{set-valued jeu de taquin}. We once again define an equivalence relation $\sim_p$ on $\svt(\lambda,w)$ whereby $T_1 \sim_p T_2$ if and only if $p^k(T_1) = T_2$ for some $k \in \Z$. We say that $T_1$ and $T_2$ are jeu de taquin equivalent if $T_1 \sim_p T_2$, and let $\widetilde{\svt}(\lambda,w)$ denote the set of jeu de taquin equivalence classes on $\svt(\lambda,w)$.
\subsection{Set-valued tableaux and generalized non-crossing matchings}
\label{subsec: tableaux vs matchings}
We begin by establishing our general bijection between standard set-valued Young tableaux of shape $\lambda = n^2$ and noncrossing partitions. This is possible for all set-valued tableaux whose densities carry a constant value of $\rho_{2,j} = 1$ across their second-row, with specific sets $\svt(\lambda,\rho)$ of this type corresponding to noncrossing partitions with different block structures. The authors realize that much of the formalism below is a recasting of existing terminology in more convenient/concise language.
So consider a tuple of positive integers $\vec{b} = ( b_1, \ldots, b_n )$, where $b_i \geq 2$ for all $1 \leq i \leq n$ and $b_1 + \cdots + b_n = N$. A
\textit{non-crossing matching of type $\vec{b}$} is a noncrossing partition of $[N]$ into $n$ blocks whose respective sizes, when ordered via their largest elements, are $b_1, \ldots, b_n$. As in Section \ref{sec: intro}, we represent our matchings as a collection of $b_i$-stars with endpoints along the $x$-axis.
Denote the set of all non-crossing matchings of type $\vec{b}$ by $\mathcal{M}_{\vec{b}}$. When it is notationally convenient, we will reference a particular matching $M \in \mathcal{M}_{\vec{b}}$ via the blocks of its corresponding noncrossing partition, listing the elements of each block in increasing order. For example, the matching in Figure \ref{fig: matching vs. set-valued tableaux example} will be denoted $M = \lbrace (1,7,8,9), (2,5,6), (3,4), (10,11) \rbrace$.
\begin{proposition}
\label{thm: non-crossing matchings vs. set-valued tableaux}
Take any tuple of positive integers $\vec{b} = ( b_1,\ldots,b_n )$. The set $\mathcal{M}_{\vec{b}}$ of non-crossing matchings of type $\vec{b}$ is in bijection with $\svt(n^2,\rho)$ for density $\rho$ with $\rho_{1,j} = b_j - 1$ and $\rho_{2,j} =1$ for all $j$.
\end{proposition}
\begin{proof}
For any $T \in \svt(\lambda,w)$, we define an injective map $\phi: \svt(\lambda,w) \rightarrow \mathcal{M}_{\vec{b}}$ by working from left to right through the second row of $T$. For each entry $a_j$ in the second row of $T$, identify the $b_j-1$ largest integers $x_{j,1},\ldots,x_{1,b_j-1}$ in the first row of $T$ that have not already been associated to a star and which satisfy $x_{j,1} < \cdots < x_{j,b_j-1} < a_j$. Then add a $b_j$-star to $\phi(T)$ whose endpoints lie at $x_{j,1},\ldots,x_{j,b_j-1},a_j$. The fact that $T$ is standard ensures that at least $b_j-1$ such integers exist. Our method of selecting the $x_{j,i}$ ensures that stars are added ``from the inside out" and hence cannot intersect.
To construct an injective inverse $\phi^{-1}: \mathcal{M}_{\vec{b}} \rightarrow \svt(\lambda,w)$, take any $M \in \mathcal{M}_{\vec{b}}$ and identify the rightmost endpoint of each $b_i$-star. Place those integers in the second row of $\phi^{-1}(M)$, in increasing order from left to right. Then place all remaining elements of $[N]$ in increasing order across the first row of $\phi^{-1}(M)$, making sure that the cell at position $(1,j)$ contains $b_j - 1$ integers. As the integer corresponding to the rightmost endpoint of each $b_j$-star is larger than the integers corresponding to its remaining endpoints, the tableau $\phi^{-1}(M)$ is column-standard.
\end{proof}
\begin{figure}[ht!]
\centering
\raisebox{28pt}{\begin{tabular}{|c|c|c|c|}
\hline
1 & 2 \kern+1pt 3 & 5 \kern+1pt 7 \kern+1pt 8 & 10 \\ \hline
4 & 6 & 9 & 11 \\ \hline
\end{tabular}}
\hspace{.2in}
\raisebox{22pt}{\scalebox{3}{$\Leftrightarrow$}}
\hspace{.1in}
\scalebox{.9}{
\begin{tikzpicture}
[scale=.55,auto=left,every node/.style={circle,fill=black,inner sep=1.3pt,outer sep=0pt}]
\node[inner sep=0pt] (left) at (.5,0) {};
\node (1) at (1,0) {};
\node (2) at (2,0) {};
\node (3) at (3,0) {};
\node (4) at (4,0) {};
\node (5) at (5,0) {};
\node (6) at (6,0) {};
\node (7) at (7,0) {};
\node (8) at (8,0) {};
\node (9) at (9,0) {};
\node (10) at (10,0) {};
\node (11) at (11,0) {};
\node[inner sep=0pt] (right) at (11.5,0) {};
\draw (left) to (right);
\node[inner sep=0pt] (a) at (5,1.35) {};
\node[inner sep=0pt] (b) at (7.5,2) {};
\draw[thick] (4,0) arc (0:180:.5);
\draw[thick] (11,0) arc (0:180:.5);
\draw[thick, bend left=25] (2) to (a);
\draw[thick] (5) to (a);
\draw[thick, bend right=20] (6) to (a);
\draw[thick, bend left=30] (1) to (b);
\draw[thick, bend left=5] (7) to (b);
\draw[thick, bend right=5] (8) to (b);
\draw[thick, bend right=20] (9) to (b);
\node[fill=none] (1l) at (1,-.5) {1};
\node[fill=none] (2l) at (2,-.5) {2};
\node[fill=none] (3l) at (3,-.5) {3};
\node[fill=none] (4l) at (4,-.5) {4};
\node[fill=none] (5l) at (5,-.5) {5};
\node[fill=none] (6l) at (6,-.5) {6};
\node[fill=none] (7l) at (7,-.5) {7};
\node[fill=none] (8l) at (8,-.5) {8};
\node[fill=none] (9l) at (9,-.5) {9};
\node[fill=none] (10l) at (10,-.5) {10};
\node[fill=none] (11l) at (11,-.5) {11};
\end{tikzpicture}}
\caption{A non-crossing matching of weight $\vec{b} = ( 2,3,4,2 )$ and its corresponding standard set-valued Young tableau.}
\label{fig: matching vs. set-valued tableaux example}
\end{figure}
See Figure \ref{fig: matching vs. set-valued tableaux example} for an example of the bijection from Proposition \ref{thm: non-crossing matchings vs. set-valued tableaux}. For constant type $\vec{b} = (k,\ldots,k)$, Proposition \ref{thm: non-crossing matchings vs. set-valued tableaux} reduces to the bijection involving $k$-equal matchings that we will examine in Subsection \ref{subsec: jdq=rotation k-Catalan}. For coprime positive integers $a,b$ and using the result of Drube \cite{Drube}, Proposition \ref{thm: non-crossing matchings vs. set-valued tableaux} also places matchings of type $\vec{b}_{(a,b)} = (\lceil \frac{b}{a} \rceil - \lceil 0 \rceil + 1, \ldots, \lceil \frac{ab}{a} \rceil - \lceil \frac{(a-1)b}{a} \rceil + 1)$ in bijection with a collection of set-valued tableaux that are enumerated by the rational Catalan number $C(a,b) = \frac{1}{a+b} \binom{a+b}{a}$. See Appendix \ref{app: comparison to rational non-crossing matchings} for a thorough discussion of how these ``rational non-crossing matchings" differ from the homogeneous $(a,b)$-noncrossing partitions of Armstrong, Rhoades, and Williams \cite{ARW}, which are also enumerated by $C(a,b)$.
Before proceeding, note that the bijection of Proposition \ref{thm: non-crossing matchings vs. set-valued tableaux} may be used to easily identify where the tableau $T$ splits. A standard set-valued Young tableau $T$ is said to split after its $m^{th}$ column if the set of integers filling its first $m$ columns equals $[M]$ for some $M \in \N$. It is easy to see that $T \in \svt(n^2,\rho_{\vec{b}})$ splits after its $m^{th}$ column if and only if the $m$ leftmost stars of $\phi(T) \in \mathcal{M}_n^k$ constitute a non-crossing matching of type $\vec{b}' = ( b_1,\ldots, b_m )$. Even more specifically:
\begin{proposition}
\label{thm: tableaux splits via non-crossing matchings}
Let $\phi: \svt(n^2,w) \rightarrow \mathcal{M}_{\vec{b}}$ be the bijection of Proposition \ref{thm: non-crossing matchings vs. set-valued tableaux}, and take $\phi(T) \in \mathcal{M}_{\vec{b}}$. If $x$ is the rightmost endpoint of the star whose leftmost endpoint is $1$, then $x = b_1 + \cdots + b_m$ for some $m \geq 1$ and $m$ is the smallest positive integer such that $T$ splits after its $m^{th}$ column.
\end{proposition}
\subsection{Jeu de taquin and rotation of equal non-crossing matchings}
\label{subsec: jdq=rotation k-Catalan}
In this subsection we restrict our attention to non-crossing matchings of constant type $\vec{b} = ( k,\ldots,k )$, corresponding to tableaux $\svt(n^2,\rho)$ with row-constant density $\rho$ satisfying $\rho_{1,j} = k-1$, $\rho_{2,j} = 1$. These are precisely the sets $\svt(n^2,\rho)$ and $\mathcal{M}_{\vec{b}}$ that Heubach, Li, and Mansour present as two of their many combinatorial interpretations of the $k$-Catalan numbers \cite{HLM}. In particular, those authors show that $| \svt(\lambda,\rho) | = | \mathcal{M}_{\vec{b}} | = C_n^k = \frac{1}{n(k-1)+1} \binom{kn}{n}$. We henceforth refer to non-crossing matchings of constant type $\vec{b} = ( k,\ldots,k )$ as $k$-equal non-crossing matchings, and denote the set of all $k$-equal non-crossing matchings on $kn$ points by $\mathcal{M}_n^k$.
For any (not necessarily constant) type $\vec{b} = ( b_1,\ldots,b_m )$, where $b_1 + \cdots + b_m = N$, there exists a rotation operator $r: \mathcal{M}_{\vec{b}} \rightarrow \mathcal{M}_{\vec{b}}$ in which $r(M)$ is obtained by replacing the leftmost $b_1$-star $(1,c_2,\ldots,c_{b_1})$ of $M$ with the $b_1$-star $(c_2-1,\ldots,c_k-1,N)$, and then re-indexing the endpoints of all remaining stars by $x \mapsto x-1$. Graphically, the matchings $M$ and $r(M)$ are related by ``swinging" the leftmost strand of the leftmost $b_1$-star in $M$ over the top of the rest of the matching. In the case of constant type $\vec{b} = ( k,\ldots,k )$, rotation of $M \in \mathcal{M}_n^k$ directly corresponds to jeu de taquin on the associated tableau $\phi^{-1}(M) \in \svt(n^2,\rho)$ from the bijection of Proposition \ref{thm: non-crossing matchings vs. set-valued tableaux}:
\begin{theorem}
\label{thm: jdq equals rotation, k-Catalan}
Fix $n \geq 1$, $k \geq 2$, and take any row-constant density $\rho$ with $\rho_{1,j} = k-1$ and $\rho_{2,j}=1$. If $\phi: \svt(n^2,\rho) \rightarrow \mathcal{M}_n^k$ is the bijection from Proposition \ref{thm: non-crossing matchings vs. set-valued tableaux}, then $\phi(p(T)) = r(\phi(T))$ for any $T \in \svt(n^2,\rho)$.
\end{theorem}
\begin{proof}
Take $T \in \svt(n^2,\rho)$, and assume $\phi(T) = \lbrace (1,a_1^2,\ldots,a_1^k), (a_2^1,\ldots,a_2^k), \ldots ,(a_n^1,\ldots,a_n^k) \rbrace$. We have $r(\phi(T)) = \lbrace (a_1^2 - 1, \ldots, a_1^k - 1, nk), (a_2^1 - 1, \ldots, a_2^k - 1), \ldots ,(a_n^1 - 1, \ldots, a_n^k -1) \rbrace$.
To characterize $\phi(p(T))$, let $b_1 < \cdots < b_n$ denote the second row entries of $T$. We have $\lbrace a_1^k,a_2^k,\ldots,a_n^k \rbrace = \lbrace b_1,\ldots,b_n \rbrace$ as sets, yet needn't have $a_i^k = b_i$ for fixed $i$. Assume $a_1^k = b_\alpha$.
Then consider the application of our set-valued jeu de taquin operation to $T$. If $b_i < b_\alpha$, the definition of $\phi$ ensures that there exist at least $i(k-1)+1$ entries $x$ in the first row of $T$ such that $x < b_i$. This means that the re-indexed second row entry $b_i - 1$ must be larger than at least one first row entry from a more rightward column of $T$, and hence that $b_i - 1$ cannot be slid upward at the point in Step \#2 of the set-valued jeu de taquin procedure when it lies directly below the under-weighted cell. Thus $b_i-1$ lies at position $(2,i)$ of $p(T)$.
For $b_\alpha$ itself, Proposition \ref{thm: tableaux splits via non-crossing matchings} guarantees that $b_\alpha = k \alpha$ and hence that $b_\alpha$ is smaller than every integer at position $(1,\alpha+1)$ of $T$. This ensures that the re-indexed second row entry $b_\alpha - 1$ must be slid upward at the point in Step \#2 when it lies directly below the under-weighted cell. After sliding $b_\alpha$ into the first column, the rest of Step \#2 involves sliding each remaining second-row entry by one cell. All of this implies that the second row of $p(T)$ is $b_1-1 < \cdots < b_{\alpha-1}-1 < b_{\alpha+1}-1 < \cdots < b_n - 1 < kn$.
It is only left to determine how the first-row entries of $p(T)$ are partitioned among the $k$-stars of $\phi(p(T))$. We work left-to-right through the second row entries of $p(T)$. For every $i < \alpha$, all first row entries of the $k$-star $(c_1,\ldots,c_{k-1},b_i)$ of $\phi(T)$ are slid precisely one entry leftward as we pass from $T$ to $p(T)$, allowing us to assert that $\phi(p(T))$ contains the $k$-star $(c_1-1,\ldots,c_{k-1} - 1,b_i - 1)$. For every $i > \alpha$, observe that the $k$-star $(c_1,\ldots,c_{k-1},b_i)$ of $\phi(T)$ satisfies $c_j > k\alpha$ for all $j$ and hence that the corresponding $k$-star $(c'_1,\ldots, c'_{k-1},b_i-1)$ of $\phi(p(T))$ must satisfy $c'_j > k\alpha-1$ for all $j$. The definition of $\phi$ then implies that $\phi(p(T))$ must contain the $k$-star $(c_1-1,\ldots,c_{k-1} - 1,b_i - 1)$. This leaves $k$ unassigned endpoints $(\gamma_1,\ldots,\gamma_{k-1},nk)$ for the final $k$-star of $\phi(p(T))$, where we must have $\gamma_j \leq k\alpha - 1$ for all $j$ and thus are forced to conclude that $\gamma_j = a_1^{j-1}-1$, yielding the final $k$-star $(a_1^2 - 1, \ldots, a_1^k - 1, nk)$. It follows that $\phi(p(T)) = \lbrace (a_1^2 - 1, \ldots, a_1^k - 1, nk), (a_2^1 - 1, \ldots, a_2^k - 1), \ldots ,(a_n^1 - 1, \ldots, a_n^k -1) \rbrace$.
\end{proof}
See Figure \ref{fig: set-valued jdq equals k-matching rotation} for an illustration of Theorem \ref{thm: jdq equals rotation, k-Catalan}. One immediate corollary of Theorem \ref{thm: jdq equals rotation, k-Catalan} is that the jeu de taquin equivalence classes of $\widetilde{\svt}(n^2,\rho)$ with $\rho_{1,j} = k-1$, $\rho_{2,j}=1$ are in bijection with ``circular $k$-equal non-crossing matchings" on $kn$ points. In analogy with Section \ref{sec: intro}, by circular $k$-equal non-crossing matchings we mean $\mathcal{M}_n^k$, modulo rotation by multiples of $2\pi/kn$ radians when the endpoints of matchings are evenly spaced about the unit circle. We denote the set of circular $k$-equal non-crossing matchings on $kn$ points by $\widetilde{\mathcal{M}}_n^k$.
\begin{corollary}
\label{thm: jdq equals rotation corollary, k-Catalan}
Take any $n \geq 1$, $k \geq 2$. Given the row-constant density $\rho$ with $\rho_{1,j}=k-1$ and $\rho_{2,j}=1$, jeu de taquin equivalence classes of $\widetilde{\svt}(n^2,\rho)$ are in bijection with the set $\widetilde{\mathcal{M}}_n^k$ of circular non-crossing k-point matchings on $kn$ points.
\end{corollary}
\begin{figure}[ht!]
\begin{subfigure}[b]{0.30\textwidth}
\centering
\scalebox{.92}{
\begin{ytableau}
1 \kern+2pt 2 & 3 \kern+2pt 5 & 6 \kern+2pt 7 \\
4 & 8 & 9
\end{ytableau}}
\vspace{.15in}
\raisebox{5pt}{$\phi$} \scalebox{2.25}{$\downarrow$} \hspace{.02in}
\vspace{.15in}
\scalebox{.92}{
\begin{tikzpicture}
[scale=.55,auto=left,every node/.style={circle,fill=black,inner sep=1.3pt,outer sep=0pt}]
\node[inner sep=0pt] (left) at (.5,0) {};
\node (1) at (1,0) {};
\node (2) at (2,0) {};
\node (3) at (3,0) {};
\node (4) at (4,0) {};
\node (5) at (5,0) {};
\node (6) at (6,0) {};
\node (7) at (7,0) {};
\node (8) at (8,0) {};
\node (9) at (9,0) {};
\node[inner sep=0pt] (right) at (9.5,0) {};
\node[inner sep=0pt] (a) at (3,1) {};
\node[inner sep=0pt] (b) at (5,2) {};
\node[inner sep=0pt] (c) at (7,1) {};
\draw[thick] (left) to (right);
\draw[thick, bend left=20] (2) to (a);
\draw[thick] (3) to (a);
\draw[thick, bend right=20] (4) to (a);
\draw[red, thick, bend left=20] (1) to (b);
\draw[red, thick] (5) to (b);
\draw[red, thick, bend right=20] (9) to (b);
\draw[thick, bend left=20] (6) to (c);
\draw[thick] (7) to (c);
\draw[thick, bend right=20] (8) to (c);
\node[fill=none] (1l) at (1,-.5) {1};
\node[fill=none] (2l) at (2,-.5) {2};
\node[fill=none] (3l) at (3,-.5) {3};
\node[fill=none] (4l) at (4,-.5) {4};
\node[fill=none] (5l) at (5,-.5) {5};
\node[fill=none] (6l) at (6,-.5) {6};
\node[fill=none] (7l) at (7,-.5) {7};
\node[fill=none] (8l) at (8,-.5) {8};
\node[fill=none] (9l) at (9,-.5) {9};
\end{tikzpicture}}
\end{subfigure}
\begin{subfigure}[b]{0.1\textwidth}
\centering
\scalebox{2.25}{$\longrightarrow$} \raisebox{12pt}{\kern-27pt$p$}
\hspace{.2in}
\vspace{.8in}
\raisebox{22pt}{\scalebox{2.25}{$\longrightarrow$} \raisebox{16pt}{\kern-27pt$r$}\hspace{.2in}}
\end{subfigure}
\begin{subfigure}[b]{0.30\textwidth}
\centering
\scalebox{.92}{
\begin{ytableau}
1 \kern+2pt 2 & 4 \kern+2pt 5 & 6 \kern+2pt 8 \\
3 & 7 & 9
\end{ytableau}}
\vspace{.16in}
\raisebox{5pt}{$\phi$} \scalebox{2.25}{$\downarrow$} \hspace{0.02in}
\vspace{.09in}
\scalebox{.92}{
\begin{tikzpicture}
[scale=.55,auto=left,every node/.style={circle,fill=black,inner sep=1.3pt,outer sep=0pt}]
\node[inner sep=0pt] (left) at (.5,0) {};
\node (1) at (1,0) {};
\node (2) at (2,0) {};
\node (3) at (3,0) {};
\node (4) at (4,0) {};
\node (5) at (5,0) {};
\node (6) at (6,0) {};
\node (7) at (7,0) {};
\node (8) at (8,0) {};
\node (9) at (9,0) {};
\node[inner sep=0pt] (right) at (9.5,0) {};
\node[inner sep=0pt] (a) at (2,1) {};
\node[inner sep=0pt] (b) at (8,2) {};
\node[inner sep=0pt] (c) at (6,1) {};
\draw[thick] (left) to (right);
\draw[thick, bend left=20] (1) to (a);
\draw[thick] (2) to (a);
\draw[thick, bend right=20] (3) to (a);
\draw[red, thick, bend left=35] (4) to (b);
\draw[red, thick] (8) to (b);
\draw[red, thick, bend right=20] (9) to (b);
\draw[thick, bend left=20] (5) to (c);
\draw[thick] (6) to (c);
\draw[thick, bend right=20] (7) to (c);
\node[fill=none] (1l) at (1,-.5) {1};
\node[fill=none] (2l) at (2,-.5) {2};
\node[fill=none] (3l) at (3,-.5) {3};
\node[fill=none] (4l) at (4,-.5) {4};
\node[fill=none] (5l) at (5,-.5) {5};
\node[fill=none] (6l) at (6,-.5) {6};
\node[fill=none] (7l) at (7,-.5) {7};
\node[fill=none] (8l) at (8,-.5) {8};
\node[fill=none] (9l) at (9,-.5) {9};
\end{tikzpicture}}
\end{subfigure}
\begin{subfigure}[b]{0.28\textwidth}
\centering
\hspace{.45in}
\raisebox{34pt}{
\begin{tikzpicture}
[scale=1.2,auto=left,every node/.style={circle,inner sep=0pt}]
\draw (0,0) circle (1cm);
\draw[thick] (0:0) to (60:1);
\draw[thick] (0:0) to (120:1);
\draw[thick] (0:0) to (270:1);
\draw[thick, bend left=30] (345:0.4) to (15:1);
\draw[thick] (345:0.4) to (345:1);
\draw[thick, bend right=30] (345:0.4) to (315:1);
\draw[thick, bend right=30] (195:0.4) to (165:1);
\draw[thick] (195:0.4) to (195:1);
\draw[thick, bend left=30] (195:0.4) to (225:1);
\end{tikzpicture}}
\end{subfigure}
\caption{A pair of set-valued tableaux related via a single jeu de taquin and the associated $3$-equal non-crossing matchings. On the right is the element of $\widetilde{\mathcal{M}}_n^k$ to which both tableaux correspond.}
\label{fig: set-valued jdq equals k-matching rotation}
\end{figure}
\subsection{Jeu de taquin and rotation of generalized non-crossing matchings}
\label{subsec: jdq=rotation general case}
Now consider non-crossing matchings of arbitrary type $\vec{b}$. The difficulty in generalizing Theorem \ref{thm: jdq equals rotation, k-Catalan} to non-constant $\vec{b}$ derives from the fact that the bijection of Proposition \ref{thm: non-crossing matchings vs. set-valued tableaux} is dependent upon the left-to-right ordering of blocks in the non-crossing matchings. As such, repeated application of the rotation operator will eventually permute the ordering of the blocks and require a set-valued tableaux with a different sequence of first-row densities. See Figure \ref{fig: jdq failure, nonconstant weight} for an example of how Theorem \ref{thm: jdq equals rotation, k-Catalan} can fail if generalized to non-constant $\vec{b}$.
\begin{figure}[ht!]
\begin{subfigure}[b]{0.24\textwidth}
\centering
\scalebox{.92}{
\begin{ytableau}
1 \kern+2pt 2 & 4 & 5 \\
3 & 6 & 7
\end{ytableau}}
\vspace{.1in}
\raisebox{5pt}{$\phi$} \scalebox{2.25}{$\downarrow$} \hspace{.02in}
\vspace{.18in}
\scalebox{.92}{
\begin{tikzpicture}
[scale=.55,auto=left,every node/.style={circle,fill=black,inner sep=1.3pt,outer sep=0pt}]
\node[inner sep=0pt] (left) at (.5,0) {};
\node (1) at (1,0) {};
\node (2) at (2,0) {};
\node (3) at (3,0) {};
\node (4) at (4,0) {};
\node (5) at (5,0) {};
\node (6) at (6,0) {};
\node (7) at (7,0) {};
\node[inner sep=0pt] (right) at (7.5,0) {};
\node[inner sep=0pt] (a) at (2,1) {};
\draw[thick] (left) to (right);
\draw[red,thick,bend left=20] (1) to (a);
\draw[red,thick] (2) to (a);
\draw[red,thick,bend right=20] (3) to (a);
\draw[thick] (6,0) arc (0:180:.5);
\draw[thick] (7,0) arc (0:180:1.5);
\node[fill=none] (1l) at (1,-.5) {1};
\node[fill=none] (2l) at (2,-.5) {2};
\node[fill=none] (3l) at (3,-.5) {3};
\node[fill=none] (4l) at (4,-.5) {4};
\node[fill=none] (5l) at (5,-.5) {5};
\node[fill=none] (6l) at (6,-.5) {6};
\node[fill=none] (7l) at (7,-.5) {7};
\end{tikzpicture}}
\end{subfigure}
\begin{subfigure}[b]{0.09\textwidth}
\centering
\scalebox{2.25}{$\longrightarrow$} \raisebox{13pt}{\kern-26pt$p$}
\vspace{.69in}
\raisebox{22pt}{\scalebox{2.25}{$\longrightarrow$} \raisebox{13pt}{\kern-26pt$r$}}
\end{subfigure}
\begin{subfigure}[b]{0.27\textwidth}
\centering
\scalebox{.92}{
\begin{ytableau}
1 \kern+2pt 2 & 3 & 4 \\
5 & 6 & 7
\end{ytableau}}
\vspace{.35in}
\scalebox{.93}{
\begin{tikzpicture}
[scale=.55,auto=left,every node/.style={circle,fill=black,inner sep=1.3pt,outer sep=0pt}]
\node[inner sep=0pt] (left) at (.5,0) {};
\node (1) at (1,0) {};
\node (2) at (2,0) {};
\node (3) at (3,0) {};
\node (4) at (4,0) {};
\node (5) at (5,0) {};
\node (6) at (6,0) {};
\node (7) at (7,0) {};
\node[inner sep=0pt] (right) at (7.5,0) {};
\node[inner sep=0pt] (a) at (2,1.65) {};
\draw[thick] (left) to (right);
\draw[red,thick,bend left=20] (1) to (a);
\draw[red,thick] (2) to (a);
\draw[red,thick,bend right=50] (7) to (a);
\draw[thick] (5,0) arc (0:180:.5);
\draw[thick] (6,0) arc (0:180:1.5);
\node[fill=none] (1l) at (1,-.5) {1};
\node[fill=none] (2l) at (2,-.5) {2};
\node[fill=none] (3l) at (3,-.5) {3};
\node[fill=none] (4l) at (4,-.5) {4};
\node[fill=none] (5l) at (5,-.5) {5};
\node[fill=none] (6l) at (6,-.5) {6};
\node[fill=none] (7l) at (7,-.5) {7};
\end{tikzpicture}}
\end{subfigure}
\begin{subfigure}[b]{0.08\textwidth}
\scalebox{2.15}{\kern-5pt$\longrightarrow$} \raisebox{12pt}{\kern-27pt$\phi$}
\vspace{1.25in}
\end{subfigure}
\begin{subfigure}[b]{0.22\textwidth}
\centering
\scalebox{.92}{
\begin{tikzpicture}
[scale=.55,auto=left,every node/.style={circle,fill=black,inner sep=1.3pt,outer sep=0pt}]
\node[inner sep=0pt] (left) at (.5,0) {};
\node (1) at (1,0) {};
\node (2) at (2,0) {};
\node (3) at (3,0) {};
\node (4) at (4,0) {};
\node (5) at (5,0) {};
\node (6) at (6,0) {};
\node (7) at (7,0) {};
\node[inner sep=0pt] (right) at (7.5,0) {};
\node[inner sep=0pt] (a) at (4,1) {};
\draw[thick] (left) to (right);
\draw[thick,bend left=20] (3) to (a);
\draw[thick] (4) to (a);
\draw[thick,bend right=20] (5) to (a);
\draw[thick] (6,0) arc (0:180:2 and 1.5);
\draw[thick] (7,0) arc (0:180:3 and 2.25);
\node[fill=none] (1l) at (1,-.5) {1};
\node[fill=none] (2l) at (2,-.5) {2};
\node[fill=none] (3l) at (3,-.5) {3};
\node[fill=none] (4l) at (4,-.5) {4};
\node[fill=none] (5l) at (5,-.5) {5};
\node[fill=none] (6l) at (6,-.5) {6};
\node[fill=none] (7l) at (7,-.5) {7};
\end{tikzpicture}}
\vspace{.95in}
\end{subfigure}
\caption{A set-valued tableaux $T$ where $\phi(p(T)) \neq r(\phi(T))$, as rotation of $\phi(T)$ changes the matching's type from $\vec{b} = (3,2,2)$ to $\vec{b}'=(2,2,3)$.}
\label{fig: jdq failure, nonconstant weight}
\end{figure}
Failings such as the one in Figure \ref{fig: jdq failure, nonconstant weight} may be addressed via a slight modification of our jeu de taquin operator, a modification that specializes to our original operator in the case of constant type $\vec{b}$. So take $T \in \svt(n^2,\rho)$, where the density $\rho$ satisfies $\rho_{2,j} = 1$ for all $1 \leq j \leq n$, and assume that $m$ is the smallest integer such that $T$ splits after its $m^{th}$ column. Then define $\widetilde{\rho}$ to be the density satisfying $\widetilde{\rho}_{2,j} = 1$ for all $1 \leq j \leq n$, $\widetilde{\rho}_{1,j} = \rho_{1,j}$ for $1 \leq j < m$, $\widetilde{\rho}_{1,j} = \rho_{1,j+1}$ for $m \leq j < n$, and $\widetilde{\rho}_{1,n} = \rho_{1,m}$. We informally refer to $\widetilde{\rho}$ as the ``rotated density" for $T$. See the first row of Figure \ref{fig: rotational jdq equals rotation} for an illustration of the relationship between $\rho$ and $\widetilde{\rho}$.
We may then define an operator $p_r : \svt(n^2,\rho) \rightarrow \bigcup_{\widetilde{\rho}} \svt(n^2,\widetilde{\rho})$ that applies to any set $\svt(n^2,\rho)$ with a density satisfying $\rho_{2,j} = 1$ for all $j$. For any $T \in \svt(n^2,\rho)$, $p_r(T)$ is obtained as follows:
\begin{enumerate}
\item Identify the smallest positive integer $m$ such that $T$ splits after its $m^{th}$ column.
\item Perform the full set-valued jeu de taquin operation on $T$, yielding $p(T) \in \svt(\lambda,\rho)$.
\item Re-partition entries in the first row of $p(T)$ to produce a tableau $p_r(T) \in \svt(\lambda,\widetilde{\rho})$ with rotated density $\widetilde{\rho}$ determined by the integer $m$ from Step \#1.
\end{enumerate}
To see that a tableau above remains column-standard as we pass from $p(T)$ to $p_r(T)$ in Step \#3, let $c_1 < \cdots < c_n$ denote the second-row entries of $T$. The sole entry to slide upward during Step \#2 is the shifted entry $c_m - 1$ that began at position $(i,j)=(2,m)$. All subsequent second row entries $c_{m+1} - 1, \ldots ,c_n - 1$ are slid one cell leftward. When first-row entries are re-partitioned during Step \#3, entries in the first $m-1$ columns are unmoved whereas entries in columns $m-1$ through $n$ are moved at most one cell leftward (some first row entries may move rightward). It follows that all first-row entries of $p_r(T)$ lie above second-row entries that are at least as large as the entries that appeared below them in $p(T)$.
We refer to the map $p_r$ as \textit{rotational set-valued jeu de taquin}. See the top row of Figure \ref{fig: rotational jeu de taquin example} for an application of $p_r$ that isn't equivalent to our original set-valued jeu de taquin. As seen in the bottom row of Figure \ref{fig: rotational jeu de taquin example}, the passage from $p(T)$ to $p_r(T)$ is precisely the correction needed for set-valued jeu de taquin to correspond to rotation of the associated matchings.
\begin{figure}[ht!]
\centering
\setlength{\tabcolsep}{3.0pt}
\scalebox{.9}{
\begin{tabular}{|c|c|c|c|c|}
\hline
1 & 2 \kern+1pt 3 & \multicolumn{1}{|c?}{5 \kern+1pt 6} & 9 \kern+1pt 10 \kern+1pt 11 & 12 \\ \hline
4 & 7 & \multicolumn{1}{|c?}{8} & 13 & 14 \\ \hline
\end{tabular}}
\hspace{.05in}
\raisebox{-4pt}{
\scalebox{2.}{$\longrightarrow$}}
\hspace{.05in}
\scalebox{.9}{
\begin{tabular}{|c|c|c|c|c|}
\hline
1 & 2 \kern+1pt 4 & 5 \kern+1pt 7 & 8 \kern+1pt 9 \kern+1pt 10 & 11 \\ \hline
3 & 6 & 12 & 13 & 14 \\ \hline
\end{tabular}}
\hspace{.05in}
\raisebox{-4pt}{
\scalebox{2.}{$\longrightarrow$}}
\hspace{.05in}
\scalebox{.9}{
\begin{tabular}{|c|c|c|c|c|}
\hline
1 & 2 \kern+1pt 4 & 5 \kern+1pt 7 \kern+1pt 8 & 9 & 10 \kern+1pt 11 \\ \hline
3 & 6 & 12 & 13 & 14 \\ \hline
\end{tabular}}
\vspace{.15in}
\scalebox{.9}{
\begin{tikzpicture}
[scale=.55,auto=left,every node/.style={circle,fill=black,inner sep=1.3pt,outer sep=0pt}]
\node[inner sep=0pt] (left) at (.5,0) {};
\node (1) at (1,0) {};
\node (2) at (2,0) {};
\node (3) at (3,0) {};
\node (4) at (4,0) {};
\node (5) at (5,0) {};
\node (6) at (6,0) {};
\node (7) at (7,0) {};
\node (8) at (8,0) {};
\node (9) at (9,0) {};
\node (10) at (10,0) {};
\node (11) at (11,0) {};
\node (12) at (12,0) {};
\node (13) at (13,0) {};
\node (14) at (14,0) {};
\node[inner sep=0pt] (right) at (14.5,0) {};
\node[inner sep=0pt] (a) at (2,1.2) {};
\node[inner sep=0pt] (b) at (6,1) {};
\node[inner sep=0pt] (c) at (11.5,1.2) {};
\draw[thick] (left) to (right);
\draw[thick,bend left=20,red] (1) to (a);
\draw[thick] (2) to (a);
\draw[thick,bend right=40] (8) to (a);
\draw[thick] (4,0) arc (0:180:0.5);
\draw[thick,bend left=15] (5) to (b);
\draw[thick] (6) to (b);
\draw[thick,bend right=15] (7) to (b);
\draw[thick] (14,0) arc (0:180:2.5 and 1.8);
\draw[thick,bend left=20] (10) to (c);
\draw[thick,bend left=7] (11) to (c);
\draw[thick,bend right=7] (12) to (c);
\draw[thick,bend right=20] (13) to (c);
\node[fill=none] (1l) at (1,-.5) {1};
\node[fill=none] (2l) at (2,-.5) {2};
\node[fill=none] (3l) at (3,-.5) {3};
\node[fill=none] (4l) at (4,-.5) {4};
\node[fill=none] (5l) at (5,-.5) {5};
\node[fill=none] (6l) at (6,-.5) {6};
\node[fill=none] (7l) at (7,-.5) {7};
\node[fill=none] (8l) at (8,-.5) {8};
\node[fill=none] (9l) at (9,-.5) {9};
\node[fill=none] (10l) at (10,-.5) {10};
\node[fill=none] (11l) at (11,-.5) {11};
\node[fill=none] (12l) at (12,-.5) {12};
\node[fill=none] (13l) at (13,-.5) {13};
\node[fill=none] (14l) at (14,-.5) {14};
\end{tikzpicture}}
\hspace{.1in}
\raisebox{20pt}{
\scalebox{2.1}{$\longrightarrow$}}
\hspace{.1in}
\scalebox{.9}{
\begin{tikzpicture}
[scale=.55,auto=left,every node/.style={circle,fill=black,inner sep=1.3pt,outer sep=0pt}]
\node[inner sep=0pt] (left) at (.5,0) {};
\node (1) at (1,0) {};
\node (2) at (2,0) {};
\node (3) at (3,0) {};
\node (4) at (4,0) {};
\node (5) at (5,0) {};
\node (6) at (6,0) {};
\node (7) at (7,0) {};
\node (8) at (8,0) {};
\node (9) at (9,0) {};
\node (10) at (10,0) {};
\node (11) at (11,0) {};
\node (12) at (12,0) {};
\node (13) at (13,0) {};
\node (14) at (14,0) {};
\node[inner sep=0pt] (right) at (14.5,0) {};
\node[inner sep=0pt] (a) at (7,1.6) {};
\node[inner sep=0pt] (b) at (5,1) {};
\node[inner sep=0pt] (c) at (10.5,1.2) {};
\draw[thick] (left) to (right);
\draw[thick,bend left=30] (1) to (a);
\draw[thick] (7) to (a);
\draw[thick,bend right=45,red] (14) to (a);
\draw[thick] (3,0) arc (0:180:0.5);
\draw[thick,bend left=15] (4) to (b);
\draw[thick] (5) to (b);
\draw[thick,bend right=15] (6) to (b);
\draw[thick] (13,0) arc (0:180:2.5 and 1.8);
\draw[thick,bend left=20] (9) to (c);
\draw[thick,bend left=7] (10) to (c);
\draw[thick,bend right=7] (11) to (c);
\draw[thick,bend right=20] (12) to (c);
\node[fill=none] (1l) at (1,-.5) {1};
\node[fill=none] (2l) at (2,-.5) {2};
\node[fill=none] (3l) at (3,-.5) {3};
\node[fill=none] (4l) at (4,-.5) {4};
\node[fill=none] (5l) at (5,-.5) {5};
\node[fill=none] (6l) at (6,-.5) {6};
\node[fill=none] (7l) at (7,-.5) {7};
\node[fill=none] (8l) at (8,-.5) {8};
\node[fill=none] (9l) at (9,-.5) {9};
\node[fill=none] (10l) at (10,-.5) {10};
\node[fill=none] (11l) at (11,-.5) {11};
\node[fill=none] (12l) at (12,-.5) {12};
\node[fill=none] (13l) at (13,-.5) {13};
\node[fill=none] (14l) at (14,-.5) {14};
\end{tikzpicture}}
\caption{Rotational set-valued jeu de taquin applied to a tableau $T \in \svt(5^2,\rho)$ that splits after its third column, as well as a comparison of $\phi(T)$ with $\phi(p_r(T))$.}
\label{fig: rotational jeu de taquin example}
\end{figure}
\begin{theorem}
\label{thm: rotational jdq equals rotation}
Fix $n \geq 1$, and take any density $\rho$ such that $\rho_{2,j} =1$ for all $1 \leq j \leq n$. For any $T \in \svt(n^2,\rho)$ with rotated density $\widetilde{\rho}$, define $\vec{b} = (\rho_{1,1}+1,\ldots,\rho_{1,n}+1)$ and $\vec{b}' = (\widetilde{\rho}_{1,1}+1,\ldots,\widetilde{\rho}_{1,n}+1)$. If $\phi: \svt(n^2,\rho) \rightarrow \mathcal{M}_{\vec{b}}$ and $\phi': \svt(n^2,\widetilde{\rho}) \rightarrow \mathcal{M}_{\vec{b}'}$ are defined as in the proof of Proposition \ref{thm: non-crossing matchings vs. set-valued tableaux}, then $\phi'(p_r(T)) = r(\phi(T))$.
\end{theorem}
\begin{proof}
The operator $p_r$ has been defined so that $\phi'(p_r(T))$ and $r(\phi(T))$ both lie in $\mathcal{M}_{\vec{b}'}$. See Figure \ref{fig: rotational jdq equals rotation} for a demonstration of this phenomenon. An equivalent argument to Theorem \ref{thm: jdq equals rotation, k-Catalan} shows that the blocks of $\phi'(p_r(T))$ and $r(\phi(T))$ have the same right endpoints, at identical locations. As the blocks of $\phi'(p(r(T))$ and $r(\phi(T))$ cannot intersect, all that remains to be shown is that each of those right endpoints (when ordered from left-to-right) is associated with a block of equivalent size in both matchings. Yet this follows directly from the fact that both $\phi'(p_r(T))$ and $r(\phi(T))$ are matchings of weight $\vec{b}'$.
\end{proof}
\begin{figure}[ht!]
\begin{subfigure}[b]{0.44\textwidth}
\centering
\setlength{\tabcolsep}{2.5pt}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
$\rho_1$ & $\cdots$ & $\rho_{m-1}$ & \multicolumn{1}{|c?}{$\rho_m$} & $\rho_{m+1}$ & $\cdots$ & $\rho_n$ \\ \hline
1 & $\cdots$ & 1 & \multicolumn{1}{|c?}{1} & 1 & $\cdots$ & 1 \\ \hline
\end{tabular}
\vspace{.43in}
\raisebox{4pt}{
\begin{tikzpicture}
[scale=.62,auto=left,every node/.style={circle,fill=black,inner sep=0pt,outer sep=0pt}]
\node[inner sep=0pt] (left) at (.5,0) {};
\node (1) at (1,0) {};
\node (6) at (6,0) {};
\node (right) at (10.5,0) {};
\draw[thick] (left) to (right);
\node (a) at (3.5,2.3) {};
\node (b1) at (2.5,1.5) {};
\node (b2) at (3.5,1.5) {};
\node (b3) at (4.5,1.5) {};
\draw[thick,bend left=40,red] (1) to (a);
\draw[thick,bend right=40] (6) to (a);
\draw[thick,bend left=10] (b1) to (a);
\draw[thick] (b2) to (a);
\draw[thick,bend right=10] (b3) to (a);
\draw[fill=gray!50!] (2,0) rectangle (5,1.5);
\draw[fill=gray!50!] (6.7,0) rectangle (9.7,1.5);
\node[fill=none] (xl) at (6,-.5) {x};
\node[fill=none] (B1) at (3.5,.75) {\scalebox{1.5}{$B_1$}};
\node[fill=none] (B2) at (8.2,.75) {\scalebox{1.5}{$B_2$}};
\end{tikzpicture}}
\end{subfigure}
\begin{subfigure}[b]{0.1\textwidth}
\centering
\scalebox{2.15}{$\longrightarrow$}
\vspace{.77in}
\scalebox{2.15}{$\longrightarrow$}
\vspace{.4in}
\end{subfigure}
\begin{subfigure}[b]{0.44\textwidth}
\centering
\setlength{\tabcolsep}{2.5pt}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
$\rho_1$ & $\cdots$ & $\rho_{m-1}$ & $\rho_{m+1}$ & $\cdots$ & $\rho_n$ & $\rho_m$ \\ \hline
1 & $\cdots$ & 1 & 1 & $\cdots$ & 1 & 1 \\ \hline
\end{tabular}
\vspace{.09in}
\begin{tikzpicture}
[scale=.62,auto=left,every node/.style={circle,fill=black,inner sep=0pt,outer sep=0pt}]
\node[inner sep=0pt] (left) at (.5,0) {};
\node (5) at (5,0) {};
\node (10) at (10,0) {};
\node (right) at (10.5,0) {};
\draw[thick] (left) to (right);
\node (a) at (3.5,2.6) {};
\node (b1) at (1.5,1.5) {};
\node (b2) at (2.5,1.5) {};
\node (b3) at (3.5,1.5) {};
\draw[thick,bend right=20] (5) to (a);
\draw[thick,bend right=45,red] (10) to (a);
\draw[thick,bend left=15] (b1) to (a);
\draw[thick,bend left=10] (b2) to (a);
\draw[thick] (b3) to (a);
\draw[fill=gray!50!] (1,0) rectangle (4,1.5);
\draw[fill=gray!50!] (5.7,0) rectangle (8.7,1.5);
\node[fill=none] (xl) at (5,-.5) {x-1};
\node[fill=none] (B1) at (2.5,.75) {\scalebox{1.5}{$B_1$}};
\node[fill=none] (B2) at (7.2,.75) {\scalebox{1.5}{$B_2$}};
\end{tikzpicture}
\end{subfigure}
\caption{Density $\rho$ and rotated density $\widetilde{\rho}$ for a tableau $T$ whose leftmost split occurs after its $m^{th}$ column. The bottom row demonstrates how rotation of $\phi(T)$ reorders rightmost endpoints of blocks in a manner consistent with the relationship between $\rho$ and $\widetilde{\rho}$. Here $x = \rho_1 + \cdots + \rho_m + m$.}
\label{fig: rotational jdq equals rotation}
\end{figure}
\section{Enumeration of jeu de taquin equivalence classes}
\label{sec: enumeration}
In this section we restrict our attention to sets $\svt(n^2,\rho)$ with row-constant density $\rho$ of the form $\rho_{1,j} = k-1, \rho_{2,j}=1$, and look to provide closed formulas for the number of jeu de taquin equivalence classes in $\widetilde{\svt}(n^2,\rho)$. Via Corollary \ref{thm: jdq equals rotation corollary, k-Catalan} this is equivalent to enumerating $\widetilde{\mathcal{M}}_n^k$ for any $n \geq 1, k \geq 2$, meaning that our formulas should specialize to Eq.\ \eqref{eq: Goldbach and Tijdeman k=2} in the case of $k=2$.
As $\widetilde{\mathcal{M}}_n^k$ may be defined via a cyclic action of $\Z_{nk}$ on $\mathcal{M}_n^k$, we utilize pre-existing machinery for investigating that action. We present two distinct methods that yield equivalent yet vastly different looking summations for $| \widetilde{\mathcal{M}}_n^k |$. In Subsection \ref{subsec: enumeration cyclic sieving} we apply the cyclic sieving phenomenon in a manner than relies upon Bodnar and Rhodes \cite{BR}. In Subsection \ref{subsec: enumeration direct} we take a more direct combinatorial approach in the flavor of Goldbach and Tijdeman \cite{GT}. Although cyclic sieving yields an enumeration with far less effort, the methodology of the direct approach reveals more about the combinatorial structure of $\mathcal{M}_n^k$ and admits a major simplification when $k$ is prime. The authors are unsure how the $q$-Catalan evaluations of Subsection \ref{subsec: enumeration cyclic sieving} may be reduced to the binomial coefficients of Subsection \ref{subsec: enumeration direct}.
With both of our methods relying upon Burnside's lemma, we pause to recap that classic result. Burnside's lemma, also known as the Cauchy-Frobenius lemma, applies whenever a finite group $G$ acts upon a set $A$. The lemma states that the number of orbits with respect to the action, namely $| A/G |$, is equal to the average size of all sets $A^g = \lbrace a \in A \vert ga=a \rbrace$. That is, $| A/G | = \frac{1}{| G |} \sum_{g \in G} | A^g |$.
In our situation let $A = \mathcal{M}_n^k$ and $G = \Z_{nk}$, with left action of $g \in \Z_{nk}$ on $M \in \mathcal{M}_n^k$ given by $g$ applications of the rotation operator, namely $g \cdot M = r^g(M)$. The orbits of this action are clearly the set of circular non-crossing $k$-point matchings $\widetilde{\mathcal{M}}_n^k$. In order to determine $| \widetilde{\mathcal{M}}_n^k |$, it is then our task to determine $| A^g |$ for arbitrary $g \in \Z_{nk}$. For any $g \in \Z_{nk}$, we henceforth refer to an element $M \in A^g$ as a \textit{$k$-equal non-crossing matching of order $g$}.
See Table \ref{tab: jdq enumeration} for values of $| \widetilde{\mathcal{M}}_n^k |$, all of which were calculated in Maple 18 via Theorem \ref{thm: circular k-point matching enumeration}. The $k=2$ row of that table predictably corresponds to \seqnum{A002995}. All later rows reveal a surprising correspondence to the numbers of $k$-gonal cacti having $n$ polygons, as studied by B\'ona, Bousquet, Labelle, and Leroux \cite{BBLL}. In particular, later rows of Table \ref{tab: jdq enumeration} appear as \seqnum{A054423} ($k=3$), \seqnum{A054362} ($k=4$), \seqnum{A054365} ($k=5$), and \seqnum{A054368} ($k=6$). Finding an explicit bijection between our jeu de taquin equivalence classes and these $k$-gonal cacti
is an interesting topic for future investigation. Note that, even if an elementary bijection were to exist, our approach has the advantage that it may be easily generalized to rectangular set-valued tableaux of distinct densities, yielding sequences that may not correspond to known statistics on $k$-gonal cacti.
\begin{table}[ht!]
\centering
\small
\renewcommand{\arraystretch}{1.25}
\setlength{\tabcolsep}{6pt}
\begin{tabular}{>{$}c<{$}| >{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$} >{$}c<{$}}
& n=1 & n=2 & n=3 & n=4 & n=5 & n=6 & n=7 & n=8 & n=9 & n=10 \\ \hline
k=2 & 1 & 1 & 2 & 3 & 6 & 14 & 34 & 95 & 280 & 854 \\
k=3 & 1 & 1 & 2 & 7 & 19 & 86 & 372 & 1825 & 9143 & 47801 \\
k=4 & 1 & 1 & 3 & 11 & 52 & 307 & 1936 & 13207 & 93496 & 683988 \\
k=5 & 1 & 1 & 3 & 17 & 102 & 811 & 6626 & 58385 & 532251 & 5011934 \\
k=6 & 1 & 1 & 4 & 25 & 187 & 1772 & 17880 & 191967 & 2141232 & 24640989 \\
k=7 & 1 & 1 & 4 & 33 & 300 & 3412 & 40770 & 518043 & 6830545 & 92909684 \\
k=8 & 1 & 1 & 5 & 43 & 463 & 5993 & 82887 & 1213879 & 18471584 & 289883603
\end{tabular}
\caption{$| \widetilde{\svt} (n^2,\rho | = | \widetilde{\mathcal{M}}_n^k |$ for $\rho$ the row-constant density $\rho_{1,j} = k-1$, $\rho_{2,j} = 1$.}
\label{tab: jdq enumeration}
\end{table}
In all that follows we use standard notation for the $q$-number $[p]_q = 1+q+\cdots+q^{p-1}$, the $q$-factorial $[p]_q! = [1]_q [2]_q \cdots [p]_q$, and the $q$-binomial coefficient $\binom{a}{b}_q = \frac{[a]_q!}{[b]_q! [a-b]_q!}$.
\subsection{Enumeration via cyclic sieving}
\label{subsec: enumeration cyclic sieving}
As defined by Reiner, Stanton, and White \cite{RSW}, cyclic sieving is a phenomenon that may be associated with the action of a cyclic group $G = \langle c \rangle$ upon a finite set $X$. For $X(q) \in \N(q)$ and $\omega \in \C$ a root of unity of order $| G |$, the ordered triple $(X,G,X(q))$ exhibits cyclic sieving if $X(\omega^d) = | X^{c^d} | = \lbrace x \in X \vert c^d x = x \rbrace$.
For relatively prime positive integers $a** 1$, a matching $M \in A^g$ must decompose into $nk/d$ ``sub-matchings" on $d$ points, each of which follows an identical pattern in how it divides its endpoints among $k$-stars. Notice that these sub-matchings need not define non-crossing $k$-point matchings on $d$ points when considered individually, as they may contain ``outgoing" strands from $k$-stars whose endpoints are divided between multiple sub-matchings. We refer to the process by which sub-matchings are pieced together to create $M \in A^g$ as horizontal concatenation, and write $q_j(M) = m$ if $j$ copies of $m$ horizontally concatenate to produce $M$. See Figure \ref{fig: sub-matching example} for several sub-matchings and their corresponding $k$-point matchings.
\begin{figure}[ht!]
\centering
\begin{tikzpicture}
[scale=.40,auto=left,every node/.style={circle,fill=black,inner sep=1.3pt,outer sep=0pt}]
\node[inner sep=0pt] (left) at (.5,0) {};
\node (1) at (1,0) {};
\node (2) at (2,0) {};
\node (3) at (3,0) {};
\node (4) at (4,0) {};
\node (5) at (5,0) {};
\node (6) at (6,0) {};
\node (7) at (7,0) {};
\node[inner sep=0pt] (right) at (7.5,0) {};
\draw[thick] (left) to (right);
\node[inner sep=0pt] (a) at (5,1) {};
\node[inner sep=0pt] (b) at (7,1.5) {};
\draw[thick, bend left=20] (4) to (a);
\draw[thick] (5) to (a);
\draw[thick, bend right=20] (6) to (a);
\draw[thick, bend left=35] (3) to (b);
\draw[thick] (7) to (b);
\draw[thick, bend right=45, ->] (1) to (-0.25,1.5);
\draw[thick, ->] (b) to (8,1.5);
\draw[thick, ->] (2) to (2,3);
\draw[red] (0.5,-0.5) rectangle (7.5,2.5);
\end{tikzpicture}
\hspace{.2in}
\raisebox{14pt}{\scalebox{3}{$\Rightarrow$}}
\hspace{.15in}
\begin{tikzpicture}
[scale=.40,auto=left,every node/.style={circle,fill=black,inner sep=1.3pt,outer sep=0pt}]
\node[inner sep=0pt] (left) at (.5,0) {};
\node (1) at (1,0) {};
\node (2) at (2,0) {};
\node (3) at (3,0) {};
\node (4) at (4,0) {};
\node (5) at (5,0) {};
\node (6) at (6,0) {};
\node (7) at (7,0) {};
\node (8) at (8,0) {};
\node (9) at (9,0) {};
\node (10) at (10,0) {};
\node (11) at (11,0) {};
\node (12) at (12,0) {};
\node (13) at (13,0) {};
\node (14) at (14,0) {};
\node (15) at (15,0) {};
\node (16) at (16,0) {};
\node (17) at (17,0) {};
\node (18) at (18,0) {};
\node (19) at (19,0) {};
\node (20) at (20,0) {};
\node (21) at (21,0) {};
\node[inner sep=0pt] (right) at (21.5,0) {};
\draw[thick] (left) to (right);
\node[inner sep=0pt] (a1) at (5,1) {};
\node[inner sep=0pt] (b1) at (7,1.5) {};
\node[inner sep=0pt] (a2) at (12,1) {};
\node[inner sep=0pt] (b2) at (14,1.5) {};
\node[inner sep=0pt] (a3) at (19,1) {};
\node[inner sep=0pt] (b3) at (17,2.5) {};
\node[inner sep=0pt] (c) at (9,3) {};
\draw[thick, bend left=20] (4) to (a1);
\draw[thick] (5) to (a1);
\draw[thick, bend right=20] (6) to (a1);
\draw[thick, bend left=20] (11) to (a2);
\draw[thick] (12) to (a2);
\draw[thick, bend right=20] (13) to (a2);
\draw[thick, bend left=20] (18) to (a3);
\draw[thick] (19) to (a3);
\draw[thick, bend right=20] (20) to (a3);
\draw[thick, bend left=40] (3) to (b1);
\draw[thick] (7) to (b1);
\draw[thick, bend right=30] (8) to (b1);
\draw[thick, bend left=40] (10) to (b2);
\draw[thick] (14) to (b2);
\draw[thick, bend right=30] (15) to (b2);
\draw[thick, bend left=30] (2) to (c);
\draw[thick] (9) to (c);
\draw[thick, bend right=30] (16) to (c);
\draw[thick, bend left=40] (1) to (b3);
\draw[thick] (17) to (b3);
\draw[thick, bend right=30] (21) to (b3);
\draw[red] (7.5,-0.5) rectangle (14.5,2.5);
\end{tikzpicture}
\vspace{.3in}
\begin{tikzpicture}
[scale=.40,auto=left,every node/.style={circle,fill=black,inner sep=1.3pt,outer sep=0pt}]
\node[inner sep=0pt] (left) at (.5,0) {};
\node (1) at (1,0) {};
\node (2) at (2,0) {};
\node (3) at (3,0) {};
\node (4) at (4,0) {};
\node (5) at (5,0) {};
\node (6) at (6,0) {};
\node (7) at (7,0) {};
\node[inner sep=0pt] (right) at (7.5,0) {};
\draw[thick] (left) to (right);
\node[inner sep=0pt] (a) at (4,1) {};
\node[inner sep=0pt] (b) at (6,1.5) {};
\draw[thick, bend left=20] (3) to (a);
\draw[thick] (4) to (a);
\draw[thick, bend right=20] (5) to (a);
\draw[thick, bend left=35] (2) to (b);
\draw[thick] (6) to (b);
\draw[thick, bend right=35] (7) to (b);
\draw[thick, ->] (1) to (1,3);
\draw[red] (0.5,-0.5) rectangle (7.5,2.5);
\end{tikzpicture}
\hspace{.2in}
\raisebox{14pt}{\scalebox{3}{$\Rightarrow$}}
\hspace{.15in}
\begin{tikzpicture}
[scale=.40,auto=left,every node/.style={circle,fill=black,inner sep=1.3pt,outer sep=0pt}]
\node[inner sep=0pt] (left) at (.5,0) {};
\node (1) at (1,0) {};
\node (2) at (2,0) {};
\node (3) at (3,0) {};
\node (4) at (4,0) {};
\node (5) at (5,0) {};
\node (6) at (6,0) {};
\node (7) at (7,0) {};
\node (8) at (8,0) {};
\node (9) at (9,0) {};
\node (10) at (10,0) {};
\node (11) at (11,0) {};
\node (12) at (12,0) {};
\node (13) at (13,0) {};
\node (14) at (14,0) {};
\node (15) at (15,0) {};
\node (16) at (16,0) {};
\node (17) at (17,0) {};
\node (18) at (18,0) {};
\node (19) at (19,0) {};
\node (20) at (20,0) {};
\node (21) at (21,0) {};
\node[inner sep=0pt] (right) at (21.5,0) {};
\draw[thick] (left) to (right);
\node[inner sep=0pt] (a1) at (4,1) {};
\node[inner sep=0pt] (b1) at (6,1.5) {};
\node[inner sep=0pt] (a2) at (11,1) {};
\node[inner sep=0pt] (b2) at (13,1.5) {};
\node[inner sep=0pt] (a3) at (18,1) {};
\node[inner sep=0pt] (b3) at (20,1.5) {};
\node[inner sep=0pt] (c) at (8,3) {};
\draw[thick, bend left=20] (3) to (a1);
\draw[thick] (4) to (a1);
\draw[thick, bend right=20] (5) to (a1);
\draw[thick, bend left=20] (10) to (a2);
\draw[thick] (11) to (a2);
\draw[thick, bend right=20] (12) to (a2);
\draw[thick, bend left=20] (17) to (a3);
\draw[thick] (18) to (a3);
\draw[thick, bend right=20] (19) to (a3);
\draw[thick, bend left=40] (2) to (b1);
\draw[thick] (6) to (b1);
\draw[thick, bend right=30] (7) to (b1);
\draw[thick, bend left=40] (9) to (b2);
\draw[thick] (13) to (b2);
\draw[thick, bend right=30] (14) to (b2);
\draw[thick, bend left=40] (16) to (b3);
\draw[thick] (20) to (b3);
\draw[thick, bend right=30] (21) to (b3);
\draw[thick, bend left=30] (1) to (c);
\draw[thick] (8) to (c);
\draw[thick, bend right=30] (15) to (c);
\draw[red] (7.5,-0.5) rectangle (14.5,2.5);
\end{tikzpicture}
\caption{Non-crossing $3$-point matchings $M_1,M_2 \in \mathcal{M}_7^3$ of order $7$, constructed from their sub-matchings $q_3(M_1),q_3(M_2)$. Notice that $r(M_1) = M_2$, implying that their associated set-valued tableaux are jeu de taquin equivalent.}
\label{fig: sub-matching example}
\end{figure}
Our strategy is to place $A^g$ in bijection with certain sets of sub-matchings on $d$ points, using the map $q_{nk/d}$. This map $q_{nk/d}$ is injective for any $g \in \Z_{nk}$, as distinct matchings must feature distinct patterns in their sub-matchings. The difficulty is then in describing $\im(q_{nk/d})$, as not all potential sub-matchings may be horizontally concatenated when one allows for outgoing strands.
So consider the $nk/d$ sub-matchings of $M \in A^g$ as if they were ordered cyclically. As our matchings are non-crossing, it is not possible for a $k$-star of $M$ to have identically placed endpoints in more than two sub-matchings unless it has endpoints in all $nk/d$ sub-matchings. Furthermore, $M$ can contain at most one ``topmost" $k$-star with identically placed endpoints in all $nk/d$ sub-matchings. These observations allow us to place all outgoing strands into two basic categories. ``Unpaired" outgoing strands belong to the $k$-star of $M$ whose $k$ endpoints are equivalently partitioned within every sub-matching. ``Paired" outgoing strands belong to $k$-stars of $M$ whose endpoints are split between precisely two sub-matchings, with the ``left-bound" and ``right-bound" strands of each pair connecting to distinctly positioned endpoints within their respective sub-matchings.\footnote{The apparent ambiguity in the case of $nk/d = 2$ is eliminated by our requirement that any fixed $k$-star associated with paired strands cannot have identically placed endpoints within each sub-matching.}
See the top matching of Figure \ref{fig: sub-matching example} for an example of sub-matchings with paired and unpaired strands. When depicting sub-matchings, unpaired strands will always be drawn as vertical rays.
It is immediate that any sub-matching in $\im(q_{nk/d})$ must feature the same number of left-bound and right-bound outgoing strands. Delaying a consideration of unpaired strands, let $m^k(d,x)$ denote the set of non-crossing $k$-point sub-matchings on $d$ points that contain precisely $x$ unpaired outgoing strands as well as identical numbers of right-bound and left-bound strands.
\begin{lemma}
\label{thm: sub-matching enumeration}
Fix $k \geq 2$, $d \geq 1$, and $x \geq 0$. Then
$$| m^k(d,x) | =
\begin{cases}
\displaystyle{\binom{d}{(d-x)/k}}, & \text{if $k \mid (d-x)$;}\\
0, & \text{if $k \nmid (d-x)$.}
\end{cases}$$
\end{lemma}
\begin{proof}
As any $m \in m^k(d,x)$ contains $d-x$ endpoints that aren't associated with unpaired strands, $| m^k(d,x) | = 0$ if $k \mid (d-x)$. When $k \mid (d-x)$, we define a bijection $\psi: m^k(d,x) \rightarrow S$ with the set $S$ of ordered $d$-tuples in $\lbrace R,L \rbrace$ that contain precisely $(d-x)/k$ copies of $R$.
For any $m \in m^k(d,x)$, identify the rightmost endpoint of each $k$-star that doesn't include an unpaired strand, assuming that $k$-stars involving left-bound (resp. right-bound) outgoing strands include more leftward (resp. rightward) endpoints. There will always be $(d-x)/k$ such rightmost endpoints. Then define the $d$-tuple $\psi(M)$ by associating our our rightmost endpoints with $R$ coordinates and all other endpoints with $L$ coordinates.
The map $\psi$ is clearly injective. To show $\psi$ is bijective we define an injective map $\psi^{-1}: S \rightarrow m^k(d,x)$. So take any $d$-tuple $\vec{v} \in S$ and consider its coordinates as if they were ordered cyclically. We construct $\psi^{-1}(\vec{v})$ one $k$-star at a time, from the ``innermost" $k$-stars outward. As $\vec{v}$ contains at most $d/k$ copies of $R$, there will be at least one length-$k$ sub-string of the form $L L \cdots L R$. Identify the substring of this form whose $R$ entry lies farthest to the right, and place a $k$-star in $\psi^{-1}(\vec{v})$ whose endpoints lie at the coordinates in that sub-string. Notice that if our distinguished sub-string ``wraps around" the end of $\vec{v}$, the resulting $k$-star will include paired outgoing strands. Recursively apply the process above for the substring of $\vec{v}$ whose endpoints have not yet been assigned to a $k$-star. This will eventually leave $x$ total $L$ coordinates, which we associate with the endpoints of unpaired outgoing strands.
\end{proof}
It is easy to see that $m^k(d,0) \subseteq \im(q_{nk/d})$ for all $g \in \Z_{nk}$ with $\gcd(g,nk) = d > 1$, as horizontal concatenation merely involves an identification of right-bound outgoing strands with left-bound outgoing strands. It is only left to determine when $m^k(d,x) \subseteq \im(q_{nk/d})$ in the case of $x > 0$:
\begin{lemma}
\label{thm: topbound strands lemma}
Fix $k \geq 2$ and non-zero $g \in \Z_{nk}$ with $\gcd(g,nk) = d > 1$. Then $m^k(d,x) \subseteq \im(q_{nk/d})$ if and only if either
\begin{enumerate}
\item $x=0$, or
\item $x=\frac{d}{n}$ and $\frac{nk}{d}$ is a non-trivial divisor of $\gcd(k,n-1)$.
\end{enumerate}
\end{lemma}
\begin{proof}
Assume $\frac{nk}{d} > 1$ and that a sub-matching $m \in m^k(d,x)$ with $q_{nk/d}(M)=m$ has unpaired outgoing strands. We have already established that all unpaired strands, across all sub-matchings of $M$, must belong to the same $k$-star. With $k$ total unpaired strands for $\frac{nk}{d}$ sub-matchings, it follows that $\frac{nk}{d} \mid k$ and that $m$ contains precisely $x = \frac{d}{n}$ unpaired strands. This leaves $d - \frac{d}{n}$ endpoints that are not unpaired outgoing strands, further requiring that $k \mid (d - \frac{d}{n})$ and hence that $\frac{nk}{d} \mid (n-1)$. Whenever $\frac{nk}{d} \mid \gcd(k,n-1)$, $\frac{nk}{d}$ copies of $m \in m^k(d,\frac{d}{n})$ may always be horizontally concatenated to produce a matching $M$. To do this, simply identify right-bound strands with left-bound strands in the unique non-crossing manner, and then identify all unpaired strands with a single topmost $k$-star.
\end{proof}
In the horizontal concatenation of $m \in m^k(d,\frac{d}{n})$ from the proof of Lemma \ref{thm: topbound strands lemma}, observe that the ``topmost" $k$-star composed of unpaired outgoing strands need not lie at the ``top" of $M \in A^g$. If $m$ also has paired outgoing strands, left-bound strands from the leftmost sub-matching will wrap around the topmost $k$-star on their way to the rightmost sub-matching. We are now ready to characterize $\im(q_{nk/d})$ and calculate $| \widetilde{\mathcal{M}}_n^k |$:
\begin{lemma}
\label{thm: fixed sets vs. sub-matchings}
Fix $k \geq 2$ and non-zero $g \in \Z_{nk}$ with $\gcd(g,nk) = d > 1$. Then $| A^g | = \displaystyle{\binom{d}{d/k} + \binom{d}{(d-\frac{d}{n})/k}}$, where binomial coefficients involving non-integers are taken to be zero.
\end{lemma}
\begin{proof}
Lemma \ref{thm: topbound strands lemma} and the observation that $m^k(d,x) = \emptyset$ if $k \nmid (d-x)$ allow us to assert that
\begin{equation}
\label{eq: fixed set lemma 1}
\im(q_{nk/d})=
\begin{cases}
m^k(d,0), & \text{if $\frac{nk}{d} \nmid \gcd(k,n-1)$;}\\
m^k(d,0) + m^k(d,\frac{d}{n}), & \text{if $\frac{nk}{d} \mid \gcd(k,n-1)$.}
\end{cases}
\end{equation}
Since $q_{nk/d}$ is an injection, applying Lemma \ref{thm: sub-matching enumeration} to Eq.\ \eqref{eq: fixed set lemma 1} gives
\begin{equation}
\label{eq: fixed set lemma 2}
| A^g | =
\begin{cases}
\displaystyle{\binom{d}{d/k}},
& \text{if $\frac{nk}{d} \nmid \gcd(k,n-1)$;}\\[15 pt]
\displaystyle{\binom{d}{d/k} + \binom{d}{(d-\frac{d}{n})/k}},
& \text{if $\frac{nk}{d} \mid \gcd(k,n-1)$.}
\end{cases}
\end{equation}
In Eq.\ \eqref{eq: fixed set lemma 2} and in all subsequent equations, binomial coefficients are taken to be zero if their bottom entry is not an integer.
As $k,n,d$ are non-zero integers such that $\frac{nk}{d} \in \Z$, we know that $\frac{nk}{d} \mid k$ if and only if $n \mid d$. This implies that, if $\frac{nk}{d} \nmid k$, then $(d - \frac{d}{n}) \notin \Z$ and hence that $(d - \frac{d}{n})/k \notin \Z$. Similarly, if $\frac{nk}{d} \nmid (n-1)$ we may conclude that $nk \nmid (dn-d)$ and hence that $k \nmid (d-\frac{d}{n})$. Combining these observations, we may conclude that $k \nmid (d-\frac{d}{n})$ whenever $\frac{nk}{d} \nmid \gcd(k,n-1)$. This allows us to add the missing second binomial coefficient (necessarily zero) to the first case of Eq.\ \eqref{eq: fixed set lemma 2} and drop all conditional statements.
\end{proof}
\begin{theorem}
\label{thm: circular k-point matching enumeration}
Fix $k \geq 2$, $n \geq 1$, and let $\rho$ be the row-constant density with $\rho_{1,j} = k-1$ and $\rho_{2,j}=1$ for all $j$. Then
$$| \widetilde{\svt}(n^2,\rho) | = | \widetilde{\mathcal{M}}_n^k | = \frac{1}{nk} \sum_{d \mid nk} \varphi(nk/d) \left( \binom{d}{d/k} + \binom{d}{(d-\frac{d}{n})/k} \right) \ - \ C_n^k.$$
Here $\varphi$ is Euler's phi function and binomial coefficients involving non-integers are zero.
\end{theorem}
\begin{proof}
By Burnside's lemma applied to $A = \mathcal{M}_n^k$ and $G = \Z_{nk}$ we have
\begin{equation}
\label{eq: GT theorem 1}
| \widetilde{\mathcal{M}}_n^k | = \frac{1}{nk} | A^0 | + \frac{1}{nk} \sum_{g \neq 0} | A^g | = \frac{1}{nk} C_n^k + \frac{1}{nk} \sum_{g \neq 0} | A^g | .
\end{equation}
We have already argued that $| A^g | = 0$ if $\gcd(g,nk) = 1$. For any $d \mid nk$ with $d > 1$, basic number theory states that there are precisely $\varphi(\frac{nk}{d})$ elements $g \in \Z_{nk}$ such that $\gcd(g,nk)=d$. Ranging over all non-zero divisors $d$ of $nk$ allows us to rewrite Eq.\ \eqref{eq: GT theorem 1} as
\begin{equation}
\label{eq: GT theorem 2}
| \widetilde{\mathcal{M}}_n^k | = \frac{1}{nk}C_n^k + \frac{1}{nk} \sum_{d \mid nk, d \neq nk} \varphi(nk/d) | A^d |.
\end{equation}
Applying Lemma \ref{thm: fixed sets vs. sub-matchings}, note that the $d=nk$ case gives $\varphi(nk/d) \left( \binom{d}{d/k} + \binom{d}{(d-\frac{d}{n})/k} \right) = \varphi(1) \left( \binom{nk}{n} + \binom{nk}{n-1} \right) = (1) \binom{nk+1}{n} = (nk+1) C_n^k$. Forcing the $d=nk$ case into our sum gives
\begin{equation}
\label{eq: GT theorem 3}
| \widetilde{\mathcal{M}}_n^k | = \frac{1}{nk}C_n^k + \frac{1}{nk} \sum_{d \mid nk} \varphi(nk/d) \left( \binom{d}{d/k} + \binom{d}{(d-\frac{d}{n})/k} \right) - \frac{nk+1}{nk}C_n^k .
\end{equation}
\end{proof}
One specific advantage of Theorem \ref{thm: circular k-point matching enumeration} over Theorem \ref{thm: enumeration, cyclic sieving} is that the summation of Theorem \ref{thm: circular k-point matching enumeration} may be significantly simplified when $k$ is prime. Notice that Corollary \ref{thm: Goldbach Tijdeman corollary} recovers Goldbach and Tijdeman's original result of Eq.\ \eqref{eq: Goldbach and Tijdeman k=2} when $k=2$.
\begin{corollary}
\label{thm: Goldbach Tijdeman corollary}
Fix $k \geq 2$ and let $p$ be prime. Then
$$| \widetilde{\mathcal{M}}_n^p | = \left( \frac{1}{np} \sum_{d \mid n} \varphi(n/d) \binom{pd}{d} \right) - \frac{p-1}{p} C_n^p + \frac{p-1}{p} C_{(n-1)/p}^p.$$
Here $\varphi$ is Euler's phi function and $p$-Catalan numbers with non-integer subscripts are zero.
\end{corollary}
\begin{proof}
Theorem \ref{thm: circular k-point matching enumeration} immediately gives
\begin{equation}
\label{eq: GT corollary 1}
| \widetilde{\mathcal{M}}_n^p | = \frac{1}{np} \sum_{d \mid np, d \neq np} \varphi(np/d) \left( \binom{d}{d/p} + \binom{d}{(d-\frac{d}{n})/p} \right) + \frac{1}{np} C^p_n.
\end{equation}
Whenever $p \nmid d$, $\binom{d}{d/p} = 0$. In this case we also have $(d-\frac{d}{n})/p \in \Z$ only if $n \mid d$, which requires $d = n$ since $p$ is prime. It follows that $\binom{d}{(d-\frac{d}{n})/p} \neq 0$ only if $\binom{d}{(d-\frac{d}{n})/p} = \binom{n}{(n-1)/p}$ and $p \mid (d-1)$. Alternatively, when $p \mid d$ we may assert that $d = pm$ for some $m$ with $m \mid n$. For $p \mid d$, also note that $\binom{d}{(d-\frac{d}{n})/p} = \binom{pm}{(m - \frac{m}{n}} \neq 0$ only when $n \mid m$ and hence when $m = n$, a case that is excluded from our summation. Applying these observations to Eq.\ \eqref{eq: GT corollary 1} gives
\begin{equation}
\label{eq: GT corollary 2}
| \widetilde{\mathcal{M}}_n^p | = \left( \frac{1}{np} \sum_{m \mid n, m \neq n} \varphi(n/m) \binom{pm}{m} \right) + \frac{1}{np} \varphi(p) \binom{n}{(n-1)/p} + \frac{1}{np} C_n^p.
\end{equation}
Noting that $\frac{1}{np} \varphi(p) \binom{n}{(n-1)/p} = \frac{p-1}{np} \binom{n}{(n-1)/p} = \frac{n(p-1)}{np} C_{(n-1)/p}^p$, and forcing the $n=m$ case into the summation as $\varphi(1)\binom{pn}{n} = ((p-1)n+1) C^p_n$, we have the (easily simplified) expression
\begin{equation}
\label{eq: GT corollary 3}
| \widetilde{\mathcal{M}}_n^p | = \left( \frac{1}{np} \sum_{m \mid n} \varphi(n/m) \binom{pm}{m} \right) - \frac{(p-1)n+1}{np} C_n^p + \frac{n(p-1)}{np} C_{(n-1)/p}^p + \frac{1}{np} C_n^p.
\end{equation}
\end{proof}
\section{Acknowledgments}
The authors would like to thank the Department of Mathematics \& Statistics at Valparaiso University, whose MATH 492 Undergraduate Research in Mathematics course provided the setting under which the research leading to Section \ref{sec: set-valued tableaux} of this paper took place.
\appendix
\section{On rational non-crossing matchings}
\label{app: comparison to rational non-crossing matchings}
As noted in Subsection \ref{subsec: jdq=rotation general case}, Proposition \ref{thm: non-crossing matchings vs. set-valued tableaux} provides a new combinatorial interpretation for the rational Catalan number $C(a,b)$ as the number non-crossing matchings of type $\vec{b}_{(a,b)} = (\lceil \frac{b}{a} \rceil - \lceil 0 \rceil + 1, \ldots, \lceil \frac{ab}{a} \rceil - \lceil \frac{(a-1)b}{a} \rceil + 1)$. Already appearing in the work of Armstrong, Rhoades, and Williams \cite{ARW} is a distinct combinatorial interpretation of $C(a,b)$ via a class of non-crossing matchings referred to as homogeneous $(a,b)$-noncrossing partitions. We use this appendix to thoroughly emphasize the differences between these two interpretations.
For relatively prime positive integers $a$ and $b$, an $(a,b)$-Dyck path is an integer lattice path from $(0,0)$ to $(b,a)$ that stays weakly below the line $y = \frac{a}{b}x$. It was originally shown by Bizley \cite{Bizley} that the number of such $(a,b)$-Dyck paths is enumerated by $C(a,b)$. Beginning with an $(a,b)$-Dyck path, Armstrong, Rhoades, and Williams use a ``laser construction" to divide the path's non-terminal lattice points into blocks that partition $a+b-1$. Lines of slope $\frac{a}{b}$ are drawn southwest from the top of each north step, and all lattice points within each resulting region (with the exception of the point at the top of each laser) are associated with one block.\footnote{Armstrong, Rhoades, and Williams \cite{ARW} work with the equivalent set of paths that lie above $y=\frac{a}{b}x$. This means that their original presentation involves sending lasers northeast from the bottom of each north step.} Note that, even for fixed $(a,b)$, the blocks in their resulting partitions needn't be consistently sized. For example, homogeneous $(5,8)$-noncrossing partitions include elements with block structure $\lbrace 4,2,2,2,2 \rbrace$ and $\lbrace 3,3,2,2,2 \rbrace$ (see Figure 7 of \cite{ARW}).
Alternatively, our matchings of type $\vec{b}_{(a,b)}$ represent partitions of $a+b$ and feature blocks whose sizes and ordering are fixed by one's choice of $(a,b)$. For example, all of our non-crossing matchings of weight $\vec{b}_{(5,8)}$ feature a block structure of $\lbrace 3,3,2,3,2 \rbrace$, with those blocks appearing in the stated order when sequenced from left-to-right via their rightmost elements.
Although we omit a formal proof here, one could construct our non-crossing matchings of weight $\vec{b}_{(a,b)}$ by passing from the associated set-valued tableau to the corresponding lattice path and then applying a modified version of the laser construction. This modified laser construction uses the same lasers, but then identifies the origin point of each laser with the block that lies under that laser. This convention is consistent with the fact that our partitions involve the final point of the $(a,b)$-Dyck path while the partitions of Armstrong, Rhoades, and Williams do not. See Figure \ref{fig: rational Catalan matching comparison} for a comparison of these two approaches.
\begin{figure}[ht!]
\begin{subfigure}[b]{0.56\textwidth}
\centering
\scalebox{.88}{
\raisebox{44pt}{\begin{tabular}{|c|c|c|c|c|}
\hline
1 \kern+1pt 2 & 3 \kern+1pt 4 & 6 & 7 \kern+1pt 9 & 10 \\ \hline
5 & 8 & 11 & 12 & 13 \\ \hline
\end{tabular}}}
\hspace{.1in}
\raisebox{31pt}{\scalebox{3}{$\Leftrightarrow$}}
\hspace{.05in}
\begin{tikzpicture}
[scale=.43,auto=left,every node/.style={circle, fill=black,inner sep=1.2pt}]
\draw[dotted] (0,0) to (8,0);
\draw[dotted] (0,1) to (8,1);
\draw[dotted] (0,2) to (8,2);
\draw[dotted] (0,3) to (8,3);
\draw[dotted] (0,4) to (8,4);
\draw[dotted] (0,5) to (8,5);
\draw[dotted] (0,0) to (0,5);
\draw[dotted] (1,0) to (1,5);
\draw[dotted] (2,0) to (2,5);
\draw[dotted] (3,0) to (3,5);
\draw[dotted] (4,0) to (4,5);
\draw[dotted] (5,0) to (5,5);
\draw[dotted] (6,0) to (6,5);
\draw[dotted] (7,0) to (7,5);
\draw[dotted] (8,0) to (8,5);
\draw (0,0) to (8,5);
\draw[red] (4,1) to (2.4,0);
\draw[red] (6,2) to (4.4,1);
\draw[red] (8,3) to (6.4,2);
\draw[red] (8,4) to (1.6,0);
\node (0*) at (0,0) {};
\node (1*) at (1,0) {};
\node (2*) at (2,0) {};
\node (3*) at (3,0) {};
\node (4*) at (4,0) {};
\node (5*) at (4,1) {};
\node (6*) at (5,1) {};
\node (7*) at (6,1) {};
\node (8*) at (6,2) {};
\node (9*) at (7,2) {};
\node (10*) at (8,2) {};
\node (11*) at (8,3) {};
\node (12*) at (8,4) {};
\node (13*) at (8,5) {};
\draw[thick] (0*) to (1*);
\draw[thick] (1*) to (2*);
\draw[thick] (2*) to (3*);
\draw[thick] (3*) to (4*);
\draw[thick] (4*) to (5*);
\draw[thick] (5*) to (6*);
\draw[thick] (6*) to (7*);
\draw[thick] (7*) to (8*);
\draw[thick] (8*) to (9*);
\draw[thick] (9*) to (10*);
\draw[thick] (10*) to (11*);
\draw[thick] (11*) to (12*);
\draw[thick] (12*) to (13*);
\node[fill=none] (1l) at (1,-.5) {\scalebox{.7}{1}};
\node[fill=none] (2l) at (2,-.5) {\scalebox{.7}{2}};
\node[fill=none] (3l) at (3,-.5) {\scalebox{.7}{3}};
\node[fill=none] (4l) at (4,-.5) {\scalebox{.7}{4}};
\node[fill=none] (5l) at (4.3,.6) {\scalebox{.7}{5}};
\node[fill=none] (6l) at (5.3,.6) {\scalebox{.7}{6}};
\node[fill=none] (7l) at (6.3,.6) {\scalebox{.7}{7}};
\node[fill=none] (8l) at (6.3,1.6) {\scalebox{.7}{8}};
\node[fill=none] (9l) at (7.3,1.6) {\scalebox{.7}{9}};
\node[fill=none] (10l) at (8.4,1.6) {\scalebox{.7}{10}};
\node[fill=none] (11l) at (8.4,2.6) {\scalebox{.7}{11}};
\node[fill=none] (12l) at (8.4,3.6) {\scalebox{.7}{12}};
\node[fill=none] (13l) at (8.4,4.6) {\scalebox{.7}{13}};
\end{tikzpicture}
\end{subfigure}
\begin{subfigure}[b]{0.08\textwidth}
\centering
\raisebox{8pt}{
\scalebox{2}{$\nearrow$}}
\vspace{.3in}
\raisebox{8pt}{
\scalebox{2}{$\searrow$}}
\end{subfigure}
\begin{subfigure}[b]{0.34\textwidth}
\centering
\raisebox{-18pt}{
\scalebox{.84}{
\begin{tikzpicture}
[scale=.5,auto=left,every node/.style={circle,fill=black,inner sep=1.3pt,outer sep=0pt}]
\node[inner sep=0pt] (left) at (.5,0) {};
\node (1) at (1,0) {};
\node (2) at (2,0) {};
\node (3) at (3,0) {};
\node (4) at (4,0) {};
\node (5) at (5,0) {};
\node (6) at (6,0) {};
\node (7) at (7,0) {};
\node (8) at (8,0) {};
\node (9) at (9,0) {};
\node (10) at (10,0) {};
\node (11) at (11,0) {};
\node (11) at (11,0) {};
\node (12) at (12,0) {};
\node (13) at (13,0) {};
\node[inner sep=0pt] (right) at (13.5,0) {};
\draw (left) to (right);
\node[inner sep=0pt] (a) at (4,.9) {};
\node[inner sep=0pt] (b) at (7,.9) {};
\node[inner sep=0pt] (c) at (9,1.6) {};
\draw[thick] (11,0) arc (0:180:.5);
\draw[thick,bend left=20] (3) to (a);
\draw[thick] (4) to (a);
\draw[thick,bend right=20] (5) to (a);
\draw[thick,bend left=20] (6) to (b);
\draw[thick] (7) to (b);
\draw[thick,bend right=20] (8) to (b);
\draw[thick,bend left=25] (2) to (c);
\draw[thick] (9) to (c);
\draw[thick,bend right=15] (12) to (c);
\draw[thick,bend right=43] (13) to (1);
\node[fill=none] (1l) at (1,-.5) {1};
\node[fill=none] (2l) at (2,-.5) {2};
\node[fill=none] (3l) at (3,-.5) {3};
\node[fill=none] (4l) at (4,-.5) {4};
\node[fill=none] (5l) at (5,-.5) {5};
\node[fill=none] (6l) at (6,-.5) {6};
\node[fill=none] (7l) at (7,-.5) {7};
\node[fill=none] (8l) at (8,-.5) {8};
\node[fill=none] (9l) at (9,-.5) {9};
\node[fill=none] (10l) at (10,-.5) {10};
\node[fill=none] (11l) at (11,-.5) {11};
\node[fill=none] (12l) at (12,-.5) {12};
\node[fill=none] (13l) at (13,-.5) {13};
\end{tikzpicture}}}
\vspace{.2in}
\raisebox{-18pt}{
\scalebox{.84}{
\begin{tikzpicture}
[scale=.5,auto=left,every node/.style={circle,fill=black,inner sep=1.3pt,outer sep=0pt}]
\node[inner sep=0pt] (left) at (.5,0) {};
\node (1) at (1,0) {};
\node (2) at (2,0) {};
\node (3) at (3,0) {};
\node (4) at (4,0) {};
\node (5) at (5,0) {};
\node (6) at (6,0) {};
\node (7) at (7,0) {};
\node (8) at (8,0) {};
\node (9) at (9,0) {};
\node (10) at (10,0) {};
\node (11) at (11,0) {};
\node (11) at (11,0) {};
\node (12) at (12,0) {};
\node[inner sep=0pt] (right) at (12.5,0) {};
\draw (left) to (right);
\node[inner sep=0pt] (a) at (6.5,1.5) {};
\draw[thick] (4,0) arc (0:180:.5);
\draw[thick] (7,0) arc (0:180:.5);
\draw[thick] (10,0) arc (0:180:.5);
\draw[thick,bend left=20] (2) to (a);
\draw[thick,bend left=20] (5) to (a);
\draw[thick,bend right=20] (8) to (a);
\draw[thick,bend right=20] (11) to (a);
\draw[thick,bend right=42] (12) to (1);
\node[fill=none] (1l) at (1,-.5) {1};
\node[fill=none] (2l) at (2,-.5) {2};
\node[fill=none] (3l) at (3,-.5) {3};
\node[fill=none] (4l) at (4,-.5) {4};
\node[fill=none] (5l) at (5,-.5) {5};
\node[fill=none] (6l) at (6,-.5) {6};
\node[fill=none] (7l) at (7,-.5) {7};
\node[fill=none] (8l) at (8,-.5) {8};
\node[fill=none] (9l) at (9,-.5) {9};
\node[fill=none] (10l) at (10,-.5) {10};
\node[fill=none] (11l) at (11,-.5) {11};
\node[fill=none] (12l) at (12,-.5) {12};
\end{tikzpicture}}}
\end{subfigure}
\caption{A standard set-valued Young tableaux of density $\vec{b}_{(5,8)}$, the corresponding $(5,8)$-Dyck path (with lasers in red), and a comparison of the matchings that result from our methodology (TOP) and the methods of Armstrong, Rhoades, and Williams (BOTTOM).}
\label{fig: rational Catalan matching comparison}
\end{figure}
For the context of this paper, our technique is preferable because there does not appear to be a straightforward way to directly associate a homogeneous $(a,b)$-noncrossing partition with a set-valued tableau (at least not without passing through a partition's associated $(a,b)$-Dyck path). This fact makes it difficult to consistently define a notion of jeu de taquin on set-valued tableaux in a way that corresponds to rotation on $(a,b)$-noncrossing partitions.
\begin{thebibliography}{10}
\bibitem{ARW}
D. Armstrong, B. Rhoades, and N. Williams, Rational associahedra and noncrossing partitions, \emph{Electron. J. Combin.} \textbf{20} (3) (2013), \#P54.
\bibitem{Bizley}
M. T. L. Bizley, Derivation of a new formula for the number of minimal
lattice paths from $(0,0)$ to $(km,kn)$ having just $t$ contacts with
the line $my=nx$ and having no points above this line; and a proof of
Grossman's formula for the number of paths which may touch but do not
rise above this line, \emph{J. for the Institute of Actuaries}
\textbf{80} (1954), 55--62.
\bibitem{BR}
M. Bodnar and B. Rhoades, Cyclic sieving and rational Catalan theory,
\emph{Electron. J. Combin.} \textbf{23} (2) (2016), Paper \#P2.4.
\bibitem{BBLL}
M. B\'ona, M. Bousquet, G. Labelle, and P. Leroux, Enumeration of $m$-ary cacti, \emph{Adv. in Appl. Math.} \textbf{24} (2000), 22--56.
\bibitem{Buch}
A. S. Buch, A Littlewood-Richardson rule for the $K$-theory of Grassmannians, \emph{Acta Math.} \textbf{189} (2002), 37--78.
\bibitem{Drube}
P. Drube, Set-valued tableaux \& generalized Catalan numbers, \textit{Australas. J. Combin.} \textbf{72} (2018), to appear.
\bibitem{Fulton}
W. Fulton, \emph{Young Tableaux, with Application to Representation Theory and Geometry}, Cambridge University Press, 1996.
\bibitem{GT}
R. W. Goldbach and R. Tijdeman, Pairings of $2n$ points on a circle, \emph{Utilitas Math.} \textbf{38} (1990), 277--284.
\bibitem{HLM}
S. Heubach, N. Y. Li, and T. Mansour, Staircase tilings and $k$-Catalan structures, \emph{Discrete Math.} \textbf{308} (2008), 5954--5964.
\bibitem{Pechenik1}
O. Pechenik, Cyclic sieving of increasing tableaux and small Schr\"oder paths, \emph{J. Comb. Theory, Ser. A}, \textbf{125} (2014), 357--378.
\bibitem{Pechenik2}
O. Pechenik, Promotion of increasing tableaux: frames and homomesies,
\emph{Electron. J. Combin.} \textbf{24} (3) (2017), \#P3.50.
\bibitem{PPR}
T. K. Petersen, P. Pylyavskyy, and B. Rhoades, Promotion and cyclic sieving via webs, \emph{J. Algebraic Combin.}, \textbf{30} (2009), 19--41.
\bibitem{RSW}
V. Reiner, D. Stanton, and D. White, The cyclic sieving phenomenon, \emph{J. Comb. Theory, Ser. A}, \textbf{108} (2004), 17--50.
\bibitem{Rhoades}
B. Rhoades, Cyclic sieving, promotion, and representation theory,
\emph{J. Combin. Theory Ser. A}, \textbf{117} (2010), 38--76.
\bibitem{Schutzenberger}
M. P. Sch\"utzenberger, Promotion des morphismes d'ensembles
ordonn\'es, \emph{Discrete Math.} \textbf{2}, (1972), 73--94.
\bibitem{Shimozono}
M. Shimozono, A cyclage poset structure for Littlewood-Richardson tableaux, \emph{European J. Combin.}, \textbf{22} (2001), 365--393.
\bibitem{Stanley2} R. P. Stanley, \emph{Enumerative Combinatorics},
Vol.~2, Cambridge University Press, 1999.
\bibitem{StanleyC} R. P. Stanley, \emph{Catalan Numbers}, Cambridge University Press, 2015.
\bibitem{Stembridge}
J. R. Stembridge, Canonical bases and self-evacuating tableaux, \emph{Duke Math. J.}, \textbf{82} (1996), 585--606.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05A19; Secondary 05C30.
\noindent \emph{Keywords: }
Young tableau, set-valued Young tableau, non-crossing matching, Catalan number, $k$-Catalan number, cyclic sieving.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A002995},
\seqnum{A054362},
\seqnum{A054365},
\seqnum{A054368}, and
\seqnum{A054423}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received October 23 2017;
revised versions received May 23 2018; May 24 2018.
Published in {\it Journal of Integer Sequences}, May 25 2018.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}
**