\RequirePackage[l2tabu, orthodox]{nag}
\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\usepackage{mathtools,enumitem,tikz,bm}
\usepackage[centertableaux]{ytableau}
\usepackage[capitalize,noabbrev]{cleveref}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\underline{#1}}}
\newcommand{\head}[1]{{\mathcal{H}(#1)}}
\newcommand{\tail}[1]{{\mathcal{T}(#1)}}
\newcommand{\setC}{\mathbb{C}}
\newcommand{\setN}{\mathbb{N}}
\newcommand{\wvec}{\mathbf{w}}
\newcommand{\uvec}{\mathbf{u}}
\newcommand{\vvec}{\mathbf{v}}
\newcommand{\ttr}{\mathtt{r}}
\newcommand{\ttc}{\mathtt{c}}
\newcommand{\Vol}{\mathrm{Vol}}
\newcommand{\symS}{S}
\newcommand{\BST}{\mathrm{BST}}
\newcommand{\BSD}{\mathrm{BSD}}
\newcommand{\BSP}{\mathrm{BSP}}
\newcommand{\BSPD}{{\mathrm{BSP}^*}}
\DeclareMathOperator{\length}{\ell}
\DeclareMathOperator{\inv}{inv}
\DeclareMathOperator{\hor}{hor}
\DeclareMathOperator{\DES}{DES}
\DeclareMathOperator{\des}{des}
\newcommand{\qbin}{\genfrac{[}{]}{0pt}{}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf Enumeration of Border-Strip Decompositions \\
\vskip .1in
and Weil-Petersson Volumes}
\vskip 1cm
\large
Per Alexandersson\\
Department of Mathematics \\
Royal Institute of Technology\\
SE-100 44 Stockholm\\
Sweden\\
\href{mailto:per.w.alexandersson@gmail.com}{\tt per.w.alexandersson@gmail.com} \\
\vskip 1cm
Linus Jordan \\
Department of Mathematics \\
EPFL\\
1015 Lausanne\\
Switzerland\\
\href{mailto:linus.jordan@bluewin.ch}{\tt linus.jordan@bluewin.ch} \\
\end{center}
\vskip .2 in
\begin{abstract}
We describe an injection from border-strip decompositions of certain diagrams to permutations.
This allows us to provide enumeration results as well as $q$-analogues of enumeration formulas.
%
Finally, we use this injection to prove a connection between the number of
border-strip decompositions of the $n\times 2n$ rectangle and the Weil-Petersson volume
of the moduli space of an $n$-punctured Riemann sphere.
\end{abstract}
%\tableofcontents
\section{Introduction and overview of results}
Border-strip \emph{tableaux} have a rich history, originating with the
celebrated Murnaghan-Nakayama rule \cite{Murnaghan1937,Nakayama1940},
which provides a combinatorial formula
for computing character values in the symmetric group.
It is given as a signed sum over border-strip tableaux, but the sign only depends on
the border-strip \emph{decomposition}, i.e.,\ the ``unlabeled version''
of the tableaux. This motivates us to study border-strip decompositions.
Note that there is a hook-formula for enumerating border-strip tableaux
given by Fomin and Lulov \cite{FominLulov1997} but less study has been devoted to
enumerating border-strip decompositions.
Even determining if a region can be tiled by $n$-strips is non-trivial
and sometimes $\mathrm{NP}$-complete,
see the papers by Beauquier et al.,\ and Pak \cite{Beauquier1995,Pak2000Ribbon}.
We introduce a family of diagrams called \emph{simple diagrams},
which have particularly nice properties with respect to enumeration.
These diagrams are parameterized by a binary sequence
and the strip size.
In particular, we show that certain normalized
enumerations grow as a polynomial in $n$ --- the size of the strips.
We show that border-strip tableaux and border-strip decompositions of simple diagrams
are in bijection with certain classes of permutations,
see \cref{InjectionToSm} and \cref{cor:SimpleBSDCharacterization}.
This allows us to study a certain $q$-analogue of
border-strip decompositions which generalize the classical inversion-statistic on permutations.
For example, in \cref{cor:totalNumberOfBorderStripDecomps},
we give the formula
\[
\sum_{\wvec \in \{\ttr,\ttc\}^k} \sum_{D \in \BSD(\wvec,n)} q^{\inv(D)} = [n+1]^k_q [n]_q!
\]
where the first sum is over all binary sequences of length $k$ (defining a simple diagram),
and $\BSD(\wvec,n)$ is the set of border-strip decompositions with strips of size $n$
and diagram determined by $(\wvec,n)$.
In \cref{Polynomiality} we give an efficient way to compute the number of
border-strip decompositions of simple diagrams, as a function of $n$.
This allows us to prove that ``straighter''
simple diagrams admit a larger number of border-strip decompositions,
see \cref{thm:straighterInequality} and the maximum is attained for rectangles.
In contrast, in \cref{cor:countingBST} we show that whenever $n\geq k$,
all these diagrams admit \emph{the same number of border-strip tableaux}.
Finally, we give a new interpretation of the sequence \seqnum{A115047} in the OEIS.
We show that these numbers count tilings of a $n \times 2n$-rectangle with strips of size $n$,
thus providing a new simple combinatorial interpretation of certain Weil-Petersson volumes.
We cannot give an intuitive explanation for this curious
connection and it invites for further research.
\section{Enumeration of border-strip decomposition}
We first give simplified definitions of border strip tableaux and decompositions
which are sufficient for the purpose of this article ---
for a thorough background see Richard Stanley's book \cite{StanleyEC2}.
\subsection{Preliminaries}
A \emph{diagram} is formally defined as a set of integer coordinates
\[
\{ (i,j) \in \setN^2 : \mu_i \leq j \leq \lambda_i \},
\]
where $\lambda$ and $\mu$ are integer partitions such that $\mu_i \leq \lambda_i$
for all $i=1,2,\dotsc$. We refer the coordinates in the diagram as \emph{boxes}.
For example, $\lambda=(4,3,2,2,2)$, $\mu=(2,1,1)$ is illustrated as
\[
\ytableausetup{boxsize=0.9em}
\begin{ytableau}
\none & \none & \scriptstyle{13} & \scriptstyle{14} \\
\none & \scriptstyle{22} & \scriptstyle{23} \\
\none & \scriptstyle{32}\\
\scriptstyle{41} & \scriptstyle{42}\\
\scriptstyle{51} & \scriptstyle{52}
\end{ytableau}
\]
where $ij$ is written in the box $(i,j)$.
A \emph{border-strip} or \emph{strip} for short
of a diagram is a subset of boxes
\[
(a_1,b_1),(a_2,b_2),\dotsc,(a_n,b_n)
\]
such that for every $i=1,\dotsc,n-1$,
\[
a_i = a_{i+1} \text{ and } b_i - 1 = b_{i+1} \qquad \text{ or } \qquad
a_i + 1 = a_{i+1} \text{ and } b_i = b_{i+1}.
\]
A \emph{tableau} $T$ is map $T:D \to \setN$ from a diagram to the set of natural numbers.
A tableau is illustrated by writing $T(i,j)$ in the box $(i,j)$.
A \emph{border-strip tableau}\footnote{Also known as rim-hook tableau.}
is a tableau $T$ such that rows and columns are weakly increasing
and for all $i$, the set of boxes $T^{-1}(i)$ is a border-strip.
In this paper, we shall only consider border-strip tableaux such that
for some $m$ and $n$,
\[
|T^{-1}(1)|=|T^{-1}(2)|=\dotsb=|T^{-1}(m)|=n \text{ and } |T^{-1}(j)|=0 \text{ for all $j>m$}.
\]
Hence, each strip of $T$ has size $n$ and $T$ is a border-strip tableau with strip size $n$.
Let $\BST(D,n)$ denote the set of border-strip tableaux with strip size $n$ and
underlying diagram $D$. For our purposes, $D$ could be any parameterization of a diagram,
in our case we are going to use binary words --- see \cref{simple diagram} below.
A \emph{border-strip decomposition} with strip size $n$
is a set-partition of a diagram into border-strips
where all the border-strip are of size $n$.
Analogously, $\BSD(D,n)$ denotes the set of border-strip decompositions of the diagram $D$.
Observe that every border strip tableau $T$ in $\BST(D,n)$
defines a border-strip decomposition in $\BSD(D,n)$,
as we shall see in the following example.
\begin{example}
The following tableau is an element in $\BST(6 \times 5,5)$,
where $6\times 5$ denotes a rectangle of dimension $6 \times 5$.
The corresponding border-strip
decomposition with the strips indicated by the colors is shown on the right.
\begin{align}\label{eq:borderTableauExample}
\ytableausetup{centertableaux,boxsize=1.0em}
\begin{ytableau}
1 & 1 & 1 & 1 & 2 \\
1 & 2 & 2 & 2 & 2 \\
3 & 3 & 4 & 4 & 6 \\
3 & 4 & 4 & 5 & 6 \\
3 & 4 & 5 & 5 & 6 \\
3 & 5 & 5 & 6 & 6
\end{ytableau}
\qquad
\begin{ytableau}
*(blue) & *(blue) & *(blue) & *(blue) & *(red) \\
*(blue) & *(red) & *(red) & *(red) & *(red) \\
*(gray) & *(gray) & *(yellow) & *(yellow) & *(brown) \\
*(gray) & *(yellow) & *(yellow) & *(green) & *(brown) \\
*(gray) & *(yellow) & *(green) & *(green) & *(brown) \\
*(gray) & *(green) & *(green) & *(brown) & *(brown)
\end{ytableau}
\end{align}
\end{example}
It is straightforward to verify that for each border-strip decomposition
there is at least one border-strip tableau,
so we get $|\BST(D,n)|\geq |\BSD(D,n)|$ for any diagram $D$ and natural number $n$.
On the other hand, we obtain a border-strip decomposition
from a border-strip tableau by ``forgetting the numbers''
so we have that $\BST(D,n)=\emptyset \iff \BSD(D,n)=\emptyset $.
Let $B$ be a border-strip, which is a subset of boxes $(i,j)$ (row-index, column-index).
It is easy to verify that the set
\[
\{ j-i : (i,j) \in B \}
\]
is of the form $a,a+1,\dotsc,b$ for some $a**\sigma^{-1}(n+i) $ whenever $w_i=\ttr$.
\end{enumerate}
\end{proposition}
\begin{proof}
We construct the tableau $T$ from $\sigma \in \BSP(\wvec,n)$
by starting from the last diagonal.
By definition, the unique head in diagonal $i$ must have
value $\sigma^{-1}(i)$ in $T$.
If $k < i \leq n+k$ then diagonal $i$ has one box
more than diagonal $i+1$ and it is always possible
to extend the partial border-strip tableau one
diagonal further in a unique fashion as in \cref{lem:headsGiveTheBSD}.
However, when $1\leq i \leq k$ we need to take $w_i$ into consideration.
If $w_i=\ttc$ then diagonals $i$ and $i+1$ are arranged as follows.
\begin{align*}
\ytableausetup{centertableaux,boxsize=0.8em}
\begin{ytableau}
\empty& \\
\none & &\\
\none & \none & &\\
\none & \none & \none & &
\end{ytableau}
\end{align*}
We observe that the new strip starting in diagonal $i$
must be \emph{above} the strip ending in diagonal $i+1$ (and starting in diagonal $n+i$).
Hence, it must be filled with a smaller number in $T$,
so we must have $\sigma^{-1}(i) < \sigma^{-1}(n+i)$.
If $w_i=\ttr$ diagonals $i$ and $i+1$ are arranged as follows.
\begin{align*}
\ytableausetup{centertableaux,boxsize=0.8em}
\begin{ytableau}
\empty\\
&\\
\none & &\\
\none & \none & &\\
\none & \none & \none &
\end{ytableau}
\end{align*}
Analogously to the previous argument,
the new strip starting in diagonal $i$ must be \emph{below} strip $n+i$
and thus $\sigma^{-1}(i)>\sigma^{-1}(n+i)$.
\end{proof}
\subsection{Counting border-strip tableaux and decompositions}
We now have the necessary setup to obtain some enumerative results.
\begin{proposition}\label{cor:countingBST}
For a sequence $\wvec$ of length $k \leq n$,
\[
|\BST(\wvec,n)|=2^{-k}(n+k)!.
\]
In particular, the number of border-strip tableaux
only depends on the length of the sequence for $n\geq k$.
\end{proposition}
\begin{proof}
Recall from \cref{injectivity} that $|\BST(\wvec,n)|=|\BSP(\wvec,n)|$.
From conditions (a) and (b) in \cref{InjectionToSm}
we know that the $\wvec$ determines the
relative order of the strips $i$ and $n+i$ for every $i=1,2,\dotsc,k$.
Whenever $n\geq k$, these pairs are disjoint.
As there are no further restrictions on
the $(n+k)!$ possible permutations, $|\BSP(\wvec,n)|=2^{-k}(n+k)!$.
\end{proof}
\cref{cor:countingBST} cannot be strengthened to the case $k>n$,
as the count $|\BST(\wvec,n)|$ in this case might depend on $\wvec$.
\begin{corollary}
For every permutation $\sigma\in \symS_{n+k}$ there is exactly
one sequence $\wvec$ of length $k$ such that $\sigma\in \BSP(\wvec,n)$.
In particular, $\psi$ determines a bijection
between $\lbrace \BST(\wvec,n):\wvec\in\lbrace \ttr,\ttc \rbrace^k\rbrace$ and $\symS_{n+k}$.
Consequently,
\[
\sum_{\wvec\in\lbrace \ttr,\ttc \rbrace^k}|\BST(\wvec,n)|=(n+k)!.
\]
\end{corollary}
\begin{proof}
From \cref{injectivity} we know $\psi$ restricted to one sequence $\wvec$ is injective.
\cref{InjectionToSm} shows that a permutation uniquely determines the sequence $\wvec$,
$\psi$ must be injective over the set of all sequences of length $k$.
On the other hand for any permutation $\sigma\in\symS_{n+k}$
there is always one sequence $\wvec\in \lbrace \ttr,\ttc \rbrace^k$ such
that $\sigma\in \BSP(\wvec,n)$ as we can find appropriate values for $w_i$ from
$\sigma^{-1}(i)$ and $\sigma^{-1}(n+i)$ together with \cref{InjectionToSm}.
Hence $\psi$ is also surjective.
\end{proof}
\begin{definition}[$k$-descents]
Let $\sigma \in \symS_n$.
We say that $i \in \{1,\dotsc,n-1\}$ is
a $k$-\emph{descent} of $\sigma$ if $\sigma(i)-k>\sigma(i+1)$.
Let $\DES_k(\sigma)$ denote the set of $k$-descents of $\sigma$
and let $\des_k(\sigma)$ be the number of such $k$-descents.
For example, the $3$-descents of the permutation
\[
[2,4,\mathbf{10},5,6,3,\mathbf{8},1,7,9]
\]
are $3$ and $7$ (marked in bold).
\end{definition}
\begin{lemma}[Technical lemma]\label{lem:technicalLemma}
Let $T=\psi^{-1}(\sigma)$ for some $\sigma \in \BSP(\wvec,n)$.
The following three statements are equivalent:
\begin{enumerate}[label=(\alph*)]
\item The permutation $\sigma$ has an $n$-descent.
\item There is an $m$ such that the strips $B_m \coloneqq T^{-1}(m)$ and $B_{m+1} \coloneqq T^{-1}(m+1)$
are not comparable in the sense of \cref{def:comparable}
and $\sigma(m)>\sigma(m+1)$.
\item
There are two strips $B_x \coloneqq T^{-1}(x)$ and $B_y \coloneqq T^{-1}(y)$
in $T$ such that $B_x$ is not comparable to $B_y$ in the sense of \cref{def:comparable},
where $x < y$ and $\sigma(x) > \sigma(y)$.
\end{enumerate}
\end{lemma}
\begin{proof}
Recall that $\sigma(x)$ is simply the diagonal containing the head of $B_x$.
\medskip
\noindent
\emph{Case $(a)\implies(b)$.} We have that $\sigma(m)-\sigma(m+1) > n$ for some $m$.
Since $\sigma(m)>\sigma(m+1)+n$,
we cannot have that $B_{m}$ is adjacent to $B_{m+1}$.
Furthermore, there cannot be a longer sequence of
strips $B_m = B_{i_1},\dotsc,B_{i_\ell} =B_{m+1}$
such that $B_{i_j}$ is above $B_{i_{j+1}}$ as the
values of these strips must then
lie strictly between $m$ and $m+1$, which is impossible.
Hence, $B_m$ is not inner to $B_{m+1}$
and this implies that they are not comparable.
\medskip
\noindent
\emph{Case $(b)\implies(c)$.}
Just take $x=m$ and $y=m+1$.
\medskip
\noindent
\emph{Case $(c)\implies(a)$.}
Consider the interval of values $x, x+1,\dotsc, y$
and choose $x \leq m < y$ such that $\sigma(m) - \sigma(m+1)$ is maximized.
Suppose $\sigma(m)-\sigma(m+1)\leq n$.
Then there is a sequence of values $i_1,\dotsc,i_s$ such that
\[
x = i_1 < i_2 < \dotsb < i_s = y,
\qquad
\sigma(x) = \sigma(i_1) > \sigma(i_2) > \dotsb > \sigma(i_s) = \sigma(y),
\]
and for all $j$ we have $\sigma(i_j)-\sigma(i_{j+1})\leq n$.
But \cref{comparable} implies that the strip with value $i_j$
is above the strip with value $i_{j+1}$.
By transitivity, $B_x$ must be inner to $B_y$ which violates one of the conditions.
It follows that $\sigma(m)-\sigma(m+1) > n$ and $\sigma$ has an $n$-descent.
\end{proof}
We are now ready to characterize a subset of $\BSP(\wvec,n)$
which is in bijection with the border-strip decomposition $\BSD(\wvec,n)$.
Let $s_1,\dotsc,s_{n-1}$ denote the simple transpositions in $\symS_n$.
\begin{proposition}\label{CountingBSD}
Suppose $\wvec$ is a sequence of length $k$, $\sigma \in \BSP(\wvec,n)$, and $i\in \DES_n(\sigma)$.
Then the border-strip tableaux $\psi^{-1}(s_i\sigma)$ and $\psi^{-1}(\sigma)$
have the same border-strip decomposition.
Moreover, the sets
\[
\BSD(\wvec,n) \quad \text{ and } \quad \{ \sigma \in \BSP(\wvec,n) : \des_n(\sigma)=0 \}
\]
are in bijection.
\end{proposition}
\begin{proof}
Let $\tau \coloneqq s_i \sigma$, $T_\sigma \coloneqq \psi^{-1}(\sigma)$, and $T_\tau \coloneqq \psi^{-1}(\tau)$
be the corresponding border-strip tableaux.
First we need to show that $\tau \in \BSP(\wvec,n$).
The only places where $\tau^{-1}$ differ from $\sigma^{-1}$ are $\tau(i)$ and $\tau(i+1)$.
Now, if $j \in \{1,\dotsc,k\}$ then at most one of
$\sigma^{-1}(j) \text{ and }
\sigma^{-1}(n+j)
$
is different from $\tau^{-1}$ and
the quantities
\begin{equation}\label{eq:sigmatau}
\tau^{-1}(j)-\tau^{-1}(n+j) \text{ and } \sigma^{-1}(j)-\sigma^{-1}(n+j)
\end{equation}
are either the same or differ by $1$.
In particular, the quantities in \eqref{eq:sigmatau} cannot have opposite signs.
Since $\sigma \in \BSP(\wvec,n)$, the corresponding inequalities in \cref{InjectionToSm}
are also fulfilled by $\tau$. Hence $\tau \in \BSP(\wvec,n)$ as well.
\noindent
\emph{It remains to show that $T_\tau$ and $T_\sigma$
have the same border-strip decomposition.}
The only strips in $T_\sigma$ and $T_\tau$ which have a different number
are strip $\tau(i)$ and strip $\tau(i+1)$, with a $\pm 1$ difference.
Therefore, the only pair of strips that has a different relative
ordering in $T_\tau$ is the pair $(\tau(i),\tau(i+1))$.
However, since $i$ is an $n$-descent it does not affect the construction
in the proof of \cref{InjectionToSm} and it follows that $T_\sigma$
and $T_\tau$ have the same border-strip decomposition.
For the second statement, we use \cref{lem:technicalLemma}.
In order for $\sigma$ to be free of $n$-descents,
the relative order of the values of all pairs of \emph{non-comparable} strips is uniquely determined.
On the other hand, the relative order of pairs of \emph{comparable strips}
is determined by the shape of the diagram.
Since a permutation is uniquely determined by the relative order of all pairs of entries,
there is at most one permutation without $n$-descents
in $\BSP(\wvec,n)$ with a given border-strip decomposition.
On the other hand, we can always find such a $\sigma$
by starting from any permutation in $\BSP(\wvec,n)$ and repeatedly
decrease the number of $n$-descents until
a permutation without $n$-descents is obtained.
This is done by interchanging the values in the non-comparable strips
$B_m$ and $B_{m+1}$ in \cref{lem:technicalLemma} (b).
\end{proof}
\begin{corollary}\label{cor:SimpleBSDCharacterization}
Let $\wvec \in \{\ttc,\ttr\}^k$.
The set of border-strip decompositions of the simple diagram $(\wvec,n)$
is in bijection with the set of permutations in $\symS_{n+k}$ such that
for each $i \in [k]$
\begin{itemize}
\item $w_i = \ttc \quad \Longrightarrow \quad \sigma^{-1}(i) < \sigma^{-1}(n+i)$,
\item $w_i = \ttr \quad \Longrightarrow \quad \sigma^{-1}(i) > \sigma^{-1}(n+i)$ and
\item $\sigma(j)-\sigma(j+1)\leq n$ for all $j\in[n+k-1]$.
\end{itemize}
\end{corollary}
Let $\BSPD(\wvec,n)$ be the subset of permutations in $\symS_{n+k}$
that fulfill the three conditions in \cref{cor:SimpleBSDCharacterization}.
Hence,
\[
\BSPD(\wvec,n) = \{ \sigma \in \BSP(\wvec,n) : \des_n(\sigma)=0 \}.
\]
Note that $\psi^{-1}$ gives a bijection from $\BSPD(\wvec,n)$ to $\BSD(\wvec,n)$.
\begin{definition}
For a sequence $\wvec \in \{\ttr,\ttc\}^k$ let
\begin{equation}
\hat{f}_{\wvec}(n) \coloneqq |\BSD(\wvec,n)|\frac{(2k)!}{(n-k)!}.
\end{equation}
\end{definition}
\begin{proposition}\label{Polynomiality}
Whenever $n\geq 2k$, the function $\hat{f}_{\wvec}(n)$ is equal to
\begin{align}\label{eq:fFormula}
f_{\wvec}(n) \coloneqq \sum_{\tau \in \BSP(\wvec,k)}(n+k-\des_k(\tau))_{2k}.
\end{align}
As a consequence, $\hat{f}_{\wvec}(n)$ is a polynomial in $n$ of
degree $2k$ with integer coefficients when restricted to
values $n\geq 2k$.
Moreover, $f_{\wvec}(n)$ is divisible by the falling factorial $(n+1)_{k+1}$.
\end{proposition}
\begin{proof}
We start by assuming that $n \geq 2k$.
Interpreting permutations in $\symS_{n+k}$ as sequences of $n+k$ numbers,
we note that the first two conditions in \cref{cor:SimpleBSDCharacterization} only
apply to the relative order of the first and last $k$ elements.
Thus, in order to construct a permutation $\sigma$ in $\symS_{n+k}$
satisfying the three conditions in
\cref{cor:SimpleBSDCharacterization}, we proceed in three steps.
\begin{enumerate}
\item Choose an ordering of the entries $\{1,2,\dotsc,k\}\cup \{n+1,n+2,\dotsc,n+k\}$.
\item Choose the positions of the entries $\{1,2,\dotsc,k\} \cup \{n+1,n+2,\dotsc,n+k\}$.
\item Choose an ordering of the entries $\{k+1,\dotsc,n\}$.
\end{enumerate}
Note that as $n\geq 2k$, the unions in the first two steps above are disjoint.
Not every choice here will fulfill the conditions in
\cref{cor:SimpleBSDCharacterization} --- we
shall see below which ones are valid.
For a choice in the first step, two things might happen.
\begin{enumerate}
\item[a)] There is some pair $(i,i+n)$ in the wrong order --- violating one of the first two conditions.
In this case we do not have a border-strip tableau, and thus no border-strip composition for this choice.
\item[b)] All pairs $(i,i+n)$ have the correct order.
In this case, the ordering of the $2k$ entries
\[
\{1,2,\dotsc,k\}\cup \{n+1,n+2,\dotsc,n+k\}
\]
fulfills the conditions (after standardization!) of being a permutation $\tau \in \BSP(\wvec,k)$.
Notice the use of $k$ and not $n$ here as strip-size.
\end{enumerate}
Now we need to ensure that there are no $n$-descents in the final permutation.
If there are no $k$-descents in $\tau$ in step $b$) above, then there are no $n$-descents either.
Otherwise, we need to insert another number after every $k$-descent of $\tau$.
This means we only have $\binom{n+k-\des_k(\tau)}{2k}$ valid choices in step (2).
The last step always has $(n-k)!$ valid choices as the order on $\{k+1,\dotsc,n\}$ does not matter.
It follows that whenever $n\geq 2k$, the function $\hat{f}_{\wvec}(n)$ is given by
\begin{align*}
\hat{f}_{\wvec}(n) & =\frac{(2k)!}{(n-k)!} \sum_{\tau \in \BSP(\wvec,k)} \binom{n+k-\des_k(\tau)}{2k} (n-k)! \\
& =\sum_{\tau \in \BSP(\wvec,k)}(n+k-\des_k(\tau))_{2k}.
\end{align*}
This function is obviously a polynomial of degree $2k$.
Furthermore, since $\des_k(\tau)$ is between $0$ and $k-1$
it follows that $(n+k-\des_k(\tau))_{2k}$ is divisible by $(n+1)_{k+1}$.
\end{proof}
\begin{corollary}
We have the enumeration
\[
|\BSD(\mathtt{rc},n)|=(n+1)!(3n+2)/12 \text{ whenever } n\geq2.
\]
\end{corollary}
\begin{proof}
Using \cref{Polynomiality}, we know that $|\BSD(\mathtt{rc},n)|$ can
be expressed as $(n-2)!\hat{f}_{\mathtt{rc}}(n)/4!$.
Since we know that $\hat{f}_{\mathtt{rc}}(n)$ is a polynomial in $n$ for $n \geq 4$,
it suffices to verify the formula for the first few values of $n$.
\end{proof}
The sequence $a_{n+1} = (n+1)!(3n+2)/12$ appears \seqnum{A227404} in the OEIS,
where $a_n$ count the total number of inversions in all permutations in $\symS_n$
consisting of a single cycle. For example, the permutations $(123)$ and $(132)$
have four inversions in total, giving $a_3=4$.
We have not managed to find an explicit bijection that shows this correspondence.
\subsection{Inversions and \texorpdfstring{$q$}{q}-analogues}
\begin{definition}[Inversions]
Two border strips $B_1$ and $B_2$ in a decomposition
form an \emph{inversion} if and only if the following three conditions are fulfilled:
\begin{itemize}
\item The intersection
\[
\{ j-i : (i,j) \in B_1 \} \cap \{ j-i : (i,j) \in B_2 \}
\]
is non-empty. Equivalently, there is a diagonal
as in \cref{def:diagLabeling} that intersects both $B_1$ and $B_2$.
\item $B_1$ is inner to $B_2$, and
\item $\head{B_1}>\head{B_2}$.
\end{itemize}
\end{definition}
We prove in \cref{cor:MahonianEnumeration} that this definition
generalizes the notion of inversions of permutations in a natural manner.
\begin{lemma}\label{lem:inversionCondition}
Let $\sigma \in \BSPD(\wvec,n)$, with $B_\sigma \coloneqq \psi^{-1}(\sigma)$
being the corresponding border-strip decomposition.
Then the strips $i$ and $j$ in $B_\sigma$
with $i\sigma^{-1}(j)$.
\end{lemma}
\begin{proof}
If $j-i\geq n$ they do not have an element on the same diagonal,
and by definition do not form an inversion.
If $j-i\sigma^{-1}(j)$
then strip $j$ is above strip $i$ and they form an inversion.
\end{proof}
Given a border-strip decomposition $B$, let $\inv(B)$ denote the total number of inversions in $B$.
Furthermore, for $\sigma \in \symS_{n+k}$ let
\[
\inv_n(\sigma) \coloneqq \{ (i,j) : 0\sigma^{-1}(j) \}.
\]
The $q$-analogue of $\BSD(\wvec,n)$ is defined as
\begin{align}
|\BSD(\wvec,n)|_q \coloneqq \sum_{B \in \BSD(\wvec,n)} q^{\inv(B)}
\end{align}
and by \cref{lem:inversionCondition} we have that
\begin{align}
|\BSD(\wvec,n)|_q = \sum_{\sigma \in \BSPD(\wvec,n)} q^{\inv_n(\sigma)}.
\end{align}
\begin{corollary}\label{cor:MahonianEnumeration}
The $q$-analogue of the $n\times n$-square, $|\BSD(\emptyset,n)|_q$, satisfies the identity
\[
\sum_{B \in \BSD(\emptyset,n)} q^{\inv(B)} = [n]_q!.
\]
\end{corollary}
\begin{proof}
From \cref{InjectionToSm} we know every permutation in $\symS_n$ is
in $\BSPD(\emptyset,n)$. From \cref{CountingBSD},
we know every border-strip tableau correspond to a unique border-strip decomposition.
From \cref{lem:inversionCondition} we can then deduce that the $q$-analogue is given by $[n]_q!$.
\end{proof}
\begin{corollary}
We have the following $q$-analogue for $\BSD(\ttc,n)$:
\[
\sum_{B \in \BSD(\ttc,n)} q^{\inv(B)} = [n-1]_q! \sum_{i=1}^n i q^{i-1}.
\]
\end{corollary}
\begin{proof}
We get a permutation corresponding to a decomposition by placing $1$ and $n+1$
(i.e.,\ choose $\sigma^{-1}(1)$ and $\sigma^{-1}(n+1)$), and then choose the
order of $2,\dotsc,n$. This choice gives $[n-1]_q!$ and the
possible positions of $1$ and $n+1$ give $\sum_{i=1}^n i q^{i-1}$, as $1$ has
to be before $n+1$ for it to be a border-strip tableau.
Note that there cannot be any $n$-descents and therefore the number of border-strip tableaux
is equal to the number of decompositions.
\end{proof}
\begin{proposition}\label{prop:inductionStep}
If $\wvec$ is a sequence of a simple diagram, then
\[
|\BSD(\ttc \wvec,n)|+|\BSD(\ttr \wvec,n)|=(n+1)|\BSD(\wvec)|.
\]
Furthermore, this relation extends to the following $q$-analogue:
\[
|\BSD(\ttc \wvec,n)|_q + |\BSD(\ttr \wvec,n)|_q = [n+1]_q |\BSD(\wvec)|_q.
\]
\end{proposition}
\begin{proof}
If we fix the positions of the heads in $(\wvec ,n)$, the new head in $(\ttc\wvec, n)$ must
be above the strip it replaces, where as in $(\ttr\wvec, n)$ it must be below.
Together, this gives $n+1$ choices to complete the partial decomposition to a BSD of $(\wvec, n)$.
If, in $(\ttc\wvec, n)$ or in $(\ttr\wvec ,n)$, we place the new head in position $i$ of the diagonal,
the new strip forms an inversion with all $i-1$ strips above it.
This proves the $q$-analogue.
\end{proof}
\begin{corollary}\label{cor:totalNumberOfBorderStripDecomps}
We can enumerate the total number of border-strip
decompositions for all sequences of length $k$:
\[
\sum_{\wvec\in\lbrace \ttr,\ttc\rbrace^k}|\BSD(\wvec,n)|=(n+1)^k n!
\]
and this relation extends to the $q$-analogue
\begin{equation}\label{eq:qAnalogCount}
\sum_{\wvec \in \{\ttr,\ttc\}^k } \sum_{B \in \BSD(\wvec,n)} q^{\inv(B)}=[n+1]_q^k[n]_q!.
\end{equation}
\end{corollary}
\begin{proof}
It suffices to show the $q$-analogue. We proceed by induction over $k$.
The base case $k=0$ is given by \cref{cor:MahonianEnumeration}.
We then have
\begin{align*}
\sum_{\wvec \in \{\ttr,\ttc\}^k } |\BSD(\wvec,n)|_q &=
\sum_{\wvec \in \{\ttr,\ttc\}^{k-1} } |\BSD(\ttr \wvec,n)|_q +
\sum_{\wvec \in \{\ttr,\ttc\}^{k-1} } |\BSD(\ttc\wvec,n)|_q \\
&= [n+1]_q \sum_{\wvec \in \{\ttr,\ttc\}^{k-1} } |\BSD(\wvec,n)|_q \\
&= [n+1]_q \left( [n+1]_q^{k-1} [n]_q! \right) \\
&= [n+1]_q^{k} [n]_q!
\end{align*}
where the second equality is due to \cref{prop:inductionStep},
and the third equality is our induction hypothesis.
This completes the proof.
\end{proof}
For $n=k-1$, \eqref{eq:qAnalogCount} gives the sequence $a(n)=(n+1)^{n-1} n!$, which is \seqnum{A066319}.
This sequence also show up in the work of Weist \cite[Thm. 5.4]{Weist2012}.
Let $K_{n,n+1}$ be the complete bipartite graph with $n$ sources and $n+1$ sinks.
There are $a(n)$ spanning trees such that every source has exactly $2$ incident edges.
As $a(n)$ is also related to computing the Euler characteristic of certain moduli spaces,
we ask if it perhaps is related to what we discuss in \cref{seq:wpConnection} below.
For a sequence $\wvec$, let $C_{\wvec}$ be the total number of $\ttc$'s in $\wvec$,
$R_{\wvec}$ be the total number of $\ttr$'s in $\wvec$
and $\hor(\wvec) \coloneqq C_{\wvec}-R_{\wvec}$.
For example,
\[
C_{\mathtt{rcrcc}}=3, \quad
R_{\mathtt{rcrcc}}=1 \text{ and } \hor(\mathtt{rcrcc})=3-2=1.
\]
Intuitively, $\hor(\wvec)$ measures how ``horizontal'' the diagram is,
and $|\hor(\wvec)|$ is smaller for ``straigher'' shapes.
The following theorem shows that straighter diagrams
admit a larger number of decompositions, in a precise sense:
\begin{theorem}\label{thm:straighterInequality}
If $\vvec$ and $\wvec$ are sequences of length $k$ and $|\hor(\vvec)|<|\hor(\wvec)|$,
then
\[
|\BSD(\vvec,n)| < |\BSD(\wvec,n)| \text{ for $n$ sufficiently large.}
\]
In fact,
\[
\frac{|\BSD(\wvec,n)| - |\BSD(\vvec,n)|}{(n-k)!} = O(n^{2k-1}).
\]
\end{theorem}
\begin{proof}
From \cref{Polynomiality}, we know that for sufficiently large $n$, we have that
\[
\hat{f}_\vvec(n) \coloneqq |\BSD(\wvec,n)|\frac{(2k)!}{(n-k)!}
=\sum_{\sigma \in \BSP(\vvec,k)}(n+k-\des_k(\sigma))_{2k}.
\]
From \cref{cor:countingBST} we know that $|\BSP(\vvec,k)| = (2k)!/2^{2k}$.
It then follows that
\[
\hat{f}_\vvec(n)=\frac{(2k)!}{2^k} n^{2k} + \alpha n^{2k-1} + \text{l.o.t} \text{ and }
\hat{f}_\wvec(n)=\frac{(2k)!}{2^k} n^{2k} + \beta n^{2k-1} + \text{l.o.t}.
\]
Our goal is to prove that $\alpha<\beta$.
For a fixed permutation $\sigma \in \BSP(\vvec,k)$, its contribution to $\alpha$ is given by
\[
\sum_{i=0}^{2k-1} (k-\des_k(\sigma)- i ) = 2k^2-k(2k-1)-2k\des_k(\sigma) = k -2k\des_k(\sigma) .
\]
Hence, by summing over all permutations,
\[
\alpha = k|\BSP(\vvec,k)| - 2k \sum_{\sigma \in \BSP(\vvec,k)} \des_k(\sigma).
\]
As $|\BSP(\vvec,k)|$ does not depend on $\vvec$, the only part depending on $\vvec$ is
\[
J_\vvec \coloneqq \sum_{\sigma \in \BSP(\vvec,k)} \des_k(\sigma),
\]
and it suffices to prove that $J_\vvec$ increases as $|\hor(\vvec)|$ decreases.
To do this, we count the number of permutations where $b+k$ is
a $k-$descent with $a$, for $1\leq a****j$.
\begin{lemma}[Adaptation of Xiang \cite{ZiqingXiang294267}]
The cardinality of $\BSD(\ttc^n, n)$ is given by the formula
\begin{equation}\label{eq:sumAsGraphs}
|\BSD(\ttc^n, n)| = \sum_{p \vdash n} (-1)^{|p - 1|} \frac{1}{m!} \binom{|p|}{p} \binom{|p + 1|}{p + 1},
\end{equation}
where $m=(m_1,m_2,\dotsc,m_k)$ and $m_i$ is the multiplicity of $i$ in $p$,
and we use the notation
$p\pm 1 \coloneqq (p_1 \pm 1,\dotsc,p_k \pm 1)$ and $|p| = p_1+\dotsb + p_k$.
Note that $\binom{|p|}{p}$ and $\binom{|p + 1|}{p + 1}$ are multinomial coefficients.
\end{lemma}
\begin{proof}
For a permutation $\sigma\in \symS_{2n}$ corresponding to a \emph{border-strip tableau},
let $\Gamma_\sigma$ be the graph on the vertex set $[n]$ with edge set
\[
\{ (\sigma(i)-n,\sigma(i+1)) : \sigma(i)-n>\sigma(i+1) \}.
\]
Let $G$ be the set of graphs obtained from such border-strip tableaux.
Let $E$ be $\binom{[n]}{2}$, that is, the set of all possible edges
on the vertex set $[n]$ and let $G(e_1,\dotsc,e_r) \subseteq G$
be the set of graphs that include the edges $\{e_1,\dotsc,e_r\}\subseteq E$.
We have that elements in $\BSPD(\ttc^n,n)$ are in bijection with $G(\emptyset)$,
and \cref{CountingBSD} tells us that
\[
|\BSD(\ttc^n,n)| = G \setminus \left( \bigcup_{r=1}^n \bigcup_{e_1,\dotsc, e_r \in E} G(e_1,\dotsc,e_r) \right).
\]
Using the inclusion-exclusion principle, it follows that
\[
|\BSD(\ttc^n,n)| = |\BST(\ttc^n,n)|-\sum_{e_1\in E} |G(e_1)|
+ \sum_{e_1,e_2\in E} |G(e_1,e_2)|- \dotsb .
\]
We then observe that these graphs are characterized by
the connected components induced by the forced edges $e_1,\dotsc,e_r$,
determining an integer partition $p$ of $n$.
Furthermore, the sign in the above formula only depends on the number of forced edges,
which is equal to $|p-1|$, so we can transform this into a sum over all partitions of $n$.
Given a partition $p \vdash n$, the number of graphs with component sizes $p_1,p_2,\dotsc,p_k$
is given by $\frac{1}{m!} \binom{|p|}{p}$, with $m$ given as above.
\noindent
\emph{Claim:} Let $e_1,e_2,\dotsc,e_r$ be fixed edges such that the component sizes are given by $p$.
Then
\[
G(e_1,\dotsc,e_r) = \binom{|p + 1|}{p + 1}.
\]
\emph{Proof:}
Suppose $\Gamma_\sigma \in G(e_1,\dotsc,e_r)$ has a component $(i_1,i_2,\dotsc,i_j)$, in increasing order.
From \cref{InjectionToSm}, we know $\sigma^{-1}(i_s)<\sigma^{-1}(i_s+n)$ for
all $1\leq s\leq j$, and for $(i_1,i_2,\dotsc,i_j)$ to be connected,
we need $i_s +n$ to form an $n$-descent with $i_{s-1}$ for
all $1**~~ 0 \\ m_1+\dotsb+m_k=n-3 }} \binom{n-3}{m_1,\dotsc,m_k} \binom{n-3+k}{m_1+1,\dotsc,m_k+1}.
\end{equation*}
\end{proposition}
We are now ready to prove the following connection
between the sequence $v(n)$ and border-strip decompositions.
\begin{theorem}\label{thm:2nxn}
Let $a(n)$ be defined inductively by $a(0)=1$ and
\begin{equation}\label{eq:2nxnRecurrence}
a(n) = \frac{1}{2} \sum_{i=1}^n \frac{ i(n - i + 1)}{ (n + 2)} \binom{n - 1}{i - 1}
\binom{n + 3}{i + 1} a(i - 1) a(n - i)
\end{equation}
and let $v_n$ be given as in \eqref{eq:zograf}.
Then $a(n) = v_{n+3} = |\BSD(\ttc^n ,n)|$.
\end{theorem}
\begin{proof}
The first equality, $v_{n+3} = a(n)$ follows from comparing \eqref{eq:zograf} and \eqref{eq:2nxnRecurrence}.
It is a straightforward calculation to verify that they are equal.
To get the second identity, note that we can get the formula in \cref{prop:KaufmannFormula}
from \cref{eq:sumAsGraphs}
by replacing integer partitions with integer compositions, and then refining the sum over
the number of parts, denoted by $k$ in \cref{prop:KaufmannFormula}.
\end{proof}
\section{Further directions}
Given the connection with Euler characteristics of
moduli spaces mentioned after \cref{cor:totalNumberOfBorderStripDecomps},
and the connection with moduli spaces in \cref{thm:2nxn}, is there
a generalization of this mysterious connection? For example, there are formula for the
volumes of surfaces of other genus; see Matone \cite{Matone2001}.
Another interesting direction is to consider the $q$-analogue of
border-strip tableaux rather than decompositions.
\section{Acknowledgments}
The authors are thankful for the observation made by Ziqing Xiang \cite{ZiqingXiang294267}.
We also thank Richard Stanley for pointing out the work by Igor Pak \cite{Pak2000Ribbon},
and Justin Troyka for pointing out an error in an earlier draft.
We are also grateful for the comments by the anonymous referee.
P. A.\ is funded by the \emph{Knut and Alice Wallenberg Foundation} (2013.03.07).
\bibliographystyle{jis}
\begin{thebibliography}{10}
\bibitem{Beauquier1995}
D. Beauquier, M. Nivat, E. Remila, and M. Robson, Tiling
figures of the plane with two bars, {\em Comput. Geom.} {\bf 5}
(1995), 1--25.
\bibitem{FominLulov1997}
S. Fomin and N. Lulov, On the number of rim hook tableaux, {\em
J. Math. Sci. (N.Y.)} {\bf 87} (1997), 4118--4123.
\bibitem{Kaufmann1996}
R. Kaufmann, Y. Manin, and D. Zagier, Higher {W}eil-{P}etersson volumes
of moduli spaces of stable $n$-pointed curves, {\em Comm. Math. Phys.} {\bf 181} (1996), 763--787.
\bibitem{Matone2001}
M. Matone, Multi-instanton measure from recursion relations in ${N}=2$
supersymmetric {Y}ang-{M}ills theory, {\em J. High Energy Phys.}
{\bf 04} (2001), 0--41.
\bibitem{Murnaghan1937}
F. Murnaghan, The characters of the symmetric group, {\em Amer. J. Math.} {\bf 59} (1937), 739--753.
\bibitem{Nakayama1940}
T. Nakayama, On some modular properties of irreducible representations of
a symmetric group. {I} and {II}, {\em Japan J. Math.} {\bf 17} (1940),
165--184, 411--423.
\bibitem{Pak2000Ribbon}
I. Pak, Ribbon tile invariants, {\em Trans. Amer. Math. Soc.} {\bf 352} (2000), 5525--5562.
\bibitem{OEIS}
N.~J.~A. Sloane et al.,
The {O}n-{L}ine {E}ncyclopedia of {I}nteger {S}equences, 2019.
Available at \url{https://oeis.org}.
\bibitem{StanleyEC2}
R.~P. Stanley, {\em Enumerative {C}ombinatorics:}, {V}olume 2, Cambridge
University Press, 1st edition, 2001.
\bibitem{Weist2012}
T. Weist, On the {E}uler characteristic of {K}ronecker moduli spaces,
{\em J. Algebraic Combin.} {\bf 38} (2012), 567--583.
\bibitem{ZiqingXiang294267}
Z. Xiang, Rim hook decomposition and volume of moduli spaces, MathOverflow.
\newblock \url{https://mathoverflow.net/q/294267} (version: 2018-03-03).
\bibitem{Zograf1993}
P. Zograf, The {W}eil-{P}etersson volume of the moduli spaces of punctured
spheres, {\em Cont. Math.} {\bf 150} (1993), 367--372.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05A15; Secondary 97N70, 05A05.
\noindent \emph{Keywords:}
border-strip decomposition, permutation, $q$-analogue,
Weil-Petersson volume, rectangular shape.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A066319},
\seqnum{A115047}, and
\seqnum{A227404}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received May 28 2018;
revised version received June 10 2019.
Published in {\it Journal of Integer Sequences}, June 28 2019.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}
~~