\documentclass[final]{FPSAC2022} 
\usepackage{graphicx} 
\usepackage{ytableau}
\usepackage{float} 
\floatstyle{ruled}
\newfloat{Algorithm}{htbp}{algo}
\usepackage{pgf,tikz}
\usetikzlibrary{calc}
\usetikzlibrary{arrows, automata}
\usepackage{subcaption}
\usepackage{xcolor}
\usepackage{url}
\captionsetup[subfigure]{labelformat=parens,labelsep=space}   % Change this most likely
%\usepackage{hyperref}   
%\allowdisplaybreaks[1]
\theoremstyle{plain}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}[lemma]{Corollary}
\newtheorem{theorem}[lemma]{Theorem}
\newtheorem{proposition}[lemma]{Proposition}
\newtheorem*{theorema}{Theorem A}
\newtheorem*{theoremb}{Theorem B}
\theoremstyle{remark}
\newtheorem{example}[lemma]{Example}
\newtheorem{remark}[lemma]{Remark}
\theoremstyle{definition}
\newtheorem{definition}[lemma]{Definition}  
\numberwithin{lemma}{section}
\numberwithin{equation}{section}

\renewcommand\subset{\subseteq}
\renewcommand\supset{\supseteq}  
\renewcommand\AA{\mathcal{A}}
\newcommand\arc{\mathrm{arc}}
\newcommand\diag{\mathrm{diag}}
\newcommand{\nat}{\mathbf P}
\newcommand\nn{\mathbf N}
\newcommand\syt{\mathrm{SYT}}  
\newcommand\Fq{\mathbf F_q}
\newcommand\psp{\Pi^{\mathrm{par}}}
\newcommand\supp{\mathrm{supp}}
\newcommand\T{\mathcal T}
\newcommand\Tab{\mathrm{Tab}}
\newcommand\stab{\mathrm{sTab}}
\newcommand{\ZZ}{\mathbf Z}

\DeclareMathOperator\rank{rank}

\title[Set Partitions, Tableaux, and Profiles]{Set Partitions, Tableaux, and Subspace Profiles of Regular Diagonal Operators}

\author[A.~Prasad \and S.~Ram]{Amritanshu Prasad\addressmark{1,2} \and Samrith Ram\thanks{\href{mailto:samrith@iiitd.ac.in}{samrith@iiitd.ac.in}}\addressmark{3}} 

\address{\addressmark{1}The Institute of Mathematical Sciences, Chennai\\ \addressmark{2} Homi Bhabha National Institute, Mumbai \\ \addressmark{3}Department of Mathematics, Indraprastha Institute of Information Technology Delhi}

\received{\today}

\abstract{We introduce a family of univariate polynomials indexed by integer partitions. At prime powers, they count the number of subspaces in a finite vector space that transform under a regular diagonal matrix in a specified manner. At 1, they count set partitions with specified block sizes. At 0, they count standard tableaux of specified shape. At $-1$, they count standard shifted tableaux of a specified shape. These polynomials are generated by a new statistic on set partitions (called the interlacing number) as well as a polynomial statistic on standard tableaux. They allow us to express $q$-Stirling numbers of the second kind as sums over standard tableaux and as sums over set partitions. In a special case these polynomials coincide with those defined by Touchard in his study of crossings of chord diagrams. }  

\keywords{subspace dynamics, split semisimple operator, interlacing, chord diagram, $q$-Stirling number, crossing}  
\addbibresource{fpsac.bib}      
\begin{document}

\maketitle

\section{Introduction} 
\label{sec:introduction}
Let $\Fq$ denote a finite field with $q$ elements. Let $\Delta$ be a linear operator on $\Fq^n$.
\begin{definition}
  \label{definition:profile}
  A subspace $W\subset \Fq^n$ is said to have partial $\Delta$-profile $\mu=(\mu_1,\ldots,\mu_k)$ if 

  \begin{displaymath}
    \dim (W + \Delta W + \dotsb + \Delta^{j-1}W) = \mu_1+\dotsb+\mu_j \text{ for } 1\leq j\leq k.
  \end{displaymath}
Furthermore, if 
  \begin{displaymath}
    \dim (W + \Delta W + \dotsb + \Delta^{k-1}W) =   \dim (W + \Delta W + \dotsb + \Delta^kW),
  \end{displaymath}
  then we say that $W$ has $\Delta$-profile $\mu$.
\end{definition}

For example, an $m$-dimensional $\Delta$-invariant subspace is one with profile $(m)$ while a subspace spanned by a $\Delta$-cyclic vector has profile $(1^n)$. It is easy to show that $\mu_j\geq \mu_{j+1}$ for all $j$, and so $\mu$ is a partition of some integer less than or equal to $n$. 


Let $\sigma_n(\mu)$ denote the number of subspaces with $\Delta$-profile $\mu$.
Using techniques of Chen and Tseng \cite{sscffa} it can be shown that $\sigma_n(\mu)$ is a polynomial in $q$ that depends only on the similarity class type of $\Delta$.    
We focus on the case where $\Delta$ has $n$ distinct eigenvalues in $\Fq$.
Thus $\Delta$ is represented by a diagonal matrix with distinct entries on its diagonal.

In Section~\ref{sec:polyn-b_lambd} we introduce a family of polynomials $b_\lambda(q)$ indexed by integer partitions such that (see Theorem~\ref{theorem:counting-profile})
\begin{equation}
  \label{eq:sigmu}
 \sigma_n(\mu) = {n \choose |\mu|}(q-1)^{\sum_{j\geq 2}\mu_j}q^{\sum_{j\geq 2}\binom{\mu_j}2}b_{\mu'}(q),
\end{equation}
where $\mu'$ denotes the partition conjugate to $\mu$. The polynomial $b_\lambda(q)$ is a sum over $\Tab_{[n]}(\lambda)$, the set of standard tableaux of shape $\lambda$:

\begin{displaymath}
  b_\lambda(q) = \sum_{T\in \Tab_{[n]}(\lambda)} c_q(T),
\end{displaymath}
where $c_q(T)$ is a polynomial associated to each standard tableau $T$ of size $n$.
The polynomial $c_q$ arises out of a surprising new connection between two classical combinatorial classes, namely set partitions and standard tableaux.
In Section~\ref{sec:tabl-assoc-set} we associate a standard tableau to each partition of the set $[n]=\{1,\dotsc,n\}$.
Set partitions that map to a given tableau are counted by a statistic $c$ on standard tableaux.
A naive substitution of certain integers that occur in the definition of $c$ (see Equation~\eqref{eq:c}) by the corresponding $q$-integers leads to $c_q$.


In Section~\ref{sec:interl-stat}, we introduce a statistic on set partitions called the interlacing number. Although defined in the spirit of the well-known crossing number of a set partition (see, for example, \cite{MR2272140}) these numbers coincide only in certain very special cases, an interesting case being that of chord diagrams (see Section \ref{sec:chord}). We show that the polynomial $c_q(T)$ is the generating polynomial of the interlacing statistic on the class of set partitions associated to the tableau $T$ (Theorem~\ref{theorem:statistic}). Moreover, noninterlacing set partitions of shape $\lambda$ are in bijection with standard tableaux of shape $\lambda$ (see Corollary \ref{cor:noninterl}).


In Section~\ref{sec:minusone} we show that $b_\lambda(-1)$ counts the number of standard shifted tableaux of shape $\lambda$ for a certain class of partitions.

To summarize, the polynomials $b_\lambda(q)$ have the following specializations:
\begin{enumerate}
\item When $q$ is a prime power, they count subspaces of $\Fq^n$ with profile $\lambda'$, up to a factor of the form $q^a(q-1)^b$ (Equation~\eqref{eq:sigmu}). 
\item When $q=1$, they count partitions of $[n]$ with block sizes given by the parts of $\lambda$ (Equation~\eqref{eq:bla1}). 
\item When $q=0$, they count standard tableaux of shape $\lambda$ and also the number of noninterlacing set partitions of shape $\lambda$ (Equations~\eqref{eq:bla0} and~\eqref{eq:blamset}). 

\item When $q=-1$ and the parts of $\lambda$ are distinct, with the possible exception of the largest part, they count standard shifted tableaux of shape $\lambda$ (Theorem \ref{theorem:minusone}). 
\end{enumerate}


We express the $q$-Stirling numbers of the second kind in terms of the polynomials $b_\lambda(q)$, as sums over standard tableaux, and as sums over set partitions:
\begin{align}
  S_q(n,m) &= \sum_{\lambda\vdash n,\;l(\lambda)=m} q^{\sum_i(i-1)(\lambda_i-1)}b_\lambda(q), \label{eq:qst1}\\
    S_q(n,m)&= \sum_{\lambda \vdash n,\;l(\lambda)=m}q^{\sum_i (i-1)(\lambda_i-1)}\sum_{T\in \Tab_{[n]}(\lambda)} c_q(T), \label{eq:qst2}\\
  S_q(n,m) &= \sum_{\AA\in \Pi_{n,m}} q^{v(\AA)+\sum_i(i-1)(\lambda_i^\AA-1)}.    \label{eq:qst3}
\end{align} 

Here $\Pi_{n,m}$ denotes the collection of partitions of $[n]$ having $m$ blocks, $(\lambda_1^\AA,\lambda_2^\AA,\ldots)$ is the list of block sizes of $\AA$ sorted in weakly decreasing order, and $v(\AA)$ is the interlacing number of $\AA$.
  Many statistics on set partitions are known to produce the $q$-Stirling numbers of the second kind  \cite{CAI201750,MR834272,MR1082841}. Our statistic appears to be different from all of these. Cai and Readdy \cite[Theorem~3.2]{CAI201750} express $S_q(n,m)$ as a sum of expressions of the form $q^a(q+1)^b$ over a small class of set partitions. In this vein, we also express $S_q(n,m)$ as a sum over noninterlacing set partitions but in our case the summands are powers of $q$ times a product of $q$-integers:    
  \begin{equation*}
  \label{eq:qs4}
S_q(n,m)=\sum_{ \substack{\AA\in\Pi_{n,m}\\v(\AA)=0}}q^{\sum_i (i-1)(\lambda_i-1)}c_q(\T(\AA)).  
\end{equation*}
 
Combining equations \eqref{eq:sigmu}  and \eqref{eq:qst1} allows for a bijective interpretation of an identity of Carlitz \cite[Equation~(8)]{MR1501675} (see also \cite[Equation~(3.4)]{MR27288}) that expresses $q$-binomial coefficients in terms of $q$-Stirling numbers of the second kind:
  $$
{n \brack m}_q=\sum_{r=m}^n (q-1)^{r-m}{n \choose r}S_q(r,m).
  $$
The left hand side counts all $m$-dimensional subspaces of $\Fq^n$ while the right hand is obtained by counting subspaces by their $\Delta$-profile. At $q=1$, the identity \eqref{eq:qst2} gives an expression for the Stirling numbers of the second kind as the sum of a statistic on standard tableaux which appears to be new. A similar identity holds for the Bell numbers.
 
If $m$ divides $n$, say $n=md$, then a $\Delta$-splitting subspace of $\Fq^n$ is a subspace $W$ of dimension $m$ such that
$$
W\oplus \Delta W\oplus \cdots\oplus \Delta^{d-1}W=\Fq^n.
$$
Thus an $m$-dimensional splitting subspace is a subspace of $\Fq^n$ with $\Delta$-profile $(m^d)$. The definition of a splitting subspace can be traced back to the work of Niederreiter \cite{N2} on pseudorandom number generation. Determining the number of $m$-dimensional $\Delta$-splitting subspaces for an arbitrary operator $\Delta$ is an open problem \cite[page~54]{MR2961399}. 
The answer is known in the cases where $\Delta$ has an irreducible characteristic polynomial \cite{MR4263652,sscffa,m=2}, $\Delta$ is nilpotent \cite{agram2022}, or when the invariant factors of $\Delta$ satisfy certain degree constraints~\cite{polynomialmatrices}.  

In the case where $\Delta$ has $n$ distinct eigenvalues in $\Fq$, Equation~\eqref{eq:sigmu} gives the number of splitting subspaces of dimension $m$ when $\mu=(m^d)$. The case $d=2$ is of particular interest; we find that it is associated with the study of crossings of chord diagrams that were extensively investigated by Touchard (see Section~\ref{sec:chord}).

Detailed proofs can be found in \cite{pr}. We extensively used \SageMath~\cite{sagemath} for computations. Code for demonstrating the results in this paper is available online at \newline \href{https://www.imsc.res.in/~amri/set_partitions}{https://www.imsc.res.in/$\sim$amri/set\_partitions}.  
   
  
\section{Set Partitions} 
\label{sec:set-partitions}
\subsection{Set partitions and standard notation}             
Let $S$ be a finite subset of the set $\nat$ of positive integers.
A partition $\AA = \{A_1,\ldots,A_m\}$ of $S$ is a decomposition
\begin{displaymath}
  S = A_1\cup \dotsb \cup A_m,
\end{displaymath}
where $A_1,\dotsc,A_m$ are pairwise disjoint non-empty subsets of $S$.
The subsets $A_1,\dotsc,A_m$ are called the \emph{blocks} of $\AA$.
The order of the blocks  does not matter.
Following standard conventions \cite[\S~2.7.1.5]{TACOP4A}, the elements of each block are listed in increasing order, and the blocks are listed in increasing order of their least elements.
When this is the case, we write $\AA=A_1|\dotsb|A_m$, which we call \emph{the standard notation} for $\AA$.
The shape of a set partition is the list of cardinalities of $A_1,\dotsc,A_m$, sorted in weakly decreasing order.
Thus the shape of a partition of $S$ is an integer partition of $|S|$.
Denote the set of all partitions of $S$ by $\Pi_S$, and the set of all partitions of $S$ with shape $\lambda$ by $\Pi_S(\lambda)$.

\subsection{The tableau associated to a set partition}
\label{sec:tabl-assoc-set}

\begin{definition}
  \label{defn:T}
  Given $\AA=A_1|\dotsb|A_m\in \Pi_S$, form an array whose entry in the $i$th row and $j$th column is the $j$th smallest element of $A_i$.
  Then sort and top-justify the columns of this array.
  Denote the resulting tableau by $\T(\AA)$.
\end{definition}
\begin{example}\label{example:partition-tableau}
  When $\AA = 12|389|56$, the associated array and the corresponding tableau $\T(\AA)$ are 
  \begin{displaymath}
    \ytableaushort{12\none,389,5 6 \none}\quad \mbox{ and } \quad
    \ytableaushort{129,36,58}\,.
  \end{displaymath}
\end{example}
\begin{definition}
  A tableau $T$ is called a \emph{multilinear tableau} if each element of $\nat$ occurs at most once in $T$, the rows of $T$ increase from left to right, and the columns of $T$ increase from top to bottom.

  The set of integers that occur in $T$ is called the support of $T$, and is denoted $\supp(T)$. For each $S\subset \nat$, let $\Tab_S$ denote the set of multilinear tableaux with support $S$. For each integer partition $\lambda$, denote the set of multilinear tableaux of shape $\lambda$ and support $S$ by $\Tab_S(\lambda)$. Let $\Tab_{\subset S}(\lambda)$ denote the set of multilinear tableaux of shape $\lambda$ whose support is a subset of $S$.
  The usual notion of a standard Young tableau coincides with that of a multilinear tableau with support $[n]$ for some $n\geq 0$.
\end{definition}

\begin{example}
  The tableau in Example~\ref{example:partition-tableau} is a multilinear tableau of shape $(3,2,2)$ and support $\{1,2,3,5,6,8,9\}$.
\end{example}


It can be shown that Definition~\ref{defn:T} gives rise to a surjective function
\begin{displaymath}
  \T \colon \Pi_S(\lambda) \to \Tab_S(\lambda).
\end{displaymath}
To see surjectivity, given $T\in \Tab_S(\lambda)$ simply take $\AA$ to be the partition of $S$ whose blocks are the rows of $T$.
Then $\T(\AA)=T$.
For each $T\in \Tab_S(\lambda)$, let
\begin{displaymath}
  \Pi(T) = \{\AA\in \Pi_S(\lambda) \mid \T(\AA)=T\},
\end{displaymath}
the fibre of $\T$ over $T$.
Our next goal is to understand the set $\Pi(T)$ for each multilinear tableau $T$.
\begin{example}
  \label{example:tableau}
  When $T=\ytableaushort{129,36,58}$\,, the set partitions in $\Pi(T)$ are
  \begin{displaymath}
    129|38|56,\; 129|36|58,\; 12|369|58,\; 12|38|569,\; 12|36|589,\; 12|389|56.
  \end{displaymath}
\end{example}
\subsection{Set partitions associated to a given tableau}
Suppose that $S\subset \nat$ is finite, and $\lambda$ is an integer partition of $|S|$.
\ytableausetup{smalltableaux}
\begin{definition}
  Let $T$ be a multilinear tableau of shape $\lambda=(\lambda_1,\dotsc,\lambda_m)$.
  For $1\leq i\leq m$ and $2\leq j\leq \lambda_i$ define
  \begin{displaymath}
    c_{ij}(T) = \#\{i'\mid i'\geq i \mbox{ and } T_{i',j-1}<T_{ij}\}.
  \end{displaymath}
  Define
  \begin{equation}
    \label{eq:c}
    c(T) = \prod_{i=1}^m \prod_{j=2}^{\lambda_i} c_{ij}(T).
  \end{equation}
\end{definition}
\begin{example}
  For the tableau $T$ of Example~\ref{example:tableau}, the values of $c_{ij}(T)$ for each relevant cell are shown below:
  \ytableausetup{nosmalltableaux}
  \begin{displaymath}
    \ytableaushort{{}13,{}2,{}1}\,,
  \end{displaymath}
  and $c(T)=6$.
\end{example}
\begin{theorem}
  \label{theorem:fibres}
  For every multilinear tableau $T$, the cardinality of $\Pi(T)$ is $c(T)$.
\end{theorem}

 
\section{$q$-analogs}
\subsection{A $q$-analog of $c(T)$}
For each multilinear tableau $T$ of shape $\lambda=(\lambda_1,\dotsc,\lambda_m)$, define $c_q(T)\in \ZZ[q]$ by
\begin{equation}
  \label{eq:rq}
  c_q(T) = \prod_{i=1}^m \prod_{j=2}^{\lambda_i} [c_{ij}(T)]_q,
\end{equation}
where, for each positive integer $n$, $[n]_q=1+q+\dotsb+q^{n-1}$, the $q$-analog of $n$.
Clearly $c_q(T)$ is a polynomial with nonnegative integer coefficients, and substituting $q=1$ gives
\begin{displaymath}
  c_q(T)|_{q=1} = c(T),
\end{displaymath}
the cardinality of $\Pi(T)$.
\subsection{The polynomials $b_\lambda(q)$}
\label{sec:polyn-b_lambd}
For each integer partition $\lambda$ and each positive integer $n$, define
\begin{equation}
  \label{eq:bla}
  b_\lambda^n(q) = \sum_{T\in \Tab_{\subset [n]}(\lambda)} c_q(T).
\end{equation}
Write $b_\lambda(q)$ for $b_\lambda^n(q)$ when $\lambda$ is a partition of $n$. Any order-preserving relabeling of the entries of $T$ leaves $c_q(T)$ invariant. Therefore, for any $\lambda$ and any $n,$
$$
b_\lambda^n(q)={n \choose |\lambda|}b_\lambda(q).
$$
It follows from Theorem ~\ref{theorem:fibres} that
\begin{equation}
  \label{eq:bla1}
  b_\lambda(1) = |\Pi_{[n]}(\lambda)|,
\end{equation}
the number of set partitions of $[n]$ of shape $\lambda$. Since, for every standard tableau $T,$ $b_\lambda(q)$ is a product of $q$-integers, we have
\begin{equation}
  \label{eq:bla0}
  b_\lambda(0) = |\Tab_{[n]}(\lambda)|.
\end{equation}
\subsection{The interlacing statistic}
\label{sec:interl-stat}
Let $\nat^*$ denote the ordered set $\nat \cup \{\infty\}$, where $\infty$ is deemed to be greater than every element of $\nat$.
\begin{definition}[Crossing arcs]
  For $a,b,c,d\in \nat^*$, we say that the arcs $(a,b)$ and $(c,d)$ cross if the intervals $[a,b]$ and $[c,d]$ are neither nested, nor disjoint.
  In other words:
  \begin{gather*}
    \text{either } a<c<b<d \text{ or } c<a<d<b.
  \end{gather*}
\end{definition}

\begin{definition}
  [The arcs of a set]
  Given a set $A\subset \nat$ whose elements are $a_1,\dotsc,a_l$ in increasing order, its $j$th arc is the pair $\arc_j(A) = (a_j,a_{j+1})$ for $j=1,\dotsc,l-1$, and its $l$th arc is $\arc_l(A) = (a_l,\infty)$.
\end{definition}
\begin{definition}[Interlacing]
  \label{definition:interlacing}
  Let $S$ be any finite subset of $\nat$.
  Let $\AA = A_1|\dotsb|A_m\in \Pi_S$ with $|A_i|=l_i$.
  An \emph{interlacing} of $\AA$ is a pair $(\arc_j(A_i)$, $\arc_j(A_{i'}))$ of crossing arcs  for some $1\leq i<i'\leq m$ and some $1\leq j\leq \min(l_i,l_{i'})$.
  Let $v(\AA)$ denote the total number of interlacings of the set partition $\AA$, called the \emph{interlacing number} of $\AA$.
\end{definition}

\begin{table}
  \begin{center}
    \begin{tabular}{ccc}
      $\AA$ & Arcs of $\AA$ & $v(\AA)$\\
      \hline
      $129|38|56$ & 
                    \begin{minipage}{0.75\textwidth}
                      \begin{tikzpicture}
                        [scale=0.9,every node/.style={circle,fill=black}]
                        \node[label=below:$1$] (1) at (1,0) {};
                        \node[label=below:$2$] (2) at (2,0) {};
                        \node[label=below:$3$] (3) at (3,0) {};
                        \node[label=below:$5$] (5) at (5,0) {};
                        \node[label=below:$6$] (6) at (6,0) {};
                        \node[label=below:$8$] (8) at (8,0) {};
                        \node[label=below:$9$] (9) at (9,0) {};
                        \node[label=below:$\infty$] (0) at (10,0) {};
                        \draw[thick,color=teal]
                        (1) [out=45, in=135] to  (2);
                        \draw[thick,color=orange]
                        (2) [out=45, in=135] to  (9);
                        \draw[thick,color=teal]
                        (3) [out=45, in=135] to  (8);
                        \draw[thick,color=teal]
                        (5) [out=45, in=135] to  (6);
                        \draw[thick,color=orange]
                        (6) [out=45, in=135] to  (0);
                        \draw[thick,color=orange]
                        (8) [out=45, in=135] to  (0);
                        \draw[thick,color=blue]
                        (9) [out=45, in=135] to  (0);
                      \end{tikzpicture}
                    \end{minipage}
                            &  2\\
      $129|36|58$&
                   \begin{minipage}{0.75\textwidth}
                     \begin{tikzpicture}
                       [scale=0.9,every node/.style={circle,fill=black}]
                       \node[label=below:$1$] (1) at (1,0) {};
                       \node[label=below:$2$] (2) at (2,0) {};
                       \node[label=below:$3$] (3) at (3,0) {};
                       \node[label=below:$5$] (5) at (5,0) {};
                       \node[label=below:$6$] (6) at (6,0) {};
                       \node[label=below:$8$] (8) at (8,0) {};
                       \node[label=below:$9$] (9) at (9,0) {};
                       \node[label=below:$\infty$] (0) at (10,0) {};
                       \draw[thick,color=teal]
                       (1) [out=45, in=135] to  (2);
                       \draw[thick,color=orange]
                       (2) [out=45, in=135] to  (9);
                       \draw[thick,color=teal]
                       (3) [out=45, in=135] to  (6);
                       \draw[thick,color=teal]
                       (5) [out=45, in=135] to  (8);
                       \draw[thick,color=orange]
                       (6) [out=45, in=135] to  (0);
                       \draw[thick,color=orange]
                       (8) [out=45, in=135] to  (0);
                       \draw[thick,color=blue]
                       (9) [out=45, in=135] to  (0);
                     \end{tikzpicture}
                   \end{minipage}
                            & $3$\\
      $12|369|58$ &
                    \begin{minipage}{0.75\textwidth}
                      \begin{tikzpicture}
                        [scale=0.9,every node/.style={circle,fill=black}]
                        \node[label=below:$1$] (1) at (1,0) {};
                        \node[label=below:$2$] (2) at (2,0) {};
                        \node[label=below:$3$] (3) at (3,0) {};
                        \node[label=below:$5$] (5) at (5,0) {};
                        \node[label=below:$6$] (6) at (6,0) {};
                        \node[label=below:$8$] (8) at (8,0) {};
                        \node[label=below:$9$] (9) at (9,0) {};
                        \node[label=below:$\infty$] (0) at (10,0) {};
                        \draw[thick,color=teal]
                        (1) [out=45, in=135] to  (2);
                        \draw[thick,color=teal]
                        (3) [out=45, in=135] to  (6);
                        \draw[thick,color=orange]
                        (6) [out=45, in=135] to  (9);
                        \draw[thick,color=teal]
                        (5) [out=45, in=135] to  (8);
                        \draw[thick,color=orange]
                        (2) [out=45, in=135] to  (0);
                        \draw[thick,color=orange]
                        (8) [out=45, in=135] to  (0);
                        \draw[thick,color=blue]
                        (9) [out=45, in=135] to  (0);
                      \end{tikzpicture}
                    \end{minipage}
                            & $2$\\
      $12|38|569$&
                   \begin{minipage}{0.75\textwidth}
                     \begin{tikzpicture}
                       [scale=0.9,every node/.style={circle,fill=black}]
                       \node[label=below:$1$] (1) at (1,0) {};
                       \node[label=below:$2$] (2) at (2,0) {};
                       \node[label=below:$3$] (3) at (3,0) {};
                       \node[label=below:$5$] (5) at (5,0) {};
                       \node[label=below:$6$] (6) at (6,0) {};
                       \node[label=below:$8$] (8) at (8,0) {};
                       \node[label=below:$9$] (9) at (9,0) {};
                       \node[label=below:$\infty$] (0) at (10,0) {};
                       \draw[thick,color=teal]
                       (1) [out=45, in=135] to  (2);
                       \draw[thick,color=teal]
                       (5) [out=45, in=135] to  (6);
                       \draw[thick,color=orange]
                       (6) [out=45, in=135] to  (9);
                       \draw[thick,color=teal]
                       (3) [out=45, in=135] to  (8);
                       \draw[thick,color=orange]
                       (2) [out=45, in=135] to  (0);
                       \draw[thick,color=orange]
                       (8) [out=45, in=135] to  (0);
                       \draw[thick,color=blue]
                       (9) [out=45, in=135] to  (0);
                     \end{tikzpicture}
                   \end{minipage}
                            & $1$\\
      $12|36|589$ &
                    \begin{minipage}{0.75\textwidth}
                      \begin{tikzpicture}
                        [scale=0.9,every node/.style={circle,fill=black}]
                        \node[label=below:$1$] (1) at (1,0) {};
                        \node[label=below:$2$] (2) at (2,0) {};
                        \node[label=below:$3$] (3) at (3,0) {};
                        \node[label=below:$5$] (5) at (5,0) {};
                        \node[label=below:$6$] (6) at (6,0) {};
                        \node[label=below:$8$] (8) at (8,0) {};
                        \node[label=below:$9$] (9) at (9,0) {};
                        \node[label=below:$\infty$] (0) at (10,0) {};
                        \draw[thick,color=teal]
                        (1) [out=45, in=135] to  (2);
                        \draw[thick,color=teal]
                        (3) [out=45, in=135] to  (6);
                        \draw[thick,color=orange]
                        (8) [out=45, in=135] to  (9);
                        \draw[thick,color=teal]
                        (5) [out=45, in=135] to  (8);
                        \draw[thick,color=orange]
                        (2) [out=45, in=135] to  (0);
                        \draw[thick,color=orange]
                        (6) [out=45, in=135] to  (0);
                        \draw[thick,color=blue]
                        (9) [out=45, in=135] to  (0);
                      \end{tikzpicture}
                    \end{minipage}
                            &$1$\\
      $12|389|56$ &
                    \begin{minipage}{0.75\textwidth}
                      \begin{tikzpicture}
                        [scale=0.9,every node/.style={circle,fill=black}]
                        \node[label=below:$1$] (1) at (1,0) {};
                        \node[label=below:$2$] (2) at (2,0) {};
                        \node[label=below:$3$] (3) at (3,0) {};
                        \node[label=below:$5$] (5) at (5,0) {};
                        \node[label=below:$6$] (6) at (6,0) {};
                        \node[label=below:$8$] (8) at (8,0) {};
                        \node[label=below:$9$] (9) at (9,0) {};
                        \node[label=below:$\infty$] (0) at (10,0) {};
                        \draw[thick,color=teal]
                        (1) [out=45, in=135] to  (2);
                        \draw[thick,color=teal]
                        (5) [out=45, in=135] to  (6);
                        \draw[thick,color=orange]
                        (8) [out=45, in=135] to  (9);
                        \draw[thick,color=teal]
                        (3) [out=45, in=135] to  (8);
                        \draw[thick,color=orange]
                        (2) [out=45, in=135] to  (0);
                        \draw[thick,color=orange]
                        (6) [out=45, in=135] to  (0);
                        \draw[thick,color=blue]
                        (9) [out=45, in=135] to  (0);
                      \end{tikzpicture}
                    \end{minipage}
                            & $0$\\
      \hline
    \end{tabular}
  \end{center}
  \ytableausetup{smalltableaux}
  \caption{Statistics for set partitions corresponding to $\ytableaushort{129,36,58}$\,.}
  \label{tab:statistics}
\end{table}
Table~\ref{tab:statistics} shows the arcs and the number of interlacings for the set partitions in Example~\ref{example:tableau}.
The first, second, and third arcs are shown in different colours.
Only crossing arcs of the same colour contribute to the interlacing number.

\begin{theorem}
  \label{theorem:statistic}
  For any multilinear tableau $T$,
  \begin{equation}
    \label{eq:rq-sp}
    c_q(T) = \sum_{\T(\AA)=T} q^{v(\AA)}.
  \end{equation}
\end{theorem}


\begin{corollary}
  \label{cor:noninterl}
For each partition $\lambda$ of $n$, the number of noninterlacing partitions of shape $\lambda$ is equal to the number of standard tableaux of shape $\lambda$.  
\end{corollary}

 Theorem \ref{theorem:statistic} allows us to express $b_\lambda(q)$ in Equation~\eqref{eq:bla} as a sum over set partitions of shape $\lambda$:
 \begin{equation}
   \label{eq:blamset}
b_\lambda(q)=\sum_{\AA\in \Pi_{n}(\lambda)}q^{v(\AA)}.   
 \end{equation}


\subsection{Value at $q=-1$}
\label{sec:minusone}
It turns out that $b_\lambda(-1)$ is always positive.
\begin{theorem}
  For every integer partition $\lambda$, $b_\lambda(-1)$ is the number of standard tableaux $T$ of shape $\lambda$ for which $c(T)$ is odd.
  For every non-empty\footnote{The empty partition is the unique partition of $0$ with no parts.} integer partition $\lambda$, $b_\lambda(-1)>0$.
\end{theorem}


For a large class of partitions $\lambda$, $b_\lambda(-1)$ has an interpretation in terms of shifted tableaux.
Let $\lambda=(\lambda_1,\dotsc,\lambda_m)$ be an integer partition of $n$.
A standard shifted tableau of shape $\lambda$ is an array
\begin{displaymath}
  T = (T_{ij}\mid T_{ij}\in \nat,\;1\leq i \leq m;\; i\leq j\leq \lambda_i+i-1),
\end{displaymath}
where each integer in $[n]$ occurs exactly once. The rows of $T$ increase from left to right, the columns of $T$ increase from top to bottom, and the diagonals of $T$ increase from top-left to bottom-right.
 We denote the set of multilinear shifted tableaux of shape $\lambda$ by $\stab_S(\lambda)$.
  When $\lambda$ is a partition of $[n]$, write $\stab(\lambda)$ for $\stab_{[n]}(\lambda)$.
 
\begin{example}
  The following is a standard shifted tableau of shape $(3,3,2,1)$:
  \ytableausetup{smalltableaux}
  \begin{displaymath}
    \ytableaushort{123,{\none}456,\none\none 78,\none\none\none 9}\,.
  \end{displaymath}
\end{example}
\begin{theorem}
  \label{theorem:minusone}
  For every partition $\lambda$ whose parts are distinct, with the possible exception of the largest part,
  \begin{displaymath}
    b_\lambda(-1) = |\stab(\lambda)|.
  \end{displaymath}
\end{theorem}
\begin{example}
  Take $\lambda = (3,3,1)$.
  Then
  \begin{displaymath}
    b_\lambda(q) = q^{4} + 5 q^{3} + 15 q^{2} + 28 q + 21,
  \end{displaymath}
  and $b_\lambda(-1)=4$.
  There are four standard shifted tableaux of shape $(3,3,1)$, namely
  \begin{displaymath}
    \ytableaushort{123,\none 456,\none\none 7}\,, \quad
    \ytableaushort{124,\none 356,\none\none 7}\,, \quad
    \ytableaushort{123,\none 457,\none\none 6}\,, \quad \text{ and } \quad
    \ytableaushort{124,\none 357,\none\none 6}\,.
  \end{displaymath}
\end{example}


\section{Profiles of Subspaces}
\label{sec:profiles-subspaces}

\subsection{Counting subspaces by profile}

Let $\Delta$ be a diagonal $n\times n$ matrix over $\Fq$ with distinct entries on its diagonal.
Recall the definition of $b_\lambda$ from Section \ref{sec:polyn-b_lambd}.  
\begin{theorem}
  \label{theorem:counting-profile}
  For every integer partition $\mu$, the number of subspaces of $\Fq^n$ with $\Delta$-profile $\mu$ is given by
  \begin{displaymath}
    \sigma_n(\mu)={n \choose |\mu|}(q-1)^{\sum_{j\geq 2} \mu_j}q^{\sum_{j\geq 2} \binom{\mu_j}2}b_{\mu'}(q).
  \end{displaymath}
\end{theorem}
Theorem~\ref{theorem:counting-profile} is a consequence of a more refined counting theorem (Theorem \ref{theorem:refined-counting-profile}).

For any $n\in \nat$, let $C(n,m)$ denote the set of all subsets of $[n]$ with cardinality $m$.
Given $C\in C(n,m)$ we always write $C$ as a tuple $  C = (c_1,\dotsc,c_m), \text{ where } c_1<\dotsb<c_m$.

\begin{definition}[Pivots]
Every $m$-dimensional subspace $W\subset \Fq^n$ has a unique basis in reduced row echelon form, namely a basis whose elements are the rows of a matrix $A=(A_{ij})$ satisfying the following conditions:
\begin{enumerate}
\item There exists $C=(c_1,\dotsc,c_m)\in C(n,m)$ (called the pivots of $W$) such that the first non-zero entry in the $i$th row of $A$ lies in the $c_i$th column and is equal to $1$.
\item $A_{i'c_i}=0$ for all $i'\neq i$ (the only non-zero entry in the $c_i$th column lies in the $i$th row).
\end{enumerate}
When this happens we say that $W$ has pivots $C$.
\end{definition}
\begin{example}
  The basis in reduced row echelon form for a subspace of $\Fq^n$ (with $n\geq 4$) with pivots $(1,3,4)$ is given by the rows of a $3\times n$ matrix of the form
  \begin{displaymath}
    \begin{pmatrix}
      1 & * & 0 & 0 & * & \dotsb & *\\
      0 & 0 & 1 & 0 & * & \dotsb & *\\
      0 & 0 & 0 & 1 & * & \dotsb & *
    \end{pmatrix},
  \end{displaymath}
  where each $*$ denotes an arbitrary element of $\Fq$.
\end{example}






















Recall the following well-known result~\cite{MR270933}.
\begin{theorem}
  \label{theorem:q-bin-coeff}
  The number of $m$-dimensional subspaces of $\Fq^n$ with pivots $C=(c_1,\dotsc,c_m)$ is $q^{\beta(C,[n]-C)}$, where
  \begin{align*}
    \beta(C,[n]-C) & =|\{(c,c') \mid c<c',\,c \in C, \,c'\in [n]-C\}|\\
               & = \sum_{i=1}^m (n-m-c_i+i).
  \end{align*}
\end{theorem}

A simultaneous refinement of Theorems~\ref{theorem:counting-profile} and~\ref{theorem:q-bin-coeff} is the following:
\begin{theorem}
  \label{theorem:refined-counting-profile}
  For every $C\in C(n,m)$ and every partition $\mu$ with $\mu_1=m$, the number of $m$-dimensional subspaces of $\Fq^n$ with pivots $C$ and profile $\mu$ is given by
  \begin{displaymath}
    \sigma^C_n(\mu) = (q-1)^{\sum_{j\geq 2}\mu_j}q^{\sum_{j\geq 2}\binom{\mu_j}2} \sum_{T\in \Tab_{\subset [n]}(\mu') \text{ has first column }C} c_q(T).
  \end{displaymath}
\end{theorem}

Taking the sum over all $C\in C(n,m)$, where $m=\mu_1$ gives Theorem~\ref{theorem:counting-profile}.
\begin{corollary}
  For any $C\in C(n,m)$,
  \begin{displaymath}
    q^{\beta(C,[n]-C)} = \sum_{\{\mu\mid \mu_j=m\}} (q-1)^{\sum_{j\geq 2} \mu_j}q^{\sum_{j\geq 2}\binom{\mu_j}2}\sum_{T\in \Tab_{\subset [n]}(\mu') \text{ has first column }C} c_q(T).
  \end{displaymath}
\end{corollary}


  
\subsection{Splitting subspaces and chord diagrams}
\label{sec:chord}
Recall the definition of a splitting subspace from Ghorpade and Ram \cite{MR2961399}.    
\begin{definition}

 Let $n=md$. An $m$-dimensional subspace $W\subset \Fq^n$ is $\Delta$-splitting if
  \begin{displaymath}
    \Fq^n = W\oplus \Delta W\oplus \dotsb \oplus \Delta^{d-1}W.
  \end{displaymath}
\end{definition}
It follows that $\Delta$-splitting subspaces are those with $\Delta$-profile $(m^d)$. Theorem \ref{theorem:counting-profile} gives the number of $m$-dimensional $\Delta$-splitting subspaces as
$$
\sigma_n(m^d)=(q-1)^{m(d-1)} q^{{m \choose 2}(d-1)}b_{(d^m)}(q).
$$
By Equation~\eqref{eq:blamset} we have
$$ 
b_{(d^m)}(q)=\sum_{\AA \in \Pi_n(d^m)}q^{v(\AA)}. 
$$
When $d=2$, $\Pi_{n}(2^m)$ coincides with the set of chord diagrams on $2m$ points and the interlacing number coincides with the number of crossing chords. Thus $b_{(2^m)}(q)$ coincides with the polynomial $T_m(q)$ studied by Touchard \cite{MR37815,MR36006,MR46325}  in the context of the stamp folding problem. For proofs of Touchard's compact expression for $T_m(q)$ see Riordan~\cite{MR366686}, Read \cite{MR556055} and Penaud~\cite{MR1336847}. For a beautiful exposition, see Aigner \cite[page~337]{MR2339282}.         
 
   
\printbibliography  
  

 
\end{document}  
