\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<b$ where $b-a+1$ is the number of boxes in $B$.
Define the \emph{head}, $\head{B}$, of a border-strip 
to be the unique box where $j-i$ is maximal, and its \emph{tail}, $\tail{B}$, 
to be the unique box which minimizes $j-i$.
In \eqref{eq:headTail}, the head and tail boxes have been marked.
\begin{align}\label{eq:headTail}
\begin{ytableau}
\none\, & \none & \none & \none & H \\
\none & \none & \, & \, & \, \\
\none & \none & \,  \\
T & \, & \, \\
\end{ytableau}
\end{align}



\subsection{Simple diagrams and permutations}

In this subsection, we introduce a natural family of diagrams 
with particularly nice properties.  We first describe a bijection 
between border-strip decompositions of simple diagrams and certain permutations. 


\begin{definition}\label{simple diagram}
A \emph{simple diagram} is parameterized by $(\wvec,n)$ 
where $\wvec$ is a finite sequence of elements in $\{ \ttr, \ttc \}$
and $n$ is a natural number. 
The family of simple diagrams is defined recursively as follows:

\begin{itemize}
 \item If $\wvec = \emptyset$, then $(\wvec,n)$ is the $n\times n$-square.
 \item The diagram $(\ttc \wvec,n)$ is obtained from $(\wvec,n)$ by adding 
 an additional column of size $n$ on the left, such that the bottom-most 
 square of the new column is in the bottom-most row of $(\wvec,n)$.
 
  \item The diagram $(\ttr \wvec,n)$ is obtained from $(\wvec,n)$ by adding 
 an additional row of size $n$ on the bottom such that the left-most 
 square of the new row is in the leftmost column of $(\wvec,n)$.
\end{itemize}
\end{definition}

Let $\BSD(\wvec,n)$ denote the set of border-strip 
decompositions of $(\wvec, n)$ with strips of size $n$,
and $\BST(\wvec,n)$ denote the set of border-strip 
tableaux of $(\wvec, n)$ with strips of size $n$.


\begin{example}
The simple diagram determined by $(\mathtt{rcrcc},2)$ is the diagram on the left below.
We can see how $(\mathtt{rcrcc},2)$ is constructed from the $2\times 2$ 
square by adding successively the blue, red, green, yellow, and gray boxes to a $2\times2$ square.
\begin{align}
\ytableausetup{centertableaux,boxsize=1.0em}
\begin{ytableau}
\none & & & &\\
& & & &\\
&  & \\
& 
\end{ytableau}
\qquad  
\begin{ytableau}
\none &*(red) \ttc &*(blue) \ttc & &\\
*(yellow) \ttc &*(red) \ttc &*(blue) \ttc & &\\
*(yellow) \ttc &*(green) \ttr & *(green) \ttr \\
*(gray) \ttr & *(gray) \ttr
\end{ytableau}
\qquad 
\begin{ytableau}
\none & & & &\\
& & 4 & 5 & 6\\
& 2 & 3 \\
& 1
\end{ytableau}
\end{align}
Given a simple diagram $D$, the shape $(\wvec,n)$ can be recovered
as follows. First, $n$ is given by the smallest number of boxes in a single row, or column.
Secondly, $k$ can be found by using the fact that $n^2+kn$ is the total number of boxes in the diagram.
We then start in the $n$th square in the bottom-most row of $D$
and follow the outline of the diagram by going right if possible and up otherwise, 
until $k+1$ squares have been visited.
The path in the example above is \emph{up, right, up right right},
which correspond to the word $\mathtt{rcrcc}$.
\end{example}


\begin{definition}\label{def:comparable}
In a fixed border-strip decomposition, a border-strip $B_a$ is \emph{above} 
a border-strip $B_b$ if there is a box $a$ of $B_a$, 
and a box $b$ of $B_b$ such that the column index of $a$ is smaller or 
equal to the column index of $b$, and the row index of $a$ is 
smaller or equal to the row index of $b$. 
If $B_a$ is above $B_b$, we say that $B_b$ is \emph{below} $B_a$.


A border-strip $B_a$ is \emph{inner} to a border-strip $B_b$ if 
there exists a sequence $B_a=B_1,B_2,\dotsc,B_k=B_b$ such 
that $B_i$ is above $B_{i+1}$ for all $i =1,2,\dotsc,k-1$. 
It means the relation \emph{inner} is the 
transitive closure of the relation \emph{above}.
If $B_a$ is inner to $B_b$, then $B_b$ is \emph{outer} to $B_a$.
Two border strips $B_a$ and $B_b$ are \emph{comparable}, if $B_a$ is inner or outer to $B_b$.
\end{definition}



\begin{remark}
If $B_1$ is above $B_2$, it implies $B_1$ must contain a 
smaller number than $B_2$ in any border-strip tableau.
This observation proves that the transitive closure of ``above'' is well-defined.
\end{remark}

\begin{example}
An example of a border-strip decomposition in $\BSD(\mathtt{ccrcc},3)$
is given in \eqref{eq:abovebelowinner}.
The blue strip is above the red one and the red strip is above 
the yellow one. Hence the blue strip is inner to 
the yellow strip and the blue and yellow strips are comparable. 
Note that the blue strip is neither above nor below the yellow strip.
\begin{align}\label{eq:abovebelowinner}
\ytableausetup{centertableaux,boxsize=1.0em}
\begin{ytableau}
\none & \none &*(gray) & *(gray)& *(blue) & *(blue) & *(blue)\\
*(green)& *(green)&*(gray) & *(red) & *(red) & *(red) &*(brown)\\
*(green) & *(yellow)& *(yellow) & *(yellow) & *(black)&*(brown)&*(brown)\\
*(orange)&*(orange)&*(orange)&*(black)&*(black)
\end{ytableau}
\qquad  
\end{align}
\end{example}


\begin{definition}[Diagonal labeling]\label{def:diagLabeling}
For a sequence $\wvec$ of length $k$, 
we label the diagonals of the simple diagram $(\wvec, n)$ from $n+k$ to $1$, 
starting from the top right corner as shown in the example below for $(\mathtt{crrc},3)$:
\begin{align*}
\ytableausetup{centertableaux,boxsize=1.0em}
\begin{ytableau}
\none 3&4 &5 &6 &7\\
\none2 1& 3& 4&5 &6\\
1& 2& 3&4 &5\\
&1 & 2&3\\
& &1 &2
\end{ytableau}
\end{align*}
\end{definition}

\begin{lemma}\label{lem:headsGiveTheBSD}
Let $\wvec$ be a sequence of length $k$. 
Then for any decomposition $B \in \BSD(\wvec,n)$ 
there is a unique head in each diagonal from $1$ to $n+k$ and the positions of 
the heads uniquely determine $B$.
\end{lemma}
\begin{proof}
We show that the positions of the heads uniquely determine the decomposition
by processing the diagonals one by one and iteratively prolonging the strips, 
starting from diagonal $n+k$.

First, the single box in diagonal $n+k$ must be the head of some strip.
For diagonal $i$ with $k<i<n+k$ there is one box more in diagonal $i$ compared to 
diagonal $i+1$. All strips we already encountered have fewer than $n$ boxes and must continue
in diagonal $i+1$. Hence, there is exactly one head in diagonal $i$. 
Moreover, the position of the head $H$ in diagonal $i$ determines the continuation of 
the strips encountered as shown in the following figure:
\begin{align}
\begin{ytableau}
 *(blue) a\\
\none & *(yellow) b\\
\none & *(green) H & *(red) c\\
\none & \none & \none &*(orange) d\\
\none & \none & \none & \none
\end{ytableau}
\qquad
\substack{ \\ \longrightarrow  }
\qquad
\begin{ytableau}
*(blue) & *(blue) a\\
\none  & *(yellow)  & *(yellow) b\\
\none & \none & *(green) H & *(red) c\\
\none & \none & \none & *(red)&*(orange) d\\
\none & \none & \none & \none  &*(orange)
\end{ytableau}
\end{align}
For $i\leq k$ there is exactly one strip ending in diagonal $i+1$.
Furthermore, diagonals $i$ and $i+1$ have the same size, therefore there must be exactly 
one head in diagonal $i$. 
Once the heads have been placed there are $n-1$ boxes left 
in diagonal $i$ and $n-1$ strips which must have a box in diagonal $i$. 
Consequently there is at most one way to extend the strips to diagonal $i$.

The diagonals below diagonal $1$ decrease in size by one in each step
and it is easy to see that there cannot be any heads below diagonal $1$. 
There is a unique way to extend the partial border-strip decomposition
from diagonal $1$ to the entire diagram.
\end{proof}



Given a border-strip decomposition of a simple diagram,
the unique strip with head in diagonal $i$ 
is referred to as \emph{strip $i$}.
\begin{proposition}\label{comparable}
Let $(\wvec, n)$ be a simple diagram with $\wvec$ of length $k$ and $B \in \BSD(\wvec,n)$. 
If $1\leq i < j \leq n+k$ and $j-i\leq n$ then strip $i$ and strip $j$ in $B$ are comparable.
\end{proposition}
\begin{proof}
The tail of $j$ is at most one diagonal higher than the head of $i$.
From this observation, it follows that the strips must be comparable.
\end{proof}


We notice in \cref{lem:headsGiveTheBSD} that the positions 
of the heads of the strips determine the
border-strip decomposition uniquely. The next definition and proposition
encodes the placements of the heads as a permutation with certain restrictions,
giving an alternative description of \emph{border-strip tableaux} of simple diagrams.
Further down, we add additional restrictions so that the resulting set of permutations 
is in bijection with the set of \emph{border-strip decompositions} of simple diagrams.


\begin{definition}
Define $\psi: \BST(\wvec,n)\rightarrow \symS_{n+k}$ so that $\psi(T) = \sigma$ 
where $\sigma(j)$ is the diagonal containing the head of the strip labeled with $j$.
Let $\BSP(\wvec,n) \subseteq \symS_{n+k}$ denote the image of $\BST(\wvec,n)$ under $\psi$.
\end{definition}


\begin{example}
Consider the following $T \in \BST(\mathtt{ccc},n)$.
The strip labeled $1$ has its head in diagonal $3$, thus $\psi(T)(1) = 3$. 
The strip labeled $2$ has its head in diagonal $2$, so $\psi(T)(2)=2$.

\begin{align}
T=
\ytableausetup{centertableaux,boxsize=1.0em}
\begin{ytableau}
1 & 1 & \mathbf{1} & 3 & \mathbf{3} & \mathbf{4} \\
2 & 2 & \mathbf{2} & 3 & 4 & 4 \\
5 & 5 & \mathbf{5} & 6 & 6 & \mathbf{6}
\end{ytableau}
\qquad  
\text{ and }
\qquad
\psi(T) = [3,2,5,6,1,4] \in \symS_{6}.
\end{align}
\end{example}



\begin{proposition}\label{injectivity}
The map $\psi$ is injective. 
In particular, $\psi:\BST(\wvec,n) \to \BSP(\wvec,n)$ is a bijection.
\end{proposition}
\begin{proof}
A permutation $\sigma \in \BSP(\wvec,n)$ determines the values of the heads,
and thus the set of values of all the boxes in each diagonal. 
As the entries in diagonals have to be increasing, $\sigma$ uniquely determine 
the corresponding border-strip tableau.
\end{proof}


\begin{proposition}\label{InjectionToSm}
Let $\wvec = (w_1,\dotsc,w_k)$ be a sequence of length $k$. 
A permutation $\sigma \in \symS_{n+k}$ is in $\BSP(\wvec,n)$ 
if and only if for all $i$ with $1\leq i\leq k$ 
we have
\begin{enumerate}[label=(\alph*)]
 \item
$\sigma^{-1}(i) <\sigma^{-1}(n+i)$ whenever $w_i=\ttc$, and
 \item
$\sigma^{-1}(i) >\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<j$ form an inversion if and only if $j-i<n$ and $\sigma^{-1}(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<n$ they share an element on the same diagonal and if $\sigma^{-1}(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<j-i<n \text{ and } \sigma^{-1}(i)>\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<b\leq k$ fixed 
(i.e.,\ we have $\dotsc,b+k,a,\dotsc$ in the permutation). 
To create such a permutation, we can choose the 
order of all elements different from $a,b,a+k,b+k$ in any way respecting the orders 
of pairs $\sigma(i),\sigma(i+k)$, which gives $(2k-4)!/2^{k-2}$ choices. 
Then we must choose the order of the three blocks $a+k,(b+k)a,b$. If $a+k$ and $b$ 
are on the same side of $(b+k)a$, this gives two possibilities, otherwise there is 
only one way. We observe $a+k$ and $b$ are 
on the same side if and only if $\vvec_a \neq \vvec_b$. 
Finally, we can chose the position of the three blocks $a+k,b,(b+k)a$, which gives $\binom{2k}{3}$ choices. 
So the number of permutations where $b+k$ is a $k$-descent with $a$ is exactly 
\[
\begin{cases}
2\binom{2k}{3}(2k-4)!/2^{k-2}, & \text{if $\vvec_a \neq \vvec_b$}; \\
\phantom{2}\binom{2k}{3}(2k-4)!/2^{k-2}, & \text{otherwise}.
\end{cases}
\]
Recall $C_\vvec$ is the number of $\ttc$'s in $\vvec$ and $R_\vvec$ 
is the number of $\ttr$'s in $\vvec$. 
The previous argument implies
\[
J_\vvec=\binom{2k}{3}\frac{(2k-4)!}{2^{k-2}} \left[ 
\binom{C_\vvec}{2} + 2C_\vvec R_\vvec +  \binom{R_\vvec}{2}
\right].
\]
Since $R_\vvec=k-C_\vvec$ it follows that 
\[
\binom{C_\vvec}{2} + 2C_\vvec R_\vvec +  \binom{R_\vvec}{2} = \binom{k}{2} + C_\vvec R_\vvec
\]
which increases as $|\hor(\vvec)|$ decreases. This implies the theorem.
\end{proof}

\begin{conjecture}
The function $f_\wvec(n)$ uniquely determines $\wvec$ up to isometry of the diagram $\wvec$,
i.e.,\ up to exchanging $\ttr$ and $\ttc$ and reversing the sequence.
\end{conjecture}
Note that for fixed $k$, the polynomials (in $n$) $\left\{ (n+k-i)_{2k} \right\}_{i=0}^{k-1} $
are linearly independent. They span the same space as
\[
\left\{ \frac{(n+i)_{2k}}{(2k)!} \right\}_{i=1}^k \quad = \quad
\left\{ \binom{n+i}{2k} \right\}_{i=1}^k
\]
and the latter collection of polynomials can be seen to be linearly independent.

As a consequence, given $f_\wvec(n)$, which is a sum over permutations in $\BSP(\wvec,k)$,
for any $i$ we can extract the number of permutations $\sigma \in \BSP(\wvec,k)$ with $\des_k(\sigma)=i$.
Hence, the conjecture is reduced to determining if the multi-set of $\des_k$-values 
of the elements in $\BSP(\wvec,k)$ uniquely determines $\wvec$ up to isometry.

In particular, if the number of terms without $k$-descents is different, 
the polynomial is also different, so we can formulate the stronger 
conjecture that $|\BSD(\wvec,k)|$ uniquely determines a sequence $\wvec$ of length $k$ up to isometry.




\section{A connection with the Weil-Petersson volume}\label{seq:wpConnection}

We let $\ttc^n$ denote the simple shape which is a rectangle of width $2n$ and height $n$.
It follows from \cref{cor:SimpleBSDCharacterization} that 
the set $\BSD(\ttc^n, n)$ is in bijection with
the set of permutations of $\{x_1,\dotsc,x_n,y_1,\dotsc,y_n\}$
such that $x_i$ appears before $y_i$ for all $i$,
and we do not have $\dotsc,x_i,y_j,\dotsc$ (consecutive), such that $i>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<s\leq j$ i.e.,\ $\sigma^{-1}(i_s+n)=\sigma^{-1}(i_{s-1})-1$.

Together these two statements imply that $\sigma$, has the following structure:
\begin{align*}
 \sigma^{-1}(i_j)<\sigma^{-1}(i_j+n) \lessdot \sigma^{-1}(i_{j-1}) < \sigma^{-1}(i_{j-1}+n) \lessdot \dotsb \\
\dotsb  <\sigma^{-1}(i_{3}+n)\lessdot \sigma^{-1}(i_{2}) < \sigma^{-1}(i_{2}+n) \lessdot \sigma^{-1}(i_{1})<
\sigma^{-1}(i_{1}+n)
\end{align*}
where $a \lessdot b$ means that $a+1=b$. Thus, we have $j+1$ \emph{blocks}, 
\[
 [\sigma^{-1}(i_j)],\;  
 [\sigma^{-1}(i_{s+1}+n) \lessdot \sigma^{-1}(i_{s})] \text{ for $s=1,\dotsc,j-1$}
 \text{ and } [\sigma^{-1}(i_1+n)]
\]
which need to appear in order, but there is no further restriction.
The number of $\Gamma_\sigma$ with component 
sizes determined by $p$ is therefore $\binom{|p + 1|}{p + 1}$, which concludes the proof.
\end{proof}


Let us now dive into a completely different part of mathematics.
We shall not use the following definition and we omit many details.
The important part is \cref{thm:zograf} further down.

The \emph{Weil-Petersson volume}, $\Vol_{WP}(\cdot)$,
is defined as
\[
\Vol_{WP}(M) \coloneqq \frac{1}{(n-3)!}\int_{M} \wedge^{n-3}(\omega_{M}),
\]
where $\omega M$ is the Weil-Petersson symplectic form on the manifold $M$.
A special type of manifold is $M_{0,n}$,
which denotes the moduli space of an $n$-punctured Riemann sphere, that is
\[
 M_{0,n} \coloneqq \{ (z_1,\dotsc,z_n) \in 
 \hat{\setC}^n\ : z_i \neq z_j\} / \symS_n \times \mathrm{PSL}(2,\setC) 
\]
and $\symS_n$ acts by permuting variables, 
and $\mathrm{PSL}(2,\setC)$ acts as a linear fractional transformation.


\begin{theorem}[Zograf \cite{Zograf1993}]\label{thm:zograf}
The Weil-Petersson volume of the moduli space of an $n$-punctured Riemann sphere $M_{0,n}$ is given by the formula
\[
\Vol_{WP}(M_{0,n}) = \frac{\pi^{2(n-3)} v_{n}}{n!(n-3)!}, \text{ for $n\geq 4$},
\]
where the sequence $(v_n)_{n=3}^{\infty}$ is defined via the recursion
\begin{align}\label{eq:zograf}
v_3=1, \qquad 
v_n = \frac{1}{2}\sum_{i=1}^{n-3}
\frac{ i(n - i -2)}{n-1}
\binom{n - 4}{i - 1} \binom{n}{i + 1} v_{i +2} v_{n - i}, \qquad n\geq 4.
\end{align}
\end{theorem}
This sequence shows up as \seqnum{A115047} in the OEIS \cite{OEIS},
see Kaufmann, Manin, and Zagier \cite{Kaufmann1996} and Matone \cite{Matone2001} for more background.
In the paper by Kauffman et al.,\ \cite{Kaufmann1996} the following relationship is shown.
\begin{proposition}\label{prop:KaufmannFormula}
Let the sequence $v_n$ be defined as in \eqref{eq:zograf}.
Then 
\begin{equation*}
v_n = \sum_{k=1}^{n-3} \frac{(-1)^{n-3-k}}{k!} \!\!\!\!
\sum_{\substack{m_1,\dotsc,m_k > 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}