\documentclass[12pt]{article} \usepackage{e-jc} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \usepackage{tikz, amsmath,longtable,amsthm} \usetikzlibrary{decorations.markings} \usepackage[numbers,square,sort&compress]{natbib} % Front matter \title{Crossings and Nestings for Arc-Coloured Permutations and Automation} \author{Lily Yen\\ \small \begin{tabular}[t]{l} Dept.\ of Math.\ \& Stats.\\ Capilano University\\ North Vancouver, B.C.\\ Canada \end{tabular} \emph{and} \begin{tabular}[t]{l} Dept.\ of Math.\\ Simon Fraser University\\ Burnaby, B.C.\\ Canada \end{tabular}\\ \small\texttt{lyen@capilanou.ca} } \date{\dateline{submission date}{acceptance date}\\ \small Mathematics Subject Classifications: 05A19} %------------------------------------------------- % Theorems and propositions \newtheorem{definition}{Definition} \newtheorem{theorem}{Theorem} \newtheorem{corollary}{Corollary} \newtheorem{example}{Example} \newtheorem{conjecture}{Conjecture} %------------------------------------------------- % Other setup \newcommand{\cross}{\operatorname{cr}} \newcommand{\nest}{\operatorname{ne}} \newcommand{\NCN}{\operatorname{NCN}} \newcommand{\NN}{\operatorname{NN}} \newcommand{\NC}{\operatorname{NC}} \newcommand{\arc}{\operatorname{Arc}} \newcommand{\figurefontsize}{\small} \newcommand{\tableaufontsize}{\relax} \providecommand{\texorpdfstring}[2]{#1} \tikzstyle{pnt}=[circle,fill,inner sep=1.5pt] \tikzstyle{state}=[draw, circle,inner sep=1pt,minimum size=6mm] \tikzstyle{uni}=[decoration={markings,% mark=at position 0.3 with {\arrow[line width=1pt]{>};}},% postaction={decorate}] \tikzstyle{unir}=[decoration={markings,% mark=at position 0.3 with {\arrowreversed[line width=1pt]{>};}},% postaction={decorate}] \tikzstyle{loop above right}=[above right,out=60,in=30,loop] \tikzstyle{loop above left}=[above left,out=150,in=120,loop] \tikzstyle{loop below left}=[below right,out=240,in=210,loop] \tikzstyle{loop below right}=[below right,out=330,in=300,loop] \newcommand{\vOne}[2]{% \begin{tikzpicture} \draw (0,0) to[bend left] +(0.4,0.2) node[right, inner sep=1pt]{\small$#1$}; \draw (0,0) to[bend right] +(0.4,-0.2) node[right, inner sep=1pt]{\small$#2$}; \draw (0,0) node[pnt]{}; \end{tikzpicture}% } \begin{document} \maketitle \begin{abstract} Symmetric joint distribution between crossings and nestings was established in several combinatorial objects. Recently, Marberg extended Chen and Guo's result on coloured matchings to coloured set partitions following a multi-dimensional generalization of the bijection and enumerative methods from Chen, Deng, Du, Stanley, and Yan. We complete the study for arc-coloured permutations by establishing symmetric joint distribution for crossings and nestings and by showing that the ordinary generating functions for $j$-noncrossing, $k$-nonnesting, $r$-coloured permutations according to size $n$ are rational functions. Finally, we automate the generation of these rational functions and analyse the first $70$ series. \paragraph{Keywords} arc-coloured permutation, crossing, nesting, bijection, enumeration, tableau, generating tree, finite state automaton, transfer matrix, automation. \end{abstract} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Crossing and nesting statistics have intrigued combinatorialists for many decades. For example, it is well known that Catalan numbers, \( c_n = \frac{1}{n+1} \binom{2n}{n} \), count the number of noncrossing matchings on $[2n]$ which is also the number of nonnesting matchings of the same size. The concept of crossing and nesting was then extended to higher numbers where symmetric joint distribution continues to hold not only for matchings~\citep{GB89}, but also for set partitions~\citep{Chetal07, Kratt06}, labelled graphs~\citep{deMi07}, set partitions of classical types~\citep{RuSt10}, permutations~\citep{BuMiPo10}, and type B permutations~\citep{Ham11}. In all cases, bijective proofs were given; and for some, generating functions were found. Inspired by recent works of \citet{ChG11} on coloured matchings and \citet{Mar12} on coloured set partitions, we combine two theorems of~\citep{Mar12} to establish symmetric joint distribution of crossing and nesting statistics for \emph{arc-coloured permutations}. We also show that the ordinary generating functions for $j$-noncrossing, $k$-nonnesting, $r$-coloured permutations according to size $n$ are rational functions, and automate the generation of these rational functions. The study of over seventy initial rational functions yields very interesting information on patterns of singularities and degrees of numerator and denominator polynomials. Furthermore, the difference in complexity of rational series also sheds some light on the dichotomy of their limiting functions: D-finite or non-D-finite. In addition to being in bijection with type B (or signed) permutations, $2$-coloured permutations provide a compact representation of genome arrangements tracking orientation of each segment. In general, $r$-coloured permutations may be a natural model for the study of genome rearrangement problems, in particular, for tracking different types of distance metrics~\citep{Fertin09}. With automated generation of their rational series according to crossing and nesting statistics, random generation algorithms like Boltzmann sampling~\citep{DFLS04} can be applied for the investigation of the distribution of such structures modelled by coloured permutations. \subsection{Definitions and terminology} A permutation $S$ of the set $[n]:=\{ 1, 2, \dots, n\}$ is a bijection from $[n]$ to itself, $\sigma: [n] \rightarrow [n]$. Using a two-line notation, we can write \( S= \left(\begin{smallmatrix} 1 & 2 & 3 & \dots & n \\ \sigma(1) &\sigma(2) & \sigma(3) & \dots &\sigma(n) \end{smallmatrix} \right) \). An \emph{arc annotated diagram} is a labelled graph on $n$ vertices increasingly labelled horizontally such that $\arc(i,j)$ joins vertex $i$ to vertex $j$. A permutation can be represented as an arc annotated diagram where $\arc(i, \sigma(i))$ is drawn as an upper arc for $\sigma(i) \ge i$, and a lower arc for $\sigma(i) < i$. Note that the dissymmetry draws a fixed point in $S$ as an upper loop. When this diagram is restricted to only the upper arcs (or lower arcs) with all $n$ vertices, then it also represents a set partition of $[n]$. Separately, we call these\emph{ upper} and \emph{ lower arc diagrams} of a permutation. From such a diagram, we define a \emph{$k$-crossing} (resp.\ \emph{$k$-nesting}) as $k$ arcs \( \{(i_1, j_1), (i_2, j_2), \dots, (i_k, j_k)\} \) all mutually cross, or \( i_1 < i_2 < \dots < i_k < j_1 < j_2 < \dots < j_k \) (resp.\ nest, i.\,e.\ \( i_1 < i_2 < \dots < i_k < j_k < j_{k-1}< \dots < j_1 \) ) as shown in Figure~\ref{fig:kcrossing} (resp.\ Figure~\ref{fig:knesting}). We also need a variant: \emph{enhanced $k$-crossing} (resp.\ \emph{enhanced $k$-nesting}) where \( i_1 < i_2 < \dots < i_k \le j_1 < j_2 < \dots < j_k \) (resp.\ \( i_1 < i_2 < \dots < i_k \le j_k < j_{k-1}< \dots < j_1 \) ) as shown in Figure~\ref{fig:kenhancedcr} (resp.\ Figure~\ref{fig:kenhancedne}). \begin{figure}\centering \begin{minipage}[b]{0.45\linewidth} \figurefontsize\centering \begin{tikzpicture}[bend left=35,scale=0.8] \node[pnt,label=below:$i_1$] at (1,0) {}; \node[pnt,label=below:$i_2$] at (2,0) {}; \node[label=below:$\dots$] at (3,0) {}; \node[pnt,label=below:$i_k$] at (4,0) {}; \node[pnt,label=below:$j_1$] at (5,0) {}; \node[pnt,label=below:$j_2$] at (6,0) {}; \node[label=below:$\dots$] at (7,0) {}; \node[pnt,label=below:$j_k$] at (8,0) {}; \draw (1,0) to (5,0); \draw (2,0) to (6,0); \draw (3,0) to (7,0); \draw (4,0) to (8,0); \end{tikzpicture} \caption{A $k$-crossing} \label{fig:kcrossing} \end{minipage} \quad \begin{minipage}[b]{0.45\linewidth} \figurefontsize\centering \begin{tikzpicture}[bend left=30,scale=0.8] \node[pnt,label=below:$i_1$] at (1,0) {}; \node[pnt,label=below:$i_2$] at (2,0) {}; \node[label=below:$\dots$] at (3,0) {}; \node[pnt,label=below:$i_k$] at (4,0) {}; \node[pnt,label=below:$j_k$] at (5,0) {}; \node[label=below:$\dots$] at (6,0) {}; \node[pnt,label=below:$j_2$] at (7,0) {}; \node[pnt,label=below:$j_1$] at (8,0) {}; \draw (1,0) to (8,0); \draw (2,0) to (7,0); \draw (3,0) to (6,0); \draw (4,0) to (5,0); \end{tikzpicture} \caption{A $k$-nesting} \label{fig:knesting} \end{minipage} \end{figure} \begin{figure} \centering \begin{minipage}[b]{0.45\linewidth} \figurefontsize\centering \begin{tikzpicture}[bend left=35] \node[pnt,label=below:$i_1$] at (1,0) {}; \node[pnt,label=below:$i_2$] at (2,0) {}; \node[label=below:$\dots$] at (3,0) {}; \node[pnt,label={below:$i_k=j_1$}] at (4,0) {}; \node[pnt,label=below:$j_2$] at (5,0) {}; \node[label=below:$\dots$] at (6,0) {}; \node[pnt,label=below:$j_k$] at (7,0) {}; \draw (1,0) to (4,0); \draw (2,0) to (5,0); \draw (3,0) to (6,0); \draw (4,0) to (7,0); \end{tikzpicture} \caption{An \emph{enhanced} $k$-crossing} \label{fig:kenhancedcr} \end{minipage} \quad \begin{minipage}[b]{0.45\linewidth} \figurefontsize\centering \begin{tikzpicture}[bend left=30] \node[pnt,label=below:$i_1$] at (1,0) {}; \node[pnt,label=below:$i_2$] at (2,0) {}; \node[label=below:$\dots$] at (3,0) {}; \node[pnt,label={below:$i_k=j_k$}] at (4,0) {}; \node[label=below:$\dots$] at (5,0) {}; \node[pnt,label=below:$j_2$] at (6,0) {}; \node[pnt,label=below:$j_1$] at (7,0) {}; \draw (1,0) to (7,0); \draw (2,0) to (6,0); \draw[bend left=45] (3,0) to (5,0); \draw[loop right] (4,0) to (); \end{tikzpicture} \caption{An \emph{enhanced} $k$-nesting} \label{fig:kenhancedne} \end{minipage} \end{figure} We need both notions of crossings and nestings for permutations because the \emph{enhanced} definitions are used for upper arc diagrams whereas the other definitions (without \emph{enhanced}), for lower arc diagrams. This is in accordance with the literature~\citep{Corteel07} on permutation statistics for weak exceedances and pattern avoidance. We define the \emph{crossing number}, $\cross(S) = j$ (resp.\ \emph{nesting number}, $\nest(S) = k$) of a permutation $S$ as the maximum $j$ (resp.\ $k$) such that $S$ has a $j$-enhanced crossing (resp.\ $k$-enhanced nesting) in the upper arc diagram or a $j$-crossing (resp.\ $k$-nesting) in the lower arc diagram. When a permutation $S$ does not have a $j$-(enhanced)-crossing (resp.\ $k$-(enhanced)-nesting), then we say $S$ is $j$-noncrossing (resp.\ $k$-nonnesting). \citet*{BuMiPo10} gave an involution mapping between the set of permutations of $[n]$ with $\cross(S)=j$ and $\nest(S)=k$ and those with $\cross(S)=k$ and $\nest(S)=j$, thus extending the result of symmetric joint distribution for matchings and set partitions of \citet*{Chetal07} and \citet{Kratt06} to permutations. Next, \citet{ChG11} generalized symmetric equidistribution of crossing and nesting statistics to \emph{coloured} complete matchings. Recently, \citet{Mar12} extended Chen et al's enumerative results on matchings to coloured set partitions proving that the ordinary generating functions of $j$-noncrossing, $k$-nonnesting, $r$-coloured partitions according to size $n$ are rational functions. We further extend symmetric joint distribution and rationality of generating functions to $r$-arc-coloured permutations, or $r$-coloured permutations in short. Some caution on terminology is in order here. Group properties of coloured permutations have been widely studied since the $1990$'s~\citep{Borodin99, Stump12}, but there the colours are assigned to \emph{vertices} instead of \emph{arcs}. \subsection{An extension to coloured permutations} Since crossing and nesting statistics involves arcs, we define an \emph{$r$-coloured permutation} parallel to~\citep{Mar12} as a pair, $(S, \phi)$ consisting of a permutation of $[n]$ and an arc-colour assigning map $\phi: \arc(S) \rightarrow [r]$, and use a capital Greek letter, $\Sigma$, to denote these objects. We say $\Sigma$ has a $k$-crossing (resp.\ $k$-nesting) if $k$ arcs of the \emph{same} colour cross (resp.\ nest). Throughout this paper, \emph{enhanced} statistics is applied to \emph{upper} arc diagrams while \emph{non-enhanced} for \emph{lower} arc diagrams of permutations. Define $\cross(\Sigma)$ (resp.\ $\nest(\Sigma)$) as the maximum integer $k$ such that $\Sigma$ has a $k$-crossing (resp.\ $k$-nesting). The bijection of~\citep{BuMiPo10} can be extended to establish symmetric joint distribution of the numbers $\cross(\Sigma)$ and $\nest(\Sigma)$ over $r$-coloured permutations preserving opener and closer sequences (equivalently, sets of minimal and maximal elements of each block when upper arc and lower arc diagrams are viewed separately as set partitions). More formally, vertices of a permutation are of five types, an opener ( \begin{tikzpicture} \draw[bend left] (1.2,0) node[pnt]{} to +(0.3,0.2); \draw[bend right] (1.2, 0) to (1.5, -0.2); \end{tikzpicture} ), a closer ( \begin{tikzpicture} \draw[bend right] (1.5,0) node[pnt]{} to (1.2, 0.2); \draw[bend left] (1.5, 0) to (1.2, -0.2); \end{tikzpicture} ), a fixed point ( \begin{tikzpicture} \draw[loop above] (0,0) node[pnt]{} to (0.0); \end{tikzpicture} ) , an upper transitory ( \begin{tikzpicture} \draw[bend left] (0,0) node[pnt]{} to +(0.3,0.2); \draw[bend right] (0,0) to (-0.3, 0.2); \end{tikzpicture} ), and a lower transitory( \begin{tikzpicture} \draw[bend right] (0,0) node[pnt]{} to (0.3,-0.2); \draw[bend left] (0,0) to (-0.3, -0.2); \end{tikzpicture}). For a particular permutation, $\Sigma$, restricting to only one colour, both upper arc and lower arc diagrams can be seen separately as set partitions whose minimal block elements are the openers ( \begin{tikzpicture} \draw[bend left] (1.2,0) node[pnt]{} to +(0.3,0.2); \end{tikzpicture} or \begin{tikzpicture} \draw[bend right] (1.2, 0) node[pnt]{} to (1.5, -0.2); \end{tikzpicture} ), and maximal block elements are the closers ( \begin{tikzpicture} \draw[bend right] (1.5,0) node[pnt]{} to (1.2, 0.2); \end{tikzpicture} or \begin{tikzpicture} \draw[bend left] (1.5, 0) node[pnt]{} to (1.2, -0.2); \end{tikzpicture} ). Let $\min(P)$ (resp.\ $\max(P)$) denote the set of minimum (resp.\ maximum) elements of the blocks of a set partition $P$. Chen et al.\ ~\citep{Chetal07} proved the following theorem for symmetric joint distribution of crossing and nesting statistics in set partitions. \begin{theorem}[Theorem 1.1 of \citep{Chetal07}] \label{thm:chetal07thm1.1} Fix a positive integer $n$ and subsets $S$, $T \subseteq [n]$. The statistics $\cross(P)$ and $\nest(P)$ have a symmetric joint distribution over all partitions $P$ of $[n]$ with $\min(P) = S$ and $\max(P) = T$. \end{theorem} For coloured set partitions, Marberg~\citep{Mar12} generalized Theorem 1.1 of~\citep{Chetal07} to maintain symmetric joint distribution for $r$-coloured set partitions. In Marberg's notation, for given positive integers $j$, $k$, and subsets $S$, $T \subseteq [n]$, we write $\NCN_{j,k}^{S,T}(n,r)$ for the number of $r$-coloured partitions $ \Lambda = (P, \phi)$ of $[n]$ with $\cross(\Lambda) < j$ and $\nest(\Lambda) < k$, and $\min(\Lambda) = S$, and $\max(\Lambda) = T$, where we define $\min(\Lambda):= \min(P)$ and $\max(\Lambda) := \max(P)$. Marberg proved the following. \begin{theorem}[Theorem 1.4 of \citep{Mar12}] \label{thm:mar12thm1.4} $\NCN_{j,k}^{S,T}(n,r) = \NCN_{k,j}^{S,T}(n,r)$ for all integers $j$, $k$ and subsets $S$, $T \subseteq [n]$. \end{theorem} Also from~\citep{Mar12} for \emph{enhanced} crossing and nesting numbers of $r$-coloured set partitions, using $\overline\Lambda = (P, \phi)$ to denote an $r$-coloured enhanced set partition, Marberg proved the following. \begin{theorem}[Theorem 5.7 of \citep{Mar12}] \label{thm:mar12thm5.7} Let $S$, $T \subseteq [n]$. The enhanced crossing and nesting numbers $\cross(\overline\Lambda)$ and $\nest(\overline\Lambda)$ have a symmetric joint distribution over all $r$-coloured enhanced partitions $\overline\Lambda$ of $[n]$ with $\min(\overline\Lambda) \setminus \max(\overline\Lambda) = S$ and $\max(\overline\Lambda) \setminus \min(\overline\Lambda) = T$. \end{theorem} Further extension of symmetric joint distribution to $r$-coloured permutations requires a similar set-up: Given an $r$-coloured permutation $\Sigma = (S, \phi)$, let the set of openers (resp.\ the set of closers) be $\mathcal{O}(\Sigma)$ (resp.\ $\mathcal{C}(\Sigma)$) of the uncoloured permutation, $S$. For all positive integers, $j$ and $k$, and subsets $O$, $C \subseteq [n]$, define \( \NCN_{j,k}^{O,C} (n,r) \) to be the number of $r$-coloured permutations $\Sigma$ of $[n]$ with $\cross(\Sigma) < j$, $\nest(\Sigma) < k$, $\mathcal{O}(\Sigma) = O$, and $\mathcal{C}(\Sigma) = C$. Then we reach an analogous result to Theorem 1.1 in~\citep{Chetal07, Mar12} for $r$-coloured permutations in the following Corollary. \begin{corollary} \label{cor:jointjk} For all positive integers, $j$ and $k$, and subsets $O$, $C \subseteq [n]$, \( \NCN_{j,k}^{O,C} (n,r) = \NCN_{k,j}^{O,C} (n,r) \). \end{corollary} \begin{proof} An $r$-coloured permutation $\Sigma = (S, \phi)$ can be viewed as an ordered pair $(\overline\Lambda, \Lambda)$ of an $r$-coloured enhanced partition $\overline\Lambda$ from the upper arc diagram of $\Sigma$ and an $r$-coloured set partition $\Lambda$ from the lower arc diagram of $\Sigma$. The sets $\mathcal{O}$ (resp.\ $\mathcal{C}$) $\subseteq [n]$ are precisely $\min(\overline\Lambda)$ and $\min(\Lambda)$ (resp.\ $\max(\overline\Lambda)$ and $\max(\Lambda)$). Thus Theorem~\ref{thm:mar12thm5.7} (Theorem 5.7 of~\citep{Mar12}) applies to $\overline\Lambda$, and similarly Theorem~\ref{thm:mar12thm1.4} (Theorem 1.4 of~\citep{Mar12}) applies to $\Lambda$. Therefore, symmetric joint distribution of nesting and crossing statistics with respect to each colour is preserved for coloured permutations. \end{proof} As in~\citet{Mar12}, we also let $\NCN_{j,k}(n,r)$ denote the number of all $r$-coloured, $j$-noncrossing, $k$-nonnesting permutations of $[n]$. Summing both sides of Corollary~\ref{cor:jointjk} over all $O$, $C \subseteq [n]$ gives the generalization of~\citep{Chetal07, Mar12} for Corollary~\ref{cor:NC}. We also let $\NC_k(n,r)$ (resp. $\NN_k(n,r)$) denote the number of $k$-noncrossing (resp. $k$-nonnesting) $r$-coloured permutations on $[n]$. \begin{corollary} \label{cor:NC} For all integers, $j, k, n, r$, \( \NCN_{j,k}(n,r) = \NCN_{k,j}(n,r) \) and $\NC_k(n,r) = \NN_k(n,r)$. \end{corollary} \subsection{Plan} The tools needed for the enumeration of $j$-noncrossing, $k$-nonnesting, $r$-coloured permutations are given in Section~\ref{sec:background}. Section~\ref{sec:pfMT} describes the encoding process translating an $r$-coloured permutation to a pair of $r$-tuple tableau sequence managing both notions of crossing and nesting for upper and lower arc diagrams. Section~\ref{sec:enum} first reviews Marberg's enumerative approach then provides a more direct interpretation for coloured set partitions. Section~\ref{sec:permenum} begins with the more direct interpretation for coloured permutations, then proves that the generating series of $j$-noncrossing, $k$-nonnesting, $r$-coloured permutations according to size $n$ is rational. Automating the generation of over seventy rational series leads to some conjectures. We end with an example which connects to permutations of type B. %%%%%%%%%%%%%%%%%%%%%%%% \section{Background} %%%%%%%%%%%%%%%%%%%%%%%%%% \label{sec:background} The translation of a set partition's arc annotated diagram to a tableau sequence as exhibited by Chen et al.\ in~\citep{Chetal07} forms the basis of our extension of symmetric joint distribution of crossing and nesting statistics for coloured permutations. The process of taking an $r$-coloured permutation and producing a pair of $r$-tuple sequence of tableaux leads to automation of the enumeration of such objects according to its crossing and nesting numbers. Understanding the process requires working knowledge of the theory of integer partition, especially its representation as Young diagrams, the Hasse diagram of the Young lattice, and the Robinson-Knuth-Schensted (RSK, in short)-algorithm for filling positive integers to obtain the beginning of some standard Young tableau. We refer the reader to Volume $2$ of Stanley's Enumerative Combinatorics~\citep{Stanley99} for more details. Define a partition of $n\in \mathbf{N}$ to be a sequence \( \lambda = (\lambda_1, \lambda_2, \dots, \lambda_k) \in \mathbf{N}^k \) such that \( \sum_{i=1}^k \lambda_i = n \), and \( \lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_k \). If $\lambda$ is a partition of $n$, we write $\lambda \vdash n$ or $| \lambda | = n$. The non-zero terms $\lambda_i$ are called the parts of $\lambda$, and we say $\lambda$ has $k$ parts if $\lambda_k > 0$. We can draw $\lambda$ using a left-justified array of boxes with $\lambda_i$ boxes in row $i$. For example, \( \lambda = (5, 3, 2, 2, 1) \) is drawn as \begin{tikzpicture}[scale=0.1] \draw (0,4) grid (5,5); \draw (0,3) grid (3,4); \draw (0,1) grid (2,3); \draw (0,0) grid (1,1); \end{tikzpicture}. This representation is the Young diagram of a partition. To ``add a box'' to a partition $\lambda$ means to obtain a partition $\mu$ such that $| \lambda| + 1 = | \mu|$, and $\lambda$'s Young diagram is included in that of $\mu$. This inclusion induces a partial order on the set of partitions of non-negative integers, denoted by $\mathbf{Y}$, or the Young lattice. When we place integers $1, 2, \dots, n$ in all $n$ boxes of a Young diagram so that entries increase in each row and column, we produce a standard Young tableau, abbreviated as SYT. As one builds an SYT from the empty set through the process of adding a box at a time, a sequence of integer partitions, \( ( \lambda^0 = \emptyset, \lambda^1, \lambda^2, \dots, \lambda^n) \) emerges where $\lambda^{i-1} \subset \lambda^i$, and $|\lambda^i| = |\lambda^{i-1}| + 1$. In addition to adding a box, we include ``deleting a box'' and ``doing nothing'' for the following two types in Definition~\ref{dfn:T} adopted from~\citep{Chetal07}. \begin{definition} \label{dfn:T} We define two types of sequences of tableaux, \( T = ( \lambda^0 = \emptyset, \lambda^1, \lambda^2, \dots, \lambda^n) \), where $\lambda^0 = \lambda^n = \emptyset$ such that $\lambda^i$ is obtained from $\lambda^{i-1}$ for each $i \in [n]$ by one of the three actions: adding a box, deleting a box, or doing nothing. \begin{enumerate} \item A \emph{hesitating tableau} is any such sequence $T$ which has $\lambda^{i-1} \subseteq \lambda^i$ when $i$ is odd, and $\lambda^{i-1} \supseteq \lambda^i$ when $i$ is even. \item A \emph{vacillating tableau} is any such sequence $T$ which has $\lambda^{i-1} \subseteq \lambda^i$ when $i$ is even, and $\lambda^{i-1} \supseteq \lambda^i$ when $i$ is odd. \end{enumerate} \end{definition} In the uncoloured case, \citet{Mar12} links the sequence $T$ to an $n$-step walk on the Hasse diagram of the Young lattice, $\mathbf{Y}$ where ``doing nothing'' is also counted as a step. For his enumeration purposes, Marberg's definitions differ slightly from~\citep{Chetal07} to achieve that these $n$-step walks are closed walks from $\emptyset$. Though we will not walk on an ordered pair of $r$-tuple Hasse diagrams, we will keep the requirement that each sequence $T$ begins and ends with $\emptyset$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Encoding process} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{sec:pfMT} Translating a coloured permutation to its pair of $r$-tuple sequence of tableaux requires treating the upper (resp.\ lower) arc diagram as an enhanced (resp.\ non-enhanced) coloured set partition. We then apply two local rules for \emph{inflating} the vertices while changing set partitions to involutions: Rule H for hesitating tableaux tracking \emph{enhanced} statistics in upper arcs and Rule V for vacillating tableaux for the lower arcs, one sequence for each colour. \begin{center} \begin{tabular}{lllll} & Opener& Closer& Transitory& Fixed point\\ Rule H& \begin{tikzpicture} \draw[bend left] (0,0) node[pnt]{} to +(0.3,0.2); \end{tikzpicture}% ${}\mapsto{}$% \begin{tikzpicture} \draw (1.5,0) node[pnt]{}; \draw[bend left] (1.3,0) node[pnt]{} to +(0.3,0.2); \end{tikzpicture} & \begin{tikzpicture} \draw[bend right] (0,0) node[pnt]{} to (-0.3,0.2); \end{tikzpicture}% ${}\mapsto{}$% \begin{tikzpicture} \draw (1.3,0) node[pnt]{}; \draw[bend right] (1.5,0) node[pnt]{} to (1.2,0.2); \end{tikzpicture} & \begin{tikzpicture} \draw[bend left] (0,0) node[pnt]{} to +(0.3,0.2); \draw[bend right] (0,0) to (-0.3, 0.2); \end{tikzpicture}% ${}\mapsto{}$% \begin{tikzpicture} \draw[bend right] (1.5,0) node[pnt]{} to (1.2, 0.2); \draw[bend left] (1.3,0) node[pnt]{} to +(0.3,0.2); \end{tikzpicture} & \begin{tikzpicture} \draw[loop above] (0,0) node[pnt]{} to (0,0); \end{tikzpicture}% ${}\mapsto{}$% \begin{tikzpicture} \draw[bend left = 80] (1,0) to (1.3, 0); \draw (1,0) node[pnt]{}; \draw (1.3, 0) node[pnt]{}; \end{tikzpicture} \\ Rule V& \begin{tikzpicture} \draw[bend left] (0,0) node[pnt]{} to +(0.3,0.2); \end{tikzpicture}% ${}\mapsto{}$% \begin{tikzpicture} \draw (1.3,0) node[pnt]{}; \draw[bend left] (1.5,0) node[pnt]{} to +(0.3,0.2); \end{tikzpicture} & \begin{tikzpicture} \draw[bend right] (0,0) node[pnt]{} to (-0.3,0.2); \end{tikzpicture}% ${}\mapsto{}$% \begin{tikzpicture} \draw (1.5,0) node[pnt]{}; \draw[bend right] (1.3,0) node[pnt]{} to (1,0.2); \end{tikzpicture} & \begin{tikzpicture} \draw[bend left] (0,0) node[pnt]{} to +(0.3,0.2); \draw[bend right] (0,0) to (-0.3, 0.2); \end{tikzpicture}% ${}\mapsto{}$% \begin{tikzpicture} \draw[bend right] (1.3,0) node[pnt]{} to (1, 0.2); \draw[bend left] (1.5,0) node[pnt]{} to +(0.3,0.2); \end{tikzpicture} & \begin{tikzpicture} \path[loop above] (0,0) node{} to (0,0); \draw (0,0) node[pnt]{}; \end{tikzpicture}% ${}\mapsto{}$% \begin{tikzpicture} \draw (1,0) node[pnt]{}; \draw (1.3,0) node[pnt]{}; \end{tikzpicture} \end{tabular} \end{center} Then we follow the steps below to construct an $r$-tuple of hesitating tableaux (resp.\ vacillating tableaux) for the upper (resp.\ lower) arc diagrams. \begin{itemize} \item[Step 1] For each colour $i$, $i \in [r]$, of the arc diagram of a given permutation on $[n]$, apply Rules H and V to inflate each vertex to obtain a sequence of $2n$ vertices. \item[Step 2] Begin each tableau sequence with an empty tableau, $\lambda^0_i = \emptyset$. \item[Step 3] Scanning each inflated vertex $k$, $k \in [2n]$, from left to right, \begin{enumerate} \item we add a box to the previous tableau $\lambda_i^{k-1}$ for an opener and label the box by the closer vertex label in the permutation's arc diagram according to RSK-algorithm; \item we do nothing to $\lambda_i^{k-1}$ to get $\lambda_i^k$ for a single vertex; \item and for a closer, we delete the box in $\lambda_i^{k-1}$ whose label is the corresponding closer label in the permutation's arc diagram, and then reverse RSK-algorithm to obtain $\lambda_i^k$. \end{enumerate} \end{itemize} This encoding process differs slightly from the one used in the bijection of Chen et al.\ ~\citep{Chetal07} for interchanging nesting and crossing numbers in set partitions. However, as proved in~\citep{Chetal07}, by RSK-algorithm, we know that each tableau sequence thus constructed has at most $j$ columns and $k$ rows if the permutation, $\Sigma$, has $\cross(\Sigma) = j$ and $\nest(\Sigma) = k$. \subsection{An example of a \texorpdfstring{$2$}{2}-coloured permutation} We show a $2$-coloured permutation and its tableau sequence encoding. \begin{example} \label{ex:perm} A permutation encoded by a \emph{hesitating tableau sequence}, $\lambda_1$ for colour $1$, $\lambda_2$ for colour $2$ in the \emph{upper} arcs and a \emph{vacillating tableau sequence}, $\mu_2$ for colour $2$ in the \emph{lower} arcs. \begin{center} \begin{tabular}{*{13}{c}} $\lambda_1^0$ & $\lambda_1^1$ & $\lambda_1^2$ & $\lambda_1^3$ & $\lambda_1^4$ & $\lambda_1^5$ & $\lambda_1^6$ & $\lambda_1^7$ & $\lambda_1^8$ & $\lambda_1^9$ & $\lambda_1^{10}$ & $\lambda_1^{11}$ & $\lambda_1^{12}$ \\ \begin{tikzpicture}[scale=0.4,baseline={(0,0.4)}] \node at (0.5,1.5) {$\emptyset$}; \end{tikzpicture} & \begin{tikzpicture}[scale=0.4,baseline={(0,0.4)}] \draw (0,1) grid (1,2); \node at (0.5,1.5) {\tableaufontsize$4$}; \end{tikzpicture} & \begin{tikzpicture}[scale=0.4,baseline={(0,0.4)}] \draw (0,1) grid (1,2); \node at (0.5,1.5) {\tableaufontsize$4$}; \end{tikzpicture} & \begin{tikzpicture}[scale=0.4,baseline={(0,0.4)}] \draw (0,1) grid (1,2); \node at (0.5,1.5) {\tableaufontsize$4$}; \end{tikzpicture} & \begin{tikzpicture}[scale=0.4,baseline={(0,0.4)}] \draw (0,1) grid (1,2); \node at (0.5,1.5) {\tableaufontsize$4$}; \end{tikzpicture} & \begin{tikzpicture}[scale=0.4,baseline={(0,0.4)}] \draw (0,0) grid (1,1); \draw (0,1) grid (1,2); \node at (0.5,1.5) {\tableaufontsize$3$}; \node at (0.5,0.5) {\tableaufontsize$4$}; \end{tikzpicture} & \begin{tikzpicture}[scale=0.4,baseline={(0,0.4)}] \draw (0,1) grid (1,2); \node at (0.5,1.5) {\tableaufontsize$4$}; \end{tikzpicture} & \begin{tikzpicture}[scale=0.4,baseline={(0,0.4)}] \draw (0,1) grid (1,2); \node at (0.5,1.5) {\tableaufontsize$4$}; \end{tikzpicture} & \begin{tikzpicture}[scale=0.4,baseline={(0,0.4)}] \node at (0.5,1.5) {$\emptyset$}; \end{tikzpicture} & \begin{tikzpicture}[scale=0.4,baseline={(0,0.4)}] \node at (0.5,1.5) {$\emptyset$}; \end{tikzpicture}& \begin{tikzpicture}[scale=0.4,baseline={(0,0.4)}] \node at (0.5,1.5) {$\emptyset$}; \end{tikzpicture}& \begin{tikzpicture}[scale=0.4,baseline={(0,0.4)}] \node at (0.5,1.5) {$\emptyset$}; \end{tikzpicture}& \begin{tikzpicture}[scale=0.4,baseline={(0,0.4)}] \node at (0.5,1.5) {$\emptyset$}; \end{tikzpicture} \\ Rule $H_1$ & \begin{tikzpicture} \draw[bend left] (1,0) node[pnt]{} to +(0.3,0.2); \end{tikzpicture} & \begin{tikzpicture} \draw (1.2,0) node[pnt]{}; \end{tikzpicture} & \begin{tikzpicture} \draw (1.2,0) node[pnt]{}; \end{tikzpicture} & \begin{tikzpicture} \draw (1.2,0) node[pnt]{}; \end{tikzpicture} & \begin{tikzpicture} \draw[bend left] (1,0) node[pnt]{} to +(0.3, 0.2); \end{tikzpicture} & \begin{tikzpicture} \draw[bend right] (1.5,0) node[pnt]{} to (1.2, 0.2); \end{tikzpicture} & \begin{tikzpicture} \draw (1.2,0) node[pnt]{}; \end{tikzpicture} & \begin{tikzpicture} \draw[bend right] (1.5,0) node[pnt]{} to (1.2, 0.2); \end{tikzpicture} & \begin{tikzpicture} \draw (1.2,0) node[pnt]{}; \end{tikzpicture} & \begin{tikzpicture} \draw (1.2,0) node[pnt]{}; \end{tikzpicture} & \begin{tikzpicture} \draw (1.2,0) node[pnt]{}; \end{tikzpicture} & \begin{tikzpicture} \draw (1.2,0) node[pnt]{}; \end{tikzpicture} \\[1ex] $\lambda_2^0$ & $\lambda_2^1$ & $\lambda_2^2$ & $\lambda_2^3$ & $\lambda_2^4$ & $\lambda_2^5$ & $\lambda_2^6$ & $\lambda_2^7$ & $\lambda_2^8$ & $\lambda_2^9$ & $\lambda_2^{10}$ & $\lambda_2^{11}$ & $\lambda_2^{12}$ \\ \begin{tikzpicture}[scale=0.4,baseline={(0,0.4)}] \node at (0.5,1.5) {$\emptyset$}; \end{tikzpicture} & \begin{tikzpicture}[scale=0.4,baseline={(0,0.4)}] \node at (0.5,1.5) {$\emptyset$}; \end{tikzpicture} & \begin{tikzpicture}[scale=0.4,baseline={(0,0.4)}] \node at (0.5,1.5) {$\emptyset$}; \end{tikzpicture} & \begin{tikzpicture}[scale=0.4,baseline={(0,0)}] \draw (0,0) grid (1,1); \node at (0.5,0.5) {\tableaufontsize$5$}; \end{tikzpicture} & \begin{tikzpicture}[scale=0.4,baseline={(0,0)}] \draw (0,0) grid (1,1); \node at (0.5,0.5) {\tableaufontsize$5$}; \end{tikzpicture} & \begin{tikzpicture}[scale=0.4,baseline={(0,0)}] \draw (0,0) grid (1,1); \node at (0.5,0.5) {\tableaufontsize$5$}; \end{tikzpicture} & \begin{tikzpicture}[scale=0.4,baseline={(0,0)}] \draw (0,0) grid (1,1); \node at (0.5,0.5) {\tableaufontsize$5$}; \end{tikzpicture} & \begin{tikzpicture}[scale=0.4,baseline={(0,0)}] \draw (0,0) grid (2,1); \node at (0.5,0.5) {\tableaufontsize$5$}; \node at (1.5, 0.5) {\tableaufontsize$6$}; \end{tikzpicture} & \begin{tikzpicture}[scale=0.4,baseline={(0,0)}] \draw (0,0) grid (2,1); \node at (0.5,0.5) {\tableaufontsize$5$}; \node at (1.5, 0.5) {\tableaufontsize$6$}; \end{tikzpicture} & \begin{tikzpicture}[scale=0.4,baseline={(0,0)}] \draw (0,0) grid (2,1); \node at (0.5,0.5) {\tableaufontsize$5$}; \node at (1.5, 0.5) {\tableaufontsize$6$}; \end{tikzpicture} & \begin{tikzpicture}[scale=0.4,baseline={(0,0.4)}] \draw (0,1) grid (1,2); \node at (0.5,1.5) {\tableaufontsize$6$}; \end{tikzpicture} & \begin{tikzpicture}[scale=0.4,baseline={(0,0.4)}] \draw (0,1) grid (1,2); \node at (0.5,1.5) {\tableaufontsize$6$}; \end{tikzpicture}& \begin{tikzpicture}[scale=0.4,baseline={(0,0.4)}] \node at (0.5,1.5) {$\emptyset$}; \end{tikzpicture} \\ Rule $H_2$ & \begin{tikzpicture} \draw (1.2,0) node[pnt]{}; \end{tikzpicture} & \begin{tikzpicture} \draw (1.2,0) node[pnt]{}; \end{tikzpicture} & \begin{tikzpicture} \draw[bend left] (1,0) node[pnt]{} to +(0.3,0.2); \end{tikzpicture} & \begin{tikzpicture} \draw (1.2,0) node[pnt]{}; \end{tikzpicture} & \begin{tikzpicture} \draw (1.2,0) node[pnt]{}; \end{tikzpicture} & \begin{tikzpicture} \draw (1.2,0) node[pnt]{}; \end{tikzpicture} & \begin{tikzpicture} \draw[bend left] (1,0) node[pnt]{} to +(0.3,0.2); \end{tikzpicture} & \begin{tikzpicture} \draw (1.2,0) node[pnt]{}; \end{tikzpicture} & \begin{tikzpicture} \draw (1.3,0) node[pnt]{}; \end{tikzpicture} & \begin{tikzpicture} \draw[bend right] (1.5,0) node[pnt]{} to (1.2,0.2); \end{tikzpicture} & \begin{tikzpicture} \draw (1.3,0) node[pnt]{}; \end{tikzpicture} & \begin{tikzpicture} \draw[bend right] (1.5,0) node[pnt]{} to (1.2,0.2); \end{tikzpicture} \end{tabular} \\ \begin{tikzpicture}[scale=1.5] \foreach \i in {1,...,6} \node[pnt,label=below:$\i$] at (\i,0)(\i) {}; \draw[bend left=45](1) to node[pos=0.2,above]{$\scriptstyle1$} (4); \draw[bend left=30](4) to node[pos=0.7, above]{$\scriptstyle2$} (6); \draw[bend left=45](2) to node[above]{$\scriptstyle2$} (5); \draw[loop above](3) to node[pos=0.1,right]{$\scriptstyle1$} (); \draw[bend right=30](2) to node[above]{$\scriptstyle2$} (5); \draw[bend right=30](1) to node[below]{$\scriptstyle2$} (6); \end{tikzpicture} \\ \begin{tabular}{*{13}{c}} Rule $V_2$ & \begin{tikzpicture}[baseline={(1,-0.2)}] \draw (1,0) node[pnt]{}; \end{tikzpicture} & \begin{tikzpicture}[baseline={(1,-0.2)}] \draw[bend right] (1,0) node[pnt]{} to (1.3,-0.2); \end{tikzpicture} & \begin{tikzpicture}[baseline={(1,-0.2)}] \draw (1,0) node[pnt]{}; \end{tikzpicture} & \begin{tikzpicture}[baseline={(1,-0.2)}] \draw[bend right] (1,0) node[pnt]{} to (1.3,-0.2); \end{tikzpicture} & \begin{tikzpicture}[baseline={(1,-0.2)}] \draw (1,0) node[pnt]{}; \end{tikzpicture} & \begin{tikzpicture}[baseline={(1,-0.2)}] \draw (1,0) node[pnt]{}; \end{tikzpicture} & \begin{tikzpicture}[baseline={(1,-0.2)}] \draw (1,0) node[pnt]{}; \end{tikzpicture} & \begin{tikzpicture}[baseline={(1,-0.2)}] \draw (1,0) node[pnt]{}; \end{tikzpicture} & \begin{tikzpicture}[baseline={(1,-0.2)}] \draw[bend left] (1.3,0) node[pnt]{} to (1,-0.2); \end{tikzpicture} & \begin{tikzpicture}[baseline={(1,-0.2)}] \draw (1.5,0) node[pnt]{}; \end{tikzpicture} & \begin{tikzpicture}[baseline={(1,-0.2)}] \draw[bend left] (1.3,0) node[pnt]{} to (1,-0.2); \end{tikzpicture} & \begin{tikzpicture}[baseline={(1,-0.2)}] \draw (1.5,0) node[pnt]{}; \end{tikzpicture} \\[1.5ex] $\mu_2^0$ & $\mu_2^1$ & $\mu_2^2$ & $\mu_2^3$ & $\mu_2^4$ & $\mu_2^5$ & $\mu_2^6$ & $\mu_2^7$ & $\mu_2^8$ & $\mu_2^9$ & $\mu_2^{10}$ & $\mu_2^{11}$ & $\mu_2^{12}$ \\ \begin{tikzpicture}[scale=0.4,baseline={(0,0.4)}] \node at (0.5,1.5) {$\emptyset$}; \end{tikzpicture} & \begin{tikzpicture}[scale=0.4,baseline={(0,0.4)}] \node at (0.5,1.5) {$\emptyset$}; \end{tikzpicture} & \begin{tikzpicture}[scale=0.4,baseline={(0,0.4)}] \draw (0,1) grid (1,2); \node at (0.5,1.5) {\tableaufontsize$6$}; \end{tikzpicture} & \begin{tikzpicture}[scale=0.4,baseline={(0,0.4)}] \draw (0,1) grid (1,2); \node at (0.5,1.5) {\tableaufontsize$6$}; \end{tikzpicture} & \begin{tikzpicture}[scale=0.4,baseline={(0,0.4)}] \draw (0,0) grid (1,2); \node at (0.5,1.5) {\tableaufontsize$5$}; \node at (0.5,0.5) {\tableaufontsize$6$}; \end{tikzpicture} & \begin{tikzpicture}[scale=0.4,baseline={(0,0.4)}] \draw (0,0) grid (1,2); \node at (0.5,1.5) {\tableaufontsize$5$}; \node at (0.5,0.5) {\tableaufontsize$6$}; \end{tikzpicture} & \begin{tikzpicture}[scale=0.4,baseline={(0,0.4)}] \draw (0,0) grid (1,2); \node at (0.5,1.5) {\tableaufontsize$5$}; \node at (0.5,0.5) {\tableaufontsize$6$}; \end{tikzpicture} & \begin{tikzpicture}[scale=0.4,baseline={(0,0.4)}] \draw (0,0) grid (1,2); \node at (0.5,1.5) {\tableaufontsize$5$}; \node at (0.5,0.5) {\tableaufontsize$6$}; \end{tikzpicture} & \begin{tikzpicture}[scale=0.4,baseline={(0,0.4)}] \draw (0,0) grid (1,2); \node at (0.5,1.5) {\tableaufontsize$5$}; \node at (0.5,0.5) {\tableaufontsize$6$}; \end{tikzpicture} & \begin{tikzpicture}[scale=0.4,baseline={(0,0.4)}] \draw (0,1) grid (1,2); \node at (0.5,1.5) {\tableaufontsize$6$}; \end{tikzpicture} & \begin{tikzpicture}[scale=0.4,baseline={(0,0.4)}] \draw (0,1) grid (1,2); \node at (0.5,1.5) {\tableaufontsize$6$}; \end{tikzpicture} & \begin{tikzpicture}[scale=0.4,baseline={(0,0.4)}] \node at (0.5,1.5) {$\emptyset$}; \end{tikzpicture} & \begin{tikzpicture}[scale=0.4,baseline={(0,0.4)}] \node at (0.5,1.5) {$\emptyset$}; \end{tikzpicture} \end{tabular} \end{center} \end{example} As a bonus, we also show the result of transposing every tableau in each sequence $\lambda_1$, $\lambda_2$, and $\mu_2$, and filling the tableau from the right yielding the following $2$-coloured permutation in Figure~\ref{fig:inperm}. \begin{figure}[htp] \begin{center} \begin{tikzpicture}[scale=1.5] \foreach \i in {1,...,6} \node[pnt,label=below:$\i$] at (\i,0)(\i) {}; \draw[bend left=45](1) to node[pos=0.2,above]{$\scriptstyle1$} (3); \draw[bend left=30](2) to node[pos=0.7, above]{$\scriptstyle2$} (6); \draw[bend left=30](4) to node[above]{$\scriptstyle2$} (5); \draw[bend left=30](3) to node[above]{$\scriptstyle1$} (4); \draw[bend right=30](1) to node[pos=0.2, below]{$\scriptstyle2$} (5); \draw[bend right=30](2) to node[pos=0.8, below]{$\scriptstyle2$} (6); \end{tikzpicture} \caption[The image of the $2$-coloured permutation] {Interchanging nesting and crossing numbers of Example~\ref{ex:perm}} \label{fig:inperm} \end{center} \end{figure} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Enumeration of coloured set partitions---another approach} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{sec:enum} A quick overview of Marberg's approach~\citep{Mar12} for the enumeration of coloured set partitions helps set the stage for a new interpretation. \subsection{Marberg's \texorpdfstring{$\mathcal{G}_{j,k,r}$}{Gjkr} for set partitions} Marberg viewed $r$ sequences of vacillating tableaux, one for each colour, as $r \times (k-1)$ matrices $A = [A_{i,l}]$ encoding $\lambda^l_i$ in a vacillating tableau sequence $T$ for colour $i$. If the set partition is $j$-noncrossing and $k$-nonnesting, then this tableau has a maximum of $j-1$ columns and $k-1$ rows. For colour $i$, the $i$th row of matrix $A$ just lists parts of $\lambda^l$, thus at most $k-1$ non-zero parts. The multigraph $\mathcal{G}_{j,k,r}$ is drawn using all such allowable $A$'s as vertices, and edges and loops connecting vertices corresponding to adding a box, deleting a box, or doing nothing in the construction of vacillating tableaux so that the resulting sequence contains only tableaux of at most $j-1$ columns and $k-1$ rows. Once completed, the multigraph $\mathcal{G}_{j,k,r}$ gives rise to an adjacency matrix. To find the number $\NCN_{j,k}(n,r)$ which is also the number of ($n-1$)-step walks on $\mathcal{G}_{j,k,r}$ from the zero matrix to itself, the method of transfer matrix gives a quotient of two polynomials (determinants actually), thus concluding that the ordinary generating function $\sum_{n \ge 0}\NCN_{j,k}(n+1,r) x^n$ is rational. \subsection{From exhaustive generation to \texorpdfstring{$\mathcal{G}_{j,k,r}$}{Gjkr} for set partitions} \label{subsec:setpartG} To illustrate the construction of $\mathcal{G}_{j,k,r}$, we first reconstruct Marberg's $\mathcal{G}_{2,2,1}$ and $\mathcal{G}_{2,2,2}$ via the first three steps of the following \textbf{enumeration scheme}: \begin{enumerate} \item Generate all set partitions according to size (level of the tree). \item Organize each level according to the types of \emph{consecutive gaps} (described below). \item Construct a finite state automaton (also Marberg's multigraph, $\mathcal{G}_{j,k,r}$) where states track the number of openers with their corresponding crossing and nesting statistics, and edges track the types of consecutive gaps in set partitions. \item Apply Marberg's bijection from the set of all $j$-noncrossing, $k$-nonnesting, $r$-coloured set partitions of size $n+1$ to the set of all $n$-step closed walks on $\mathcal{G}_{j,k,r}$ from its initial vertex. \item Apply the method of transfer matrix on the adjacency matrix of $\mathcal{G}_{j,k,r}$ to yield a rational series. \end{enumerate} \subsubsection{Construction of \texorpdfstring{$\mathcal{G}_{2,2,1}$}{G221}} The arc annotated diagram of a set partition on $[n]$ has $n-1$ \emph{consecutive gaps}, i.\,e.\ between each pair of adjacent points. Let the set of noncrossing, nonnesting, uncoloured set partitions on $[n]$ be denoted by $\mathcal{P}_{2,2,1}(n)$. Figure~\ref{fig:1part} shows the first three levels of exhaustive generation. \begin{figure} \centering \begin{tikzpicture}[every node/.style={outer sep=5pt},scale=0.7 ] \node at (0,0) (v) {% \begin{tikzpicture} \draw (0,0) node[pnt]{}; \end{tikzpicture}}; \node at (3,3) (v1) {% \begin{tikzpicture} \draw (0,0) node[pnt]{} (1,0) node[pnt]{}; \end{tikzpicture}}; \draw (v) -- (v1.west); \node at (3,0) (v2) {% \begin{tikzpicture} \draw (0,0) node[pnt]{} to[bend left] (1,0) node[pnt]{}; \end{tikzpicture}}; \draw (v) -- (v2.west); \node at (3,-3) (v3) {% \begin{tikzpicture} \draw[->] (0,0) node[pnt]{} to[out=45, in=180] +(0.8,0.2); \draw (1,0) node[pnt]{}; \end{tikzpicture}}; \draw (v) -- (v3.west); \node at (7,4) (v11) {% \begin{tikzpicture} \draw (0,0) node[pnt]{} (1,0) node[pnt]{} (2,0) node[pnt]{}; \end{tikzpicture}}; \draw (v1.east) -- (v11.west); \node at (7,3) (v12) {% \begin{tikzpicture} \draw (0,0) node[pnt]{} (1,0) node[pnt]{} to[bend left] (2,0) node[pnt]{}; \end{tikzpicture}}; \draw (v1.east) -- (v12.west); \node at (7,2) (v13) {% \begin{tikzpicture} \draw (0,0) node[pnt]{} (2,0) node[pnt]{}; \draw[->] (1,0) node[pnt]{} to[out=45, in=180] +(0.8,0.2); \end{tikzpicture}}; \draw (v1.east) -- (v13.west); \node at (7,1) (v21) {% \begin{tikzpicture} \draw (0,0) node[pnt]{} to[bend left] (1,0) node[pnt]{} (2,0) node[pnt]{}; \end{tikzpicture}}; \draw (v2.east) -- (v21.west); \node at (7,0) (v22) {% \begin{tikzpicture} \draw (0,0) node[pnt]{} to[bend left] (1,0) node[pnt]{} to[bend left] (2,0) node[pnt]{}; \end{tikzpicture}}; \draw (v2.east) -- (v22.west); \node at (7,-1) (v23) {% \begin{tikzpicture} \draw[->] (0,0) node[pnt]{} to[bend left] (1,0) node[pnt]{} to[out=45, in=180] +(0.8,0.2); \draw (2,0) node[pnt]{}; \end{tikzpicture}}; \draw (v2.east) -- (v23.west); \node at (7,-2.5) (v31) {% \begin{tikzpicture} \draw[->] (0,0) node[pnt]{} to[out=45, in=180] +(0.8,0.2); \draw (1,0) node[pnt]{} (2,0) node[pnt]{}; \end{tikzpicture}}; \draw (v3.east) -- (v31.west); \node at (7,-3.5) (v32) {% \begin{tikzpicture}[decoration={ markings, mark=at position 0.5 with {\arrow{>}} }] \draw[postaction=decorate] (0,0) node[pnt]{} to[bend left] (2,0) node[pnt]{}; \draw (1,0) node[pnt]{}; \end{tikzpicture}}; \draw (v3.east) -- (v32.west); \draw[magenta] (v2.south west) rectangle (v1.north east); \end{tikzpicture} \caption{Noncrossing, nonnesting, uncoloured set partitions} \label{fig:1part} \end{figure} \begin{table}[htb] \figurefontsize\centering \begin{tabular}{cccc} Domain & Set partition & Types of arcs & Types of steps in $\mathcal{G}_{2,2,1}$ and $\mathcal{G}_{2,2,2}$ \\ \hline $m \ge 2$ & \begin{tikzpicture} \path (0, 0) node[pnt]{} node[below]{$m-1$} (1, 0) node[pnt]{} node[below]{$m\phantom{1}$}; \end{tikzpicture} & no arc & \begin{tikzpicture}[baseline={(0,0)}] \draw (0,0) node[pnt]{} to[loop above] node[right]{$\scriptstyle\times$} (); \end{tikzpicture} \\ $m \ge 2$ & \begin{tikzpicture} \draw[bend left] (0,0) node[pnt]{} node[below]{$m-1$} to node[above]{$\scriptstyle r$} (1,0) node[pnt]{} node[below]{$m\phantom{1}$}; \end{tikzpicture} & a $1$-arc coloured $r$ & \begin{tikzpicture} \draw (0,0) node[pnt]{} to[loop above] node[right]{$\scriptstyle r$} (); \end{tikzpicture}, $r \in [2]$ \\ $m \ge 2$ & \begin{tikzpicture} \draw[bend left,uni] (0,0) node[pnt]{} node[below]{$m-1$} to node[above]{$\scriptstyle r$} +(0.7,0.3); \draw (1,0) node[pnt]{} node[below]{$m\phantom{1}$}; \end{tikzpicture} & an opener & \begin{tikzpicture} \draw[uni] (0,0) node[pnt]{} node[below]{$v_i$} -- node[above]{$\scriptstyle r$} (1,0) node[pnt]{} node[below]{$v_{i+1}$}; \end{tikzpicture} \\ $m \ge 3$ & \begin{tikzpicture} \draw[bend right,unir] (1,0) node[pnt]{} node[below]{$m\phantom{1}$} to node[above]{$\scriptstyle r$} +(-0.7,0.3); \draw (0,0) node[pnt]{} node[below]{$m-1$}; \end{tikzpicture} & a closer & \begin{tikzpicture} \draw[uni] (1,0) node[pnt]{} node[below]{$v_{i+1}$} -- node[below]{$\scriptstyle r$} (0,0) node[pnt]{} node[below]{$v_{i}$}; \end{tikzpicture} \\ $m \ge 3$ & \begin{tikzpicture} \draw[bend left,uni] (0,0) node[pnt]{} node[below]{$m-1$} to node[above,near end]{$\scriptstyle 2$} +(1,0.3); \draw[bend right,unir] (1,0) node[pnt]{} node[below]{$m\phantom{1}$} to node[above,near end]{$\scriptstyle 1$} +(-1,0.3); \end{tikzpicture} & a closer and an opener & \begin{tikzpicture} \draw[uni] (0,1) node[pnt]{} node[right]{$v_{i_1}$} -- node[right] {$\scriptstyle 12$} (0,0) node[pnt] {} node[right]{$v_{i_2}$}; \end{tikzpicture} \end{tabular} \caption[Set partition and its multigraph] { \emph{Consecutive gaps} in set partitions and their corresponding steps in $\mathcal{G}_{2,2,r}$.} \label{tab:five} \end{table} To organize the set partitions on each level, we note that for each $P \in \mathcal{P}_{2,2,1}(n)$, a consecutive gap belongs to one of the first four types in Table~\ref{tab:five} where the matching steps in $\mathcal{G}_{2,2,1}$ are also given. Since $r=1$, only two states exist in the finite state automaton, $\mathcal{G}_{2,2,1}$: $v_0$, the initial state with no opener (boxed in Figure~\ref{fig:1part} for level $2$), and $v_1$, for one opener. No other states are present because any state $v_i$ with $i \ge 2$ openers will form at least a $2$-nesting or $2$-crossing when closed. Incident at $v_0$ are three types of edges: two loops, \begin{tikzpicture}[baseline={(0,0)}] \draw (0,0) node[pnt]{} to[loop above] node[right]{$\scriptstyle\times$} (); \end{tikzpicture} for no arc in the consecutive gap, and \begin{tikzpicture}[baseline={(0,0)}] \draw (0,0) node[pnt]{} to[loop above] node[right]{$\scriptstyle1$} (); \end{tikzpicture} for a distance $1$-arc both of which do not change the number of openers present as consecutive gaps are encountered; the last type is a directed edge from $v_0$ to $v_1$ to indicate that an opener is present in the consecutive gap. Once at $v_1$, only the loop, \begin{tikzpicture}[baseline={(0,0)}] \draw (0,0) node[pnt]{} to[loop above] node[right]{$\scriptstyle\times$} (); \end{tikzpicture}, is allowed because a $1$-arc \begin{tikzpicture}[baseline={(0,0)}] \draw (0,0) node[pnt]{} to[loop above] node[right]{$\scriptstyle1$} (); \end{tikzpicture} will create a $2$-nesting in $P$ with the existing opener. A directed edge from $v_1$ to $v_0$ means that an opener is closed. To simplify drawing, an edge without arrows is bidirectional. The result is shown in Figure~\ref{fig:setpartG221}. \subsubsection{Construction of \texorpdfstring{$\mathcal{G}_{2,2,2}$}{G222}} We first show the tree of exhaustive generation in Figure~\ref{fig:2part}. Rectangular boxes group \emph{consecutive gaps} according to the number of openers. Dashed and shaded triangles indicate similar children generation of a partition: without any opener, a dashed triangle repeats the generation established in the big dashed triangle, and similarly for the shaded box for the generation of children from one opener in their parent. \begin{figure} \centering \begin{tikzpicture}[every node/.style={outer sep=1pt},yscale=0.7] \node at (0,4) (v) {% \begin{tikzpicture} \draw (0,0) node[pnt]{}; \end{tikzpicture}}; \node at (3,8) (v1) {% \begin{tikzpicture} \draw (0,0) node[pnt]{}; \draw (1,0) node[pnt]{}; \end{tikzpicture}}; \draw (v.east) -- (v1.west); \node at (3,6) (v2) {% \begin{tikzpicture} \draw (0,0) node[pnt]{} to[bend left] node[above]{\small$1$} (1,0) node[pnt]{}; \end{tikzpicture}}; \draw (v.east) -- (v2.west); \node at (3,4) (v3) {% \begin{tikzpicture} \draw (0,0) node[pnt]{} to[bend left] node[above]{\small$2$} (1,0) node[pnt]{}; \end{tikzpicture}}; \draw (v.east) -- (v3.west); \node at (3,0) (v4) {% \begin{tikzpicture} \draw[ ->] (0,0) node[pnt]{} to[out=45, in=180] node[above]{\small$1$} +(0.8,0.2); \draw (1,0) node[pnt]{}; \end{tikzpicture}}; \draw (v.east) -- (v4.west); \node at (3,-4) (v5) {% \begin{tikzpicture} \draw[ ->] (0,0) node[pnt]{} to[out=45, in=180] node[above]{\small$2$} +(0.8,0.2); \draw (1,0) node[pnt]{}; \end{tikzpicture}}; \draw (v.east) -- (v5.west); \draw[dashed,thick] (v.north east) -- (v1.north west) -- (v1.north east) -- (v5.south east) -- (v5.south west) -- (v.south east) -- cycle; \draw[dashed,thick] (v1.east) -- +(3,0.5) -- +(3,-0.5) -- cycle; \draw[dashed,thick] (v2.east) -- +(3,0.5) -- +(3,-0.5) -- cycle; \draw[dashed,thick] (v3.east) -- +(3,0.5) -- +(3,-0.5) -- cycle; \node at (7,2) (v41) {% \begin{tikzpicture} \draw[->] (0,0) node[pnt]{} to[out=45, in=180] node[above]{\small$1$} +(0.8,0.2); \draw (1,0) node[pnt]{} (2,0) node[pnt]{}; \end{tikzpicture}}; \draw (v4.east) -- (v41.west); \node at (7,1) (v42) {% \begin{tikzpicture} \draw[->] (0,0) node[pnt]{} to[out=45, in=180] node[above]{\small$1$} +(0.8,0.2); \draw (1,0) node[pnt]{} to[bend left] node[above]{\small$2$} (2,0) node[pnt]{}; \end{tikzpicture}}; \draw (v4.east) -- (v42.west); \node at (7,0) (v43) {% \begin{tikzpicture} \draw[->] (0,0) node[pnt]{} to[out=45, in=180] node[above]{\small$1$} +(0.8,0.2); \draw[->] (1,0) node[pnt]{} to[out=45, in=180] node[above]{\small$2$}+(0.8,0.2); \draw (2,0) node[pnt]{}; \end{tikzpicture}}; \draw (v4.east) -- (v43.west); \node at (7,-1) (v44) {% \begin{tikzpicture}[decoration={ markings, mark=at position 0.5 with {\arrow{>}} }] \draw[postaction=decorate] (0,0) node[pnt]{} to[bend left] node[below left]{\small$1$} (2,0) node[pnt]{}; \draw (1,0) node[pnt]{}; \end{tikzpicture}}; \draw (v4.east) -- (v44.west); \node at (7,-2) (v45) {% \begin{tikzpicture} \draw (0,0) node[pnt]{} to[bend left] node[below left]{\small$1$} (2,0) node[pnt]{}; \draw[->,xscale=1.2] (5/6,0) node[pnt]{} to[out=45, in=180] node[below]{\small$2$}+(0.8,0.2); \end{tikzpicture}}; \draw (v4.east) -- (v45.west); \fill[very nearly transparent] (v4.north east) -- (v41.north west) -- (v41.north east) -- (v45.south east) -- (v45.south west) -- (v4.south east) -- cycle; \fill[very nearly transparent] (v5.east) -- +(3,0.5) -- +(3,-0.5) -- cycle; \draw[magenta] (v3.south west) rectangle (v1.north east); \draw[magenta] (v5.south west) rectangle (v4.north east); \end{tikzpicture} \caption{Noncrossing, nonnesting, $2$-coloured set partitions} \label{fig:2part} \end{figure} To construct $\mathcal{G}_{2,2,2}$, we organize the types of consecutive gaps in set partitions into four states in our finite state automaton: $v_0$ as the initial state for no opener, two states indicating one $r$-coloured ($r \in [2]$) opener, $v_{1_1}$ and $v_{1_2}$, and one more state, $v_{2_{12}}$, for two openers, one of each colour, since two arcs of different colours do not create a crossing or nesting. As in $\mathcal{G}_{2,2,1}$, the loops and edges are placed according to what is allowed in $P$, but a new edge between $v_{1_1}$ and $v_{1_2}$ is added in the last row of Table~\ref{tab:five} for the closing of one colour on point $m$ while an opener is present at point $m-1$ in $P$. The result is shown in Figure~\ref{fig:setpartG222}. For details on how the adjacency matrices for Figures~\ref{fig:setpartG221} and~\ref{fig:setpartG222} give rise to generating functions, please see \citep{Yen12colour}. \begin{figure} \begin{minipage}{0.45\linewidth} \figurefontsize\centering \begin{tikzpicture} \node[state] (O) at (0,0) {$v_0$}; \node[state] (I) at (2,0) {$v_1$}; \draw[loop above left] (O) to node[above]{$\scriptstyle\times$}(); \draw[loop below left] (O) to node[below]{$\scriptstyle1$}(); \draw[loop right] (I) to node[right]{$\scriptstyle\times$}(); \draw (O) to node[above]{$\scriptstyle1$}(I); \end{tikzpicture} \caption{An uncoloured set partition graph, $\mathcal{G}_{2, 2, 1}$.} \label{fig:setpartG221} \end{minipage} %\end{figure} \qquad %\begin{figure} \begin{minipage}{0.45\linewidth} \figurefontsize\centering \begin{tikzpicture}[state/.append style={minimum size=8mm}] \node[state] (O) at (-1,0) {$v_0$}; \node[state] (A) at (1,1) {$v_{1_1}$}; \node[state] (B) at (1, -1) {$v_{1_2}$}; \node[state] (C) at (3, 0) {$v_{2_{12}}$}; \draw[loop above] (O) to node[above]{$\scriptstyle\times$} (); \draw[loop below] (O) to node[below]{$\scriptstyle1$}(); \draw[loop left] (O) to node[left]{$\scriptstyle2$}(); \draw[loop above left] (A) to node[left]{$\scriptstyle\times$} (); \draw[loop above right] (A) to node[right]{$\scriptstyle2$}(); \draw[loop below left] (B) to node[left]{$\scriptstyle\times$}(); \draw[loop below right] (B) to node[below]{$\scriptstyle1$}(); \draw[loop right] (C) to node[right]{$\scriptstyle\times$}(); \draw (O) to node[above]{$\scriptstyle1$} (A); \draw (O) to node[below]{$\scriptstyle2$} (B); \draw (A) to node[right]{$\scriptstyle12$} (B); \draw (A) to node[right]{$\scriptstyle2$} (C); \draw (B) to node[right]{$\scriptstyle1$} (C); \end{tikzpicture} \caption{A $2$-coloured set partition graph, $\mathcal{G}_{2, 2, 2}$.} \label{fig:setpartG222} \end{minipage} \end{figure} To construct the multigraph, $\mathcal{G}_{j,k,r}$, for general $j, k > 2$, the organization of vertices according to the number of openers (as in Figure~\ref{fig:vertices}) combined with the crossing and nesting statistics produced by the openers (as in Marberg's tableaux sequence bijection~\citep{Mar12}) yields an automation algorithm. \begin{figure}[htb] \centering\figurefontsize \begin{tikzpicture}[xscale=4,yscale=0.6] \node (0) at (0,0) {$v_0$}; \node (11) at (1,1.5) {$v_{1_1}$}; \node (12) at (1,0.5) {$v_{1_2}$}; \node at (1,-0.5) {$\vdots$}; \node (1r) at (1,-1.5) {$v_{1_r}$}; \node (211) at (2,3) {$v_{2_{11}}$}; \node (212) at (2,2) {$v_{2_{12}}$}; \node at (2,1) {$\vdots$}; \node (21r) at (2,0) {$v_{2_{1r}}$}; \node (221) at (2,-1) {$v_{2_{21}}$}; \node at (2,-2) {$\vdots$}; \node (2rr) at (2,-3) {$v_{2_{rr}}$}; \foreach \i in {1,2,r} { \draw (0) -- (1\i); \foreach \j in {11,12,1r,21,rr} \draw (1\i) -- (2\j); } \foreach \j in {11,12,1r,21,rr} { \draw (2\j) -- +(0.5,0.2); \draw (2\j) -- +(0.5,0); \draw (2\j) -- +(0.5,-0.2); } \end{tikzpicture} \caption{The line-up for states of the same number of openers} \label{fig:vertices} \end{figure} We list the first few series for $\mathcal{G}_{2,2,r}$, $r = \{3, 4\}$. The first two series, $r=1, 2$ were found by \citet{Mar12} where A216949 in \citep{oeis} is for $r=2$. Our series mark the number of consecutive gaps, namely, $x^k$ counts the number of such coloured set partitions on $k+1$ elements. For more terms and the rational functions, please consult A225029--A225033 in \citep{oeis} for $r=3$ to $7$. \[ \begin{split} \sum_{n \ge 0} \NCN_{2,2}(n, 3) x^n &= \frac{1-10x+22x^2-x^3}{1-14x +59 x^2-74x^3+x^4} \\ &=1+4x+19x^2+103x^3+616x^4+3949x^5+\dots \\ \sum_{n \ge 0} \NCN_{2,2}(n, 4) x^n &= \frac{1-20x+122x^2-224x^3+x^4}{1-25x +218 x^2-782x^3+973x^4-x^5} \\ &=1+5x+29x^2+193x^3+1441x^4+\dots \end{split} \] Using an average personal computer, Maple~15 can generate up to $7$ colours. The next case, $r=8$, with a matrix size of $256 \times 256$, computation would take too long to find the determinants. %%%%%%%%%%%%%%%%%%%%%%%%% \section{Enumeration of \texorpdfstring{$r$}{r}-coloured permutations} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{sec:permenum} Similar to the construction of $\mathcal{G}_{j,k,r}(\Pi)$ (i.e.\ the multigraph for set partitions), we modify the first three steps of the \textbf{enumeration scheme} from Section~\ref{subsec:setpartG} for the construction of $\mathcal{G}_{j,k,r}(\Sigma)$, the multigraph for permutations. Once constructed, a similar bijection from the set of all $j$-noncrossing, $k$-nonnesting, $r$-coloured permutations of size $n$ to the set of all $n$-step closed walks on $\mathcal{G}_{j,k,r}(\Sigma)$ from its initial vertex permits a routine application of the method of transfer matrix to the adjacency matrix of $\mathcal{G}_{j,k,r}(\Sigma)$, thus resulting in a rational series. \begin{enumerate} \item Generate all permutations from $\emptyset$ as shown in Figure~\ref{fig:2perm} for $\mathcal{G}_{2,2,2}(\Sigma)$. \begin{figure} \centering \begin{tikzpicture}[yscale=0.2,xscale=0.5] \node (0) at (0,-5) {$\emptyset$}; \node (v1r) at (5,10) {\begin{tikzpicture} \draw (0,0) node[pnt,black]{} to[loop above] node[above, right]{\small$1$} (0,0); \end{tikzpicture}}; \node (v1b) at (5,5) {\begin{tikzpicture} \draw (0,0) node[pnt,black]{} to[loop above] node[above, right]{\small$2$} (0,0); \end{tikzpicture}}; \node (v1rr) at (5,0) {\vOne11}; \node (v1rb) at (5,-5) {\vOne12}; \node (v1br) at (5,-10) {\vOne21}; \node (v1bb) at (5,-15) {\vOne22}; \node (v2rr) at (15,10) {\begin{tikzpicture} \draw (0,0) to[bend left] node[above]{\small$1$} (1,0) to[bend left] node[below]{\small$1$} (0,0); \draw (0,0) node[pnt]{} (1,0) node[pnt]{}; \end{tikzpicture}}; \node (v2rrbl) at (15,5) {\begin{tikzpicture} \draw (0,0) to[bend left] +(0.4,0.2) node[right,inner sep=1pt]{\small$1$}; \draw (0,0) to[bend right] +(0.4,-0.2) node[right,inner sep=1pt]{\small$1$}; \draw (0,0) node[pnt]{} (1,0) node[pnt]{}; \draw (1,0) node[pnt,black]{} to[loop above] node[above, right]{\small$2$} (1,0); \end{tikzpicture}}; \node (v2rbr) at (15,0) {\begin{tikzpicture} \draw (0,0) to[bend left] node[above]{\small$1$}(1,0); \draw (1,0) to[bend left] +(0.4,0.2) node[right,inner sep=1pt]{\small$2$}; \draw (0,0) to[bend right] +(1.4,-0.2) node[right,inner sep=1pt]{\small$1$}; \foreach \i in {0,1} \node[pnt] at (\i,0) {}; \end{tikzpicture}}; \node (v2rrr) at (15,-5) {\begin{tikzpicture} \draw (0,0) to[bend left] +(1.4,0.3) node[right,inner sep=1pt]{\small$1$}; \draw (0,0) to[bend right] node[below]{\small$1$} (1,0) to[bend right] +(0.4,-0.2) node[right,inner sep=1pt]{\small$1$}; \foreach \i in {0,1} \node[pnt] at (\i,0) {}; \end{tikzpicture}}; \node (v2rrb) at (15,-10) {\begin{tikzpicture} \draw (0,0) to[bend left] +(1.4,0.3) node[right,inner sep=1pt]{\small$1$}; \draw (0,0) to[bend right] node[below]{\small$1$}(1,0); \draw (1,0) to[bend right] +(0.4,-0.2) node[right,inner sep=1pt]{\small$2$}; \foreach \i in {0,1} \node[pnt] at (\i,0) {}; \end{tikzpicture}}; \node (v2rrbb) at (15,-15) {\begin{tikzpicture} \draw (0,0) to[bend left] +(0.4,0.2) node[right,inner sep=1pt]{\small$1$}; \draw (0,0) to[bend right] +(0.4,-0.2) node[right,inner sep=1pt]{\small$1$}; \draw (1,0) to[bend left] +(0.4,0.2) node[right,inner sep=1pt]{\small$2$}; \draw (1,0) to[bend right] +(0.4,-0.2) node[right,inner sep=1pt]{\small$2$}; \foreach \i in {0,1} \node[pnt] at (\i,0) {}; \end{tikzpicture}}; \foreach \i in {v1r, v1b, v1rr, v1rb, v1br, v1bb} \draw (0.east) -- (\i.west); \foreach \i in {v2rr, v2rrbl, v2rbr, v2rrr, v2rrb, v2rrbb} \draw (v1rr.east) -- (\i.west); \fill[very nearly transparent] (0.north east) -- (v1r.north west) -- (v1r.north east) -- (v1bb.south east) -- (v1bb.south west) -- (0.south east) -- cycle; \foreach \i in {v1r, v1b, v2rr} \fill[very nearly transparent] (\i.east) -- +(3,0.5) -- +(3,-0.5) -- cycle; \end{tikzpicture} \caption{Noncrossing, nonnesting, $2$-coloured permutations} \label{fig:2perm} \end{figure} \item Organize each level according to types of vertices present. \item Construct a finite state automaton $\mathcal{G}_{j,k,r}(\Sigma)$ (i.e.\ the multigraph for permutations) where the states track the number of opener pairs with their corresponding crossing and nesting statistics, and edges track the types of vertices in permutations. \end{enumerate} We remark that an analogous bijection from the set of all $j$-noncrossing, $k$-nonnesting, $r$-coloured permutations of size $n$ to the set of all $n$-step closed walks on $\mathcal{G}_{j,k,r}(\Sigma)$ from its initial state leads to a rational series via the method of transfer matrix. \subsection{Warm-up examples} Instead of translating consecutive gaps from set partitions into steps in the multigraph $\mathcal{G}_{j,k,r}(\Pi)$, we examine each vertex in the arc diagram of a coloured permutation and assign each type of vertex to a step in $\mathcal{G}_{j,k,r}(\Sigma)$. The construction of the first two cases help build intuition for the general case. \subsubsection{Construction of \texorpdfstring{$\mathcal{G}_{2, 2, 1}(\Sigma)$}{G221}} As for set partitions, we first construct the multigraph $\mathcal{G}_{2,2,1}(\Sigma)$ for noncrossing, nonnesting, uncoloured permutations. Let us denote the set of all such permutations on $[n]$ by $\mathcal{S}_{2,2,1}(n)$. If $S \in \mathcal{S}_{2,2,1}(n)$, then a vertex is either a fixed point ( \begin{tikzpicture} \draw[loop above] (0,0) node[pnt]{} to (0.0); \end{tikzpicture} ) , an opener ( \begin{tikzpicture} \draw[bend left] (1.2,0) node[pnt]{} to +(0.3,0.2); \draw[bend right] (1.2, 0) to (1.5, -0.2); \end{tikzpicture} ), a closer ( \begin{tikzpicture} \draw[bend right] (1.5,0) node[pnt]{} to (1.2, 0.2); \draw[bend left] (1.5, 0) to (1.2, -0.2); \end{tikzpicture} ), or a lower transitory( \begin{tikzpicture} \draw[bend right] (0,0) node[pnt]{} to (0.3,-0.2); \draw[bend left] (0,0) to (-0.3, -0.2); \end{tikzpicture} ). We can't have an upper transitory which contributes to a $2$-(enhanced) crossing. In Figure~\ref{fig:permG221}, $v_0$ still indicates the initial state with $0$ opener; $v_1$ indicates the state with $1$ opener. The loop labelled $1$ is the step taken when a fixed point coloured $1$ is encountered in the vertex set of the permutation. The loop labelled $1_t$ is the presence of a lower transitory with coloured $1$ arcs on both sides; this is possible only when an opener coloured $1$ is present, thus at $v_1$. Note that a lower transitory does not alter the state. The directed edge $(v_0, v_1)$ indicates the presence of an opener, and the edge traversed in reverse indicates that of a closer. An edge drawn without arrows still means a bidirectional edge. \begin{figure} \figurefontsize\centering \begin{tikzpicture} \node[state] (O) at (0,0) {$v_0$}; \node[state] (I) at (1.5,0) {$v_1$}; \draw[loop left] (O) to node[left]{$\scriptstyle1$}(); \draw[loop right] (I) to node[right]{$\scriptstyle1_t$}(); \draw (O) to node[above]{$\begin{smallmatrix}1\\1\end{smallmatrix}$}(I); \end{tikzpicture} \caption{An uncoloured permutation graph, $\mathcal{G}_{2, 2, 1}$.} \label{fig:permG221} \end{figure} \subsubsection{Construction of \texorpdfstring{$\mathcal{G}_{2, 2, 2}(\Sigma)$}{G222}} The construction of $\mathcal{G}_{2,2,2}$ involves more types of states and edges which we summarize in Table~\ref{tab:perm}. The tree of generation in Figure~\ref{fig:2perm} shows the types of vertices to organize for the finite state automaton. Each state with one opener has the colour of the opener as its subscript. When a state has two openers, both colours are used, thus only one such vertex in $v_2$. The method of transfer matrix gives the following generating function. Here $x$ marks the size of the permutation. \[ \begin{split} \sum_{n \ge 0} \NCN_{2,2}(n, 2) x^n &= \frac{1-6x+4x^2}{(1-2x)(1-6x)} \\ &=1+2x+8x^2+40x^3+224x^4+1312x^5+7808x^6+O(x^7). \end{split} \] This series, A092807 in \citep{oeis}, counts (with interpolated zeros) the number of closed walks of length $n$ at a vertex of the edge-vertex incidence graph of $K_4$, the complete graph on $4$ vertices associated with the edges of $K_4$. \begin{table}[htb] \figurefontsize\centering \begin{tabular}{cccc} Domain & Permutation Vertex & Arcs & Steps in $\mathcal{G}_{2,2,2}(\Sigma)$ \\ \hline all vertices & \begin{tikzpicture} \draw[loop above] (0,0) node[pnt]{} to node[above]{$\scriptstyle l$}(0.0); \end{tikzpicture} & a fixed point & \begin{tikzpicture}[baseline={(0,0)}] \draw (0,0) node[pnt]{} to[loop above] node[right]{$\scriptstyle l$} (); \end{tikzpicture}, $l \in [2]$ \\ all except the last & \begin{tikzpicture} \draw[bend left] (1.2,0) node[pnt]{} to node[above]{$\scriptstyle r$} +(0.3,0.2); \draw[bend right] (1.2, 0) to node[below]{$\scriptstyle s$}(1.5, -0.2); \end{tikzpicture} & an opener & \begin{tikzpicture} \draw[uni] (0,0) node[pnt]{} node[below]{$v_i$} -- node[above]{$\begin{smallmatrix}r\\s\end{smallmatrix}$} (1,0) node[pnt]{} node[below]{$v_{i+1}$}; \end{tikzpicture}, $r, s \in [2]$ \\ all except the first & \begin{tikzpicture} \draw[bend right] (1.5,0) node[pnt]{} to node[above]{$\scriptstyle r$} (1.2, 0.2); \draw[bend left] (1.5, 0) to node[below]{$\scriptstyle s$}(1.2, -0.2); \end{tikzpicture} & a closer & \begin{tikzpicture} \draw[uni] (1,0) node[pnt]{} node[below]{$v_{i+1}$} -- node[above]{$\begin{smallmatrix}r\\s\end{smallmatrix}$} (0,0) node[pnt]{} node[below]{$v_{i}$}; \end{tikzpicture}, $r, s \in [2]$ \\ no first, no last & \begin{tikzpicture} \draw[bend right] (0,0) node[pnt]{} to node[below]{$\scriptstyle r$} (0.3,-0.2); \draw[bend left] (0,0) to node[below]{$\scriptstyle r$} (-0.3, -0.2); \end{tikzpicture} & a lower transitory & \begin{tikzpicture}[baseline={(0,0)}] \draw (0,0) node[pnt]{} to[loop above] node[right]{$\scriptstyle r_t$} (); \end{tikzpicture}, $r \in [2]$ \\ no first, no last & \begin{tikzpicture} \draw[bend left] (0,0) node[pnt]{} to node[above]{$\scriptstyle s$}+(0.3,0.2); \draw[bend right] (0,0) to node[above]{$\scriptstyle r$}(-0.3, 0.2); \end{tikzpicture} &an upper transitory & \begin{tikzpicture} \draw[uni] (0,1) node[pnt]{} node[right]{$v_{i_r}$} -- node[right] {$\scriptstyle \underline{rs}$} (0,0) node[pnt] {} node[right]{$v_{i_s}$}; \end{tikzpicture}, $r, s \in [2]$ \\ no first, no last & \begin{tikzpicture} \draw[bend right] (0,0) node[pnt]{} to node[below]{$\scriptstyle r$} (0.3,-0.2); \draw[bend left] (0,0) to node[below]{$\scriptstyle s$} (-0.3, -0.2); \end{tikzpicture} & a lower transitory & \begin{tikzpicture} \draw[unir] (0,1) node[pnt]{} node[right]{$v_{i_r}$} -- node[right] {$\scriptstyle \overline{sr}$} (0,0) node[pnt] {} node[right]{$v_{i_s}$}; \end{tikzpicture}, $r, s \in [2]$ \end{tabular} \caption{Vertices in permutations and their corresponding steps in $\mathcal{G}_{2,2,2}(\Sigma)$. } \label{tab:perm} \end{table} \begin{figure} \label{fig:permG222} \figurefontsize\centering \begin{tikzpicture} \node[state] (O) at (0,0) {$v_0$}; \node[state] (A) at (4, 3) {$v_{1_{\begin{smallmatrix}1\\1\end{smallmatrix}}}$}; \node[state] (B) at (4, 1) {$v_{1_{\begin{smallmatrix}1\\2\end{smallmatrix}}}$}; \node[state] (C) at (4,-1) {$v_{1_{\begin{smallmatrix}2\\1\end{smallmatrix}}}$}; \node[state] (D) at (4,-3) {$v_{1_{\begin{smallmatrix}2\\2\end{smallmatrix}}}$}; \node[state] (E) at (8, 0) {$v_{2_{\begin{smallmatrix}1,2\\1,2\end{smallmatrix}}}$}; \draw[loop above left] (O) to node[above]{$\scriptstyle1$} (); \draw[loop below left] (O) to node[below]{$\scriptstyle2$} (); \draw[loop above left] (A) to node[above]{$\scriptstyle2$} (); \draw[loop above right] (A) to node[above]{$\scriptstyle1_t$} (); \draw[loop above left] (B) to node[above right]{$\scriptstyle2$} (); \draw[loop above right] (B) to node[above]{$\scriptstyle2_t$} (); \draw[loop below right] (C) to node[below]{$\scriptstyle1_t$} (); \draw[loop below left] (C) to node[below right]{$\scriptstyle1$} (); \draw[loop below left] (D) to node[below]{$\scriptstyle1$} (); \draw[loop below right] (D) to node[below]{$\scriptstyle2_t$} (); \draw[loop above right] (E) to node[right]{$\scriptstyle1_t$} (); \draw[loop below right] (E) to node[right]{$\scriptstyle2_t$} (); \draw (O) to node[above]{$\begin{smallmatrix}1\\1\end{smallmatrix}$} (A) to node[right]{$\scriptstyle\overline{12}$} (B) to node[above]{$\begin{smallmatrix}1\\2\end{smallmatrix}$} (O) to node[below]{$\begin{smallmatrix}2\\1\end{smallmatrix}$} (C) to node[right]{$\scriptstyle\overline{12}$} (D) to node[below]{$\begin{smallmatrix}2\\2\end{smallmatrix}$} (O); \draw[bend right] (A) to node[near start,left]{$\scriptstyle\underline{12}$} (C); \draw[bend right] (B) to node[near end,left]{$\scriptstyle\underline{12}$} (D); \draw (A) to node[above]{$\begin{smallmatrix}2\\2\end{smallmatrix}$} (E) to node[above]{$\begin{smallmatrix}1\\2\end{smallmatrix}$} (C); \draw[postaction={decoration}] (E) to node[above]{$\begin{smallmatrix}2\\1\end{smallmatrix}$} (B); \draw (E) to node[below]{$\begin{smallmatrix}1\\1\end{smallmatrix}$} (D); \end{tikzpicture} \caption[A $2$-coloured permutation multigraph] {A $2$-coloured permutation multigraph, $\mathcal{G}_{2, 2, 2}(\Sigma)$ } \end{figure} \subsection{Proof of Rationality through Multigraphs for \texorpdfstring{$r$}{r}-coloured permutations} To construct $\mathcal{G}_{j,k,r}(\Sigma)$ for $j, k \ge 2$ (otherwise, the trivial permutation), we first define the set of labels for the vertices followed by the edge set. To track completed crossing and nesting statistics in addition to the number of opener pairs, we use $r$ copies of hesitating (resp.\ vacillating) tableau bijection sequences for upper (resp.\ lower) arc diagrams of $r$-coloured permutations. An important detail is to track the changes in upper and lower arc diagrams simultaneously for permutations. Extending Marberg's matrix label \citep{Mar12} for each vertex of $\mathcal{G}_{j,k,r}(\Pi)$, we use a pair of matrices \( \left[ \begin{smallmatrix} U\\ L \end{smallmatrix} \right] \) to label each vertex of $\mathcal{G}_{j,k,r}(\Sigma)$ where each matrix $A \in \{U,L\}$ satisfies the following: \begin{enumerate} \item $A$ is a non-negative integer matrix of dimension $r \times (k-1)$. \item Each row $i$ of $A =[A_{i,l}]$ codes the tableau translation of colour $i$ as an integer partition, namely, \[ j > A_{i,1} \ge A_{i,2} \ge \dots \ge A_{i,k-1} \ge 0, \quad \text{for all} \quad i \in [r]. \] \item For each vertex label, \( \left[ \begin{smallmatrix} U\\ L \end{smallmatrix} \right], \) \[ \sum_{l = 1}^{k-1} \sum_{i=1}^{r} U_{i, l} = \sum_{l = 1}^{k-1} \sum_{i=1}^{r} L_{i, l} . \] \end{enumerate} An edge connects vertices labelled \( \left[ \begin{smallmatrix} U\\ L \end{smallmatrix} \right] \) and \( \left[ \begin{smallmatrix} U^{\smash\prime}\\ L^{\smash\prime} \end{smallmatrix} \right], \) if \begin{itemize} \item an opener or closer pair is encountered in a permutation's arc diagram, that is, \[ U - U' = \pm E_{i,l} \quad \text{and} \quad L - L' = \pm E_{m,n} \] where the same sign applies, and $E_{i,l}$ denotes the $r \times (k-1)$ matrix with $1$ in position $(i,l)$ and $0$ elsewhere, or \item a lower or upper transitory is encountered causing a change in tableau sequence, that is, either \[ U = U', \quad \text{and} \quad L-L' = E_{i,l} - E_{m,n}, \] or \[ L=L', \quad \text{and} \quad U - U' = E_{i,l} - E_{m,n}, \] for some $(i,l) \ne (m,n)$, or \item a fixed point, a lower transitory, or an upper transitory is encountered causing no change in the tableau sequence, that is, \( \left[ \begin{smallmatrix} U\\ L \end{smallmatrix} \right] = \left[ \begin{smallmatrix} U^{\smash\prime}\\ L^{\smash\prime} \end{smallmatrix} \right], \) and the number of loops at \( \left[ \begin{smallmatrix} U\\ L \end{smallmatrix} \right] \) is $\sum_{i=1}^r (u_i + l_i)$ where $u_i$ is the number of distinct entries in the $i$th row of $U$ which are less than $j-1$, and $l_i$ is the number of distinct entries in the $i$th row of $L$ greater than $0$. \end{itemize} Note that a fixed point in the arc diagram of a permutation adds a new row to its tableau translation in that colour, whereas upper (resp.\ lower) transitories add a box then delete a box (resp.\ vice versa) for the corresponding rows of the matrix; thus, in the case no change happens to the $r$-tableau sequence, tracking where in the tableaux such a manoeuvre is possible leads to the number of loops for each vertex of $\mathcal{G}_{j,k,r}(\Sigma)$. No other edges are present. Once constructed, $\mathcal{G}_{j,k,r}(\Sigma)$ yields an adjacency matrix which permits the application of the method of transfer matrix, thus resulting in a rational generating function for $j$-noncrossing, $k$-nonnesting, $r$-coloured permutations. Once automated, the construction of $\mathcal{G}_{j,k,r}(\Sigma)$ together with the method of transfer matrix yields the rational series, some of which are shown in Table~\ref{tab:rational}. Table~\ref{tab:degree} lists the degrees of numerator and denominator polynomials for pattern complexity analysis. \begin{table} \centering \begin{tabular}{rrcl@{\Large\strut}} $j$& $k$& $r$\\ \hline $2$& $2$& $1$& $ \frac {1-x}{1-2 x} $ \\ $2$& $3$& $1$& $ \frac {1-3 x+x^{2}}{ ( 1-3 x ) ( 1-x ) } $ \\ $2$& $4$& $1$& $ \frac { 1-5x + 6x^2 -x^{3}}{ ( 1-2 x ) ( 1 - 4x + 2x^2 ) } $ \\ $2$& $5$& $1$& $ \frac { ( 1-x ) (1-6x + 9x^2 - x^{3}) }{ ( 1-3 x+x^{2} ) (1 - 5x + 5 x^{2}) } $ \\ $2$& $6$& $1$& $ \frac {1-9 x+28 x^{2}-35 x^{3}+15 x^{4}-x^{5}}{ ( 1-3 x ) (1-2 x ) ( 1- x ) (1-4x+ x^{2} ) } $ \\ $2$& $7$& $1$& $ \frac {1-11 x+45 x^{2}-84 x^{3}+70 x^{4}-21 x^{5}+x^{6 }}{ (1-7x + 14x^2 - 7 x^{3} ) ( 1-5x + 6x^2 -x^{3}) } $ \\ $2$& $8$& $1$& $ \frac { (1- x ) ( 1-3 x+x^{2} ) (1-9x + 26x^2 - 24x^3+ x^{4}) }{ (1- 2 x ) ( 1-4x +2 x^{2}) (1 -8x + 20x^2 - 16x^3+ 2 x^{4} ) } $ \\ $2$& $9$& $1$& $ \frac {1-15 x+91 x^{2}-286 x^{3}+495 x^{4}-462 x^{5}+210 x^{6}-36 x^{7}+x^{8}}{ ( 1-3 x ) (1- x ) ( 1-6x+9x^2-3 x^{3}) ( 1-6x+9x^2 -x^{3} ) } $ \\ $2$& $10$& $1$& $ \frac {1-17 x+120 x^{2}-455 x^{3}+1001 x^{4}-1287 x^{5} +924 x^{6}-330 x^{7}+45 x^{8}-x^{9}}{ (1- 2 x ) ( 1-3 x+x^{2} ) ( 1-5x +5 x^{2} ) (1 -8x + 19x^2 - 12x^3+ x^{4} ) } $ \\ $3$& $3$& $1$& $ \frac {1-11x+34x^2-30x^3+4 x^{4}}{ (1-8x+ 10 x^{2}) ( 1-4x+ 2 x^{2}) } $ \\ $2$& $2$& $2$& $ \frac {1-6x +4 x^{2}}{ ( 1-6 x ) ( 1-2 x ) } $ \\ $2$& $3$& $2$& $ \frac {1-18x + 95x^2-150x^3+36 x^{4}}{ (1-10x)(1-6x)(1-3x) (1- x ) } $ \\ $2$& $2$& $3$& $ \frac {1-17x+66x^2 -36 x^{3}}{ ( 1-12 x ) (1- 6 x ) (1- 2 x ) } $ \\ $2$& $3$& $3$& $ \frac {1 - 53x + 1012x^2 - 8529x^3 + 31059x^4- 39690x^5 +8100 x^{6}}{ (1-21x)(1-15x)(1-10x)(1-6x)(1-3x)(1-x)} $ \\ $2$& $2$& $4$& $ \frac {1-36x+380x^2-1200x^3+576 x^{4}}{ (1-20x)( 1-12 x ) (1- 6 x ) ( 1-2 x ) } $ \\ $2$& $2$& $5$& $ \frac{ 1-65x+1408x^2-11804x^3+32880x^4-14400x^5 } {(1-30x)(1-20x)(1-12x)(1-6x)(1-2x)} $ \\ %% from previous method: $2$& $2$& $6$& $\frac{1-106x + 4048x^2 - 68232x^3 + 496944x^4-1270080x^5 + 518400x^6}{(1-42x)(1-30x)(1-20x)(1-12x)(1-6x)(1-2x)}$ \\ $2$& $2$& $7$& $\frac{1-161x + 9842x^2 - 287632x^3 + 4152216x^4-27460656x^5 + 65862720x^6 - (7!)^2x^7}{(1-56x)(1-42x)(1-30x)(1-20x)(1-12x)(1-6x)(1-2x)}$ % End previous method \end{tabular} \caption[Selected rational function]{The rational series for selected values of $j$, $k$, and $r$.} \label{tab:rational} \end{table} \begin{table} \makebox[\linewidth][s]{% \begin{tabular}[t]{rrrrr} \multicolumn{1}{c}{$j$}& \multicolumn{1}{c}{$k$}& \multicolumn{1}{c}{$r$}& \multicolumn{1}{c}{$N$}& \multicolumn{1}{c}{$D$} \\\hline $2$& $2$& $1$& $1$& $1$\\ $2$& $3$& $1$& $2$& $2$\\ $2$& $4$& $1$& $3$& $3$\\ $2$& $5$& $1$& $4$& $4$\\ $2$& $6$& $1$& $5$& $5$\\ $2$& $7$& $1$& $6$& $6$\\ $2$& $8$& $1$& $7$& $7$\\ $2$& $9$& $1$& $8$& $8$\\ $2$& $10$& $1$& $9$& $9$\\ $2$& $11$& $1$& $10$& $10$\\ $2$& $12$& $1$& $11$& $11$\\ $2$& $13$& $1$& $12$& $12$\\ $2$& $14$& $1$& $13$& $13$\\ $2$& $15$& $1$& $14$& $14$\\ $2$& $16$& $1$& $15$& $15$\\ $2$& $17$& $1$& $16$& $16$\\ $2$& $18$& $1$& $17$& $17$\\ $2$& $19$& $1$& $18$& $18$\\ $2$& $20$& $1$& $19$& $19$\\ $2$& $21$& $1$& $20$& $20$\\ $2$& $22$& $1$& $21$& $21$\\ $2$& $23$& $1$& $22$& $22$\\ $2$& $24$& $1$& $23$& $23$\\ $2$& $25$& $1$& $24$& $24$%\\ % \end{tabular}\hfil \begin{tabular}[t]{rrrrr} \multicolumn{1}{c}{$j$}& \multicolumn{1}{c}{$k$}& \multicolumn{1}{c}{$r$}& \multicolumn{1}{c}{$N$}& \multicolumn{1}{c}{$D$} \\\hline % $2$& $26$& $1$& $25$& $25$\\ $2$& $27$& $1$& $26$& $26$\\ $2$& $28$& $1$& $27$& $27$\\ $2$& $29$& $1$& $28$& $28$\\ $2$& $30$& $1$& $29$& $29$\\ $2$& $31$& $1$& $30$& $30$\\ $2$& $32$& $1$& $31$& $31$\\ $2$& $33$& $1$& $32$& $32$\\ $2$& $34$& $1$& $33$& $33$\\ $2$& $35$& $1$& $34$& $34$\\ $2$& $36$& $1$& $35$& $35$\\ $2$& $37$& $1$& $36$& $36$\\ $2$& $38$& $1$& $37$& $37$\\ $2$& $39$& $1$& $38$& $38$\\ $2$& $40$& $1$& $39$& $39$\\ $2$& $41$& $1$& $40$& $40$\\ $2$& $42$& $1$& $41$& $41$\\ $2$& $43$& $1$& $42$& $42$\\ $2$& $44$& $1$& $43$& $43$\\ $2$& $45$& $1$& $44$& $44$\\ $2$& $46$& $1$& $45$& $45$\\ $2$& $47$& $1$& $46$& $46$\\ $2$& $48$& $1$& $47$& $47$\\ $2$& $49$& $1$& $48$& $48$%\\ % \end{tabular}\hfil \begin{tabular}[t]{rrrrr} \multicolumn{1}{c}{$j$}& \multicolumn{1}{c}{$k$}& \multicolumn{1}{c}{$r$}& \multicolumn{1}{c}{$N$}& \multicolumn{1}{c}{$D$} \\\hline % $2$& $50$& $1$& $49$& $49$\\ $3$& $3$& $1$& $4$& $4$\\ $3$& $4$& $1$& $14$& $14$\\ $3$& $5$& $1$& $21$& $21$\\ $3$& $6$& $1$& $44$& $44$\\ $3$& $7$& $1$& $61$& $61$\\ $3$& $8$& $1$& $100$& $100$\\ $3$& $9$& $1$& $131$& $131$\\ $3$& $10$& $1$& $190$& $190$\\ $4$& $4$& $1$& $20$& $20$\\ $4$& $5$& $1$& $114$& $114$\\ $2$& $2$& $2$& $2$& $2$\\ $2$& $3$& $2$& $4$& $4$\\ $2$& $4$& $2$& $14$& $14$\\ $2$& $5$& $2$& $22$& $22$\\ $2$& $6$& $2$& $43$& $43$\\ $2$& $7$& $2$& $62$& $62$\\ $3$& $3$& $2$& $21$& $21$\\ $2$& $2$& $3$& $3$& $3$\\ $2$& $3$& $3$& $6$& $6$\\ $2$& $2$& $4$& $4$& $4$\\ $2$& $2$& $5$& $5$& $5$ \end{tabular}% } \caption[Numerator and denominator degrees]{The degrees, $N$ and $D$, of the numerator and denominator of the rational function for selected values of $j$, $k$, and $r$} \label{tab:degree} \end{table} \subsection{Observations from \texorpdfstring{$70$}{70} initial series} The generation of series is primarily limited by the symbolic computation of determinants of large matrices with many non-zero entries. For example, Maple 17 took $8$ hours to find the rational function for $j=2=k$ and $r=5$, a $252 \times 252$ matrix with about $5\%$ of its entries being non-zero. Let $\sum_n\NC_k^{\text{perm}} (n,r) x^n$ denote the ordinary generating function for the number of $k$-noncrossing, $r$-coloured permutations of $[n]$. \subsubsection{Noncrossing permutations} For $k=2$, and $r=1$, as noted in Table 2 of \citep{BuMiPo10}, $\NC_2^{\text{perm}}(n,1) = \dfrac1{n+1}\binom{2n}{n}$, the $n$th Catalan number, thus $\sum_n\NC_2^{\text{perm}} (n,1) x^n$ is algebraic. Let \[ \sum_n\NCN_{j,2}^{\text{perm}} (n,1) x^n = R_{j,2,1}(x) = \frac{P_{j,2,1}(x)}{Q_{j,2,1}(x)}. \] For $ 2 \le j \le 50$, $\deg P_{j,2,1}(x) = \deg Q_{j,2,1}(x) = j-1$. Moreover, all zeroes of $Q_{j,2,1}(x)$ are distinct positive reals with the smallest zero approaching $\frac14$ as $j$ increases. Recently, Chen~\citep{Chen14} proved the following for partitions. \begin{theorem} \[ \lim_{j \to\infty} \sum_n \NCN_{j,2}^{\text{part}} (n,1) x^n = \frac{1 - \sqrt{1-4x}}{2x}. \] \end{theorem} Though the adjacency matrix of permutations' $\mathcal{G}_{j,2,1}(\Sigma)$ differs from that of set partitions' $\mathcal{G}_{j,2,1}(\Pi)$ only by $1$ in the $(1,1)$th entry, except for the $(1,1)$th entry, we still have \[ \lim_{j \to \infty} R_{j,2,1}(x) = \frac{1 - \sqrt{1-4x}}{2x}. \] The sequence of rational functions $R_{j,2,1}$ approaching an algebraic function is an interesting phenomenon. \begin{conjecture} For $r=1$ and $j=2$, as $k$ increases, $Q_{2,k,1}(x) | Q_{2,mk,1}(x)$ for $m \in \mathbb{N}$. \end{conjecture} \begin{conjecture} For $j$ and $k$ fixed at $2$, as $r$ increases from $1$, the quotient of consecutive denominators of $R_{2,2,r}$ is \[ \frac{Q_{2,2,r}(x)}{Q_{2,2,r-1}(x)} = (1 - r(r+1) x), \quad \text{for} \quad r > 1. \] Furthermore, $\deg P_{2,2,r}(x) = \deg Q_{2,2,r}(x) = r$ for all $r \in \mathcal{N}$. \end{conjecture} Although the increase in degree in $P$ and $Q$ follows the same pattern as the first case, namely, nonnesting, $1$-coloured permutations, the zeroes of the $Q_{2,2,r}$ approach $0$ as $r$ increases. \begin{conjecture} For $j=2$, and $k = 3$, as $r$ increases from $1$, \[ \frac{Q_{2,3,r}(x)}{Q_{2,3,r-1}(x)} = \left(1 - \binom{2r}{2} x\right) \left(1- \binom{2r+1}{2}x\right), \quad \text{for} \quad r > 1. \] \end{conjecture} \subsubsection{A non-D-finite conjecture} For a fixed $j \ge 3$, $r=1$, as $k$ increases from $2$, $R_{j,k,1}$ grows in complexity unpredictably seen from degrees of numerator and denominator polynomials of $R$, further confirming the conjecture \citep{Mar12}: The ordinary generating series for $j$-noncrossing permutations is non-D-finite for $j \ge 3$. \subsection{Permutations of type \texorpdfstring{$B$}{B}} A \emph{type $B$} permutation, also a \emph{signed} permutation on $[n]$ is a permutation $\sigma$ of $\{ -n, \dots,$ $ -2, -1, 1, 2, \dots, n\}$ that satisfies $\sigma(-i) = -\sigma(i)$ for each $i \in [n]$. For example, we write $\sigma = (3, -5, 2, 4, -1)$ to mean \( \sigma= \left(\begin{smallmatrix} -5& -4& -3& -2& -1& 1 & 2 & 3 & 4 & 5 \\ 1& -4& -2& 5& -3& 3 & -5 & 2 & 4 & -1 \end{smallmatrix} \right) \) with an arc diagram representation: \begin{figure}[htp] \begin{center} \begin{tikzpicture}[scale=1] \foreach \i in {-5, -4, -3, -2, -1, 1, 2, 3, 4, 5} \node[pnt,label=below:$\i$] at (\i,0) (\i) {}; \draw[bend left=30](-5) to (1); \draw[bend left=45](-3) to (-2); \draw[bend left=30](-2) to (5); \draw[bend left=45](1) to (3); \draw[loop above] (-4) to (); \draw[loop above](4) to (); \draw[bend right=30](-5) to (2); \draw[bend right=30](-1) to (5); \draw[bend right=55](-3) to (-1); \draw[bend right=45](2) to (3); \end{tikzpicture} \end{center} \end{figure} Hamdi~\citep{Ham11} extended Corteel's result~\citep{Corteel07} on symmetric joint distribution of crossings and nestings for permutations to signed permutations. A signed permutation like $\sigma$ above can be drawn as a $2$-coloured permutation where arcs of colour $1$ (resp.\ colour $2$) connect elements of the same (resp.\ opposite) sign. For example, a $2$-coloured arc diagram representation of $\sigma = (3, -5, 2, 4, -1)$ is shown in Figure~\ref{fig:Bperm}. \begin{figure}[htp] \centering \begin{tikzpicture}[scale=1] \foreach \i in { 1, 2, 3, 4, 5} \node[pnt,label=below:$\i$] at (\i,0) (\i) {}; \draw[bend left=45](1) to node[pos=0.2,above]{$\scriptstyle1$} (3); \draw[loop above](4) to node[pos=0.2, left]{$\scriptstyle1$} (); \draw[bend left=45](2) to node[pos=0.4,above]{$\scriptstyle2$} (5); \draw[bend right=45](1) to node[pos=0.4,below]{$\scriptstyle2$}(5); \draw[bend right=45](2) to node[pos=0.5, above]{$\scriptstyle1$} (3); \end{tikzpicture} \caption{A $2$-coloured arc diagram of $\sigma = (3, -5, 2, 4, -1)$} \label{fig:Bperm} \end{figure} This bijection mapping between the set of type $B$ permutations on $[n]$ and $2$-coloured permutations on $[n]$ does not transfer results of symmetric joint distribution for crossings and nestings; rather, $2$-coloured arc diagrams of type $B$ permutations differentiate crossings and nestings between same-signed and opposite-signed elements. \section{Concluding Remarks} When both nesting and crossing numbers are bounded, a finite multigraph can be constructed, leading to a rational generating series. The method of transfer matrix may be extended to the enumeration of set partitions of classical types as in the works of \citet{RuSt10}, even their coloured counterparts. The challenge lies in finding the generating function when only one of the bounds is present. For instance, \citet{Mar12} showed that the ordinary generating function for noncrossing $2$-coloured set partitions is D-finite, but conjectured non-D-finite series for noncrossing $r$-coloured set partitions when $r \ge 3$. Experimental data shows that noncrossing $2$-coloured permutations have unpredictable complexity for the rational functions, thus placing the series in the non-D-finite category. The automation of generating series for coloured set partitions and permutations of arbitrarily fixed nesting and crossing numbers opens a new window into the classification of series. As one of the parameters increases, a sequence of rational functions emerges with a myriad of patterns to understand. See~\citet{Chen14} for examples of such results. Since crossing and nesting numbers are bounded in biological models, specific series also open the door to random generations for topological structural studies of secondary RNA's (coloured set partitions~\citep{clote2012page}) and genome rearrangement problems (coloured permutations). \section{Acknowledgements} The author would like to thank Marni Mishna for recommending Marberg's paper~\citep{Mar12}, Eric Marberg for clarifying the construction of the matrices which act as vertex labels of the multigraph $\mathcal{G}_{j,k,r}$, Cedric Chauve for the reference on genome rearrangements~\citep{Fertin09}, and Michael Monagan for computing large rational series for coloured permutations. Mogens Lemvig Hansen helped with figures, tables, and Maple code \citep{Yen12colour} for the automation. Finally, comments from an anonymous referee resulted in a denser presentation of the beginning sections. \bibliographystyle{plainnat} %\bibliography{../main} \begin{thebibliography}{19} \providecommand{\natexlab}[1]{#1} \providecommand{\url}[1]{\texttt{#1}} \expandafter\ifx\csname urlstyle\endcsname\relax \providecommand{\doi}[1]{doi: #1}\else \providecommand{\doi}{doi: \begingroup \urlstyle{rm}\Url}\fi \bibitem[Borodin(1999)]{Borodin99} Alexei Borodin. \newblock Longest increasing subsequences of random colored permutations. \newblock \emph{Electron. J. Combin.}, 6\penalty0 (1):\penalty0 R13, February 1999. \bibitem[Burrill et~al.(2010)Burrill, Mishna, and Post]{BuMiPo10} Sophie Burrill, Marni Mishna, and Jacob Post. \newblock On {$k$}-crossings and {$k$}-nestings of permutations. \newblock In \emph{Proceedings of 22nd International Conference on Formal Power Series and Algebraic Combinatorics}, pages 593--600, San Francisco, CA, USA, 2010. \bibitem[Chen(2014)]{Chen14} Wei Chen. \newblock Crossings and nestings enumeration for set partitions. \newblock Master's thesis, Simon Fraser University, December 2014. \bibitem[Chen and Guo(2011)]{ChG11} William Y.~C. Chen and P.~L. Guo. \newblock Oscillating rim hook tableaux and colored matchings. \newblock \emph{Adv. in Appl. Math.}, 48\penalty0 (2):\penalty0 393--406, 2011. \bibitem[Chen et~al.(2007)Chen, Deng, Du, Stanley, and Yan]{Chetal07} William Y.~C. Chen, Eva Y.~P. Deng, Rosena R.~X. Du, Richard~P. Stanley, and Catherine~H. Yan. \newblock Crossings and nestings of matchings and partitions. \newblock \emph{Trans. Amer. Math. Soc.}, 359\penalty0 (4):\penalty0 1555--1575 (electronic), 2007. \newblock ISSN 0002-9947. \bibitem[Clote et~al.(2012)Clote, Dobrev, Dotu, Kranakis, Krizanc, and Urrutia]{clote2012page} Peter Clote, Stefan Dobrev, Ivan Dotu, Evangelos Kranakis, Danny Krizanc, and Jorge Urrutia. \newblock On the page number of {RNA} secondary structures with pseudoknots. \newblock \emph{J. Math. Biol.}, 65\penalty0 (6-7):\penalty0 1337--1357, 2012. \bibitem[Corteel(2007)]{Corteel07} Sylvie Corteel. \newblock Crossings and alignments of permutations. \newblock \emph{Adv. in Appl. Math.}, 38\penalty0 (2):\penalty0 149--163, 2007. \newblock ISSN 0196-8858. \bibitem[de~Mier(2007)]{deMi07} Anna de~Mier. \newblock {$k$}-noncrossing and {$k$}-nonnesting graphs and fillings of {F}errers diagrams. \newblock \emph{Combinatorica}, 27\penalty0 (6):\penalty0 699--720, 2007. \newblock ISSN 0209-9683. \bibitem[Duchon et~al.(2004)Duchon, Flajolet, Louchard, and Schaeffer]{DFLS04} Philippe Duchon, Philippe Flajolet, Guy Louchard, and Gilles Schaeffer. \newblock Boltzmann samplers for the random generation of combinatorial structures. \newblock \emph{Combinatorics, Probability and Computing}, 13:\penalty0 577--625, 2004. \bibitem[Fertin et~al.(2009)Fertin, Labarre, Rusu, Tannier, and Vialette]{Fertin09} Guillaume Fertin, Anthony Labarre, Irena Rusu, {\'E}ric Tannier, and St{\'e}phane Vialette. \newblock \emph{Combinatorics of Genome Rearrangements}. \newblock The MIT Press, Cambridge, Massachusetts, 2009. \newblock ISBN 978-0-262-06282-4. \bibitem[Gouyou-Beauchamps(1989)]{GB89} Dominique Gouyou-Beauchamps. \newblock Standard {Y}oung tableaux of height {$4$} and {$5$}. \newblock \emph{European Journal of Combinatorics}, 10:\penalty0 69--82, 1989. \bibitem[Hamdi(2011)]{Ham11} Adel Hamdi. \newblock Symmetric distribution of crossings and nestings in permutations of type {$B$}. \newblock \emph{Electron. J. Combin.}, 18\penalty0 (1):\penalty0 P200, October 2011. \bibitem[Krattenthaler(2006)]{Kratt06} Christian Krattenthaler. \newblock Growth diagrams, and increasing and decreasing chains in fillings of {F}errers shapes. \newblock \emph{Adv. in Appl. Math.}, 37\penalty0 (3):\penalty0 404--431, 2006. \newblock ISSN 0196-8858. \bibitem[Marberg(2013)]{Mar12} Eric Marberg. \newblock Crossings and nestings in colored set partitions. \newblock \emph{Electron. J. Combin.}, 20\penalty0 (4), October 2013. \bibitem[{OEIS Foundation Inc.}(2011)]{oeis} {OEIS Foundation Inc.} \newblock \emph{The On-Line Encyclopedia of Integer Sequences}. \newblock Published electronically at http://oeis.org, 2011. \bibitem[Rubey and Stump(2010)]{RuSt10} Martin Rubey and Christian Stump. \newblock Crossings and nestings in set partitions of classical types. \newblock \emph{Electron. J. Combin.}, 17\penalty0 (1):\penalty0 R120, September 2010. \bibitem[Stanley(1999)]{Stanley99} Richard~P. Stanley. \newblock \emph{Enumerative Combinatorics}, volume~2. \newblock Cambridge University Press, 1999. \bibitem[Stump(2014)]{Stump12} Christian Stump. \newblock More bijective {Catalan} combinatorics on permutations and on signed permutations. \newblock \emph{J. Comb.}, 4\penalty0 (4), 2014. \bibitem[Yen(2012)]{Yen12colour} Lily Yen. \newblock Crossings and nestings for arc-coloured permutations. \newblock \emph{Preprint}, November 2012. \newblock URL \url{http://arxiv.org/abs/1211.3472}. \end{thebibliography} \end{document}