\documentclass[submission]{FPSAC2019}

\articlenumber{103}
\addbibresource{103.bib}

\usepackage{enumerate, amsfonts, mathrsfs, mathabx, booktabs, xspace}
\usepackage[textsize=footnotesize]{todonotes}
\usepackage[utf8]{inputenc}

%% note that the class file already loads {amsmath, amsthm, amssymb}

\usepackage{tikz}
\usetikzlibrary{shapes,decorations.pathmorphing,calc,arrows}

%\usepackage[para]{footmisc}


\usepackage[colorlinks=true]{hyperref}
\numberwithin{equation}{section}
\usepackage{cleveref}

%\usepackage[backend=bibtex]{biblatex}
%\addbibresource{FPSAC2019.bib}


\usepackage{enumitem}
\setlist{noitemsep=-1pt}

\def\ZZ{\mathbb Z}
\newcommand{\Dfn}[1]{\emph{\color{blue}#1}} % to highlight and collect definitions
\newcommand{\Set}[1]{\ensuremath{\mathcal{#1}}} % for set
\newcommand{\Perm}{\Set{S}}

\newcommand{\ttFindStat}{{\tt FindStat}\xspace}%
\newcommand{\ttSageMath}{{\tt SageMath}\xspace}%
\newcommand{\ttOEIS}{{\tt OEIS}\xspace}%
\newcommand{\ttmathoverflow}{{\tt mathoverflow}\xspace}%
\newcommand{\FindStat}[1]{%
  \ifx&#1&%
  \url{www.findstat.org}% #1 is empty
  \else \url{www.findstat.org/#1}% #1 is nonempty
  \fi}%
\newcommand{\mathoverflow}[1]{%
  \ifx&#1&%
  \url{www.mathoverflow.net}% #1 is empty
  \else \url{www.mathoverflow.net/q/#1}% #1 is nonempty
  \fi}%

\newcommand{\OEIS}[1]{\url{www.oeis.org/#1}}
\newlength{\Stwidth}
\settowidth{\Stwidth}{\tt{St000000:}}
\newcommand{\stat}[3]%
{{\tt \makebox[\Stwidth][r]{#1:} #2 $\to\ZZ$}\\{\small #3}}
\newcommand{\map}[4]%
{{\tt \makebox[\Stwidth][r]{#1:} #2 $\xrightarrow{\text{#3}}$ #4}}

\newcommand{\newmap}[5]%
{\tt{#1}: & \tt{#2} & $\xrightarrow{\makebox[#5]{\tt{\scriptsize #3}}}$ & \tt{#4}}

\newcommand{\opgreek}[1]{\begingroup\mathgroup-1 #1\endgroup}
\DeclareMathOperator{\Mp}{\opgreek{\phi}}% I think we should use Mp here
\DeclareMathOperator{\St}{\opgreek{\beta}}% I think we should use St here
\newcommand{\coll}[1]{{\tt #1}}
\newenvironment{result}{\begin{quote}}{\end{quote}}

\numberwithin{equation}{section}
\theoremstyle{plain}
\newtheorem{lemma}[equation]{Lemma}
\newtheorem{theorem}[equation]{Theorem}
\newtheorem{conjecture}[equation]{Conjecture}
\newtheorem{corollary}[equation]{Corollary}
\newtheorem{proposition}[equation]{Proposition}
\newtheorem*{feature}{Feature}

\theoremstyle{definition}
\newtheorem{definition}[equation]{Definition}
\newtheorem{remark}[equation]{Remark}
\newtheorem{remarks}[equation]{Remarks}
\newtheorem{example}[equation]{Example}

\crefname{proposition}{Prop.}{Props.}
\crefname{corollary}{Cor.}{Cors.}
\crefname{theorem}{Thm.}{Thms.}
\crefname{equation}{Eq.}{Eqs.}

\Crefname{proposition}{Proposition}{Propositions}
\Crefname{theorem}{Theorem}{Theorems}
\Crefname{corollary}{Corollary}{Corollaries}
\Crefname{equation}{Equation}{Equations}

%% define your title in the usual way
\title{\ttFindStat\ -- a database and search engine \\ for combinatorial
statistics and maps}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[Martin~Rubey and Christian~Stump]{Martin
  Rubey\thanks{Supported by the Austrian Science Fund (FWF): P
    29275.}\addressmark{1} \and Christian Stump\thanks{Supported by
    DFG grants STU 563/2 ``Coxeter-Catalan combinatorics'' and STU
    563/4-1 ``Noncrossing phenomena in Algebra and
    Geometry''.}\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Fakult\"at f\"ur Mathematik und Geoinformation, TU Wien,
  Austria \\ \addressmark{2}Fakult\"at f\"ur Mathematik, Ruhr-Universit\"at Bochum, Germany}

%% put the date of submission here
\received{\today}

\abstract{%
  \ttFindStat is a collaborative online database of combinatorial statistics on combinatorial collections and of maps between such collections.
  A search engine allows users to identify statistics and maps given a few known values, using for example the web interface.
  As of April 2019, the database contains 1387 statistics and 146 maps on 18 collections by 70 contributors.
}

\begin{document}
\maketitle

\section{Introduction}

The \emph{On-Line Encyclopedia of Integer Sequences} \ttOEIS~\cite{OEIS}
% proved to be
is an incredibly valuable tool in mathematical research.  As a \lq fingerprint database for theorems\rq\, it allows to identify interconnections and relations between theorems throughout mathematics~\cite{MR3113227}.

\medskip

In this spirit, \ttFindStat\ is a collaborative online database of combinatorial statistics on combinatorial collections and of combinatorial maps between such collections.
It is mainly used via its web interface which may be found at
\begin{center}
  \FindStat{}\ .
\end{center}
A \Dfn{(combinatorial) collection}\footnote{\FindStat{CollectionsDatabase}} is, for the purpose of this project and only loosely speaking, a collection $\Set C = \bigcup_n \Set C_n$ of finite ``combinatorial'' sets $\Set C_n$.
Examples are
\begin{itemize}
  \item the set of permutations of $\{1,\dots,n\}$,
  \item the set of integer partitions of~$n$,
  \item the set of binary words with $n$ letters, and
  \item the set of simple unlabelled graphs on $n$ vertices.
\end{itemize}
A \Dfn{(combinatorial) map} is a map $\phi:\Set C \to \Set C'$ between two such collections.
An example is
\begin{itemize}
  \item the map sending a permutation of $\{1,\dots,n\}$ to the integer partition of~$n$ given by its \emph{cycle type}\footnote{\FindStat{Mp00108}}.
\end{itemize}
Finally, a \Dfn{(combinatorial) statistic} is a map $st:\Set C\to\ZZ$.
Examples are
\begin{itemize}
  \item the \emph{number of descents} of a permutation\footnote{\FindStat{St000021}},
  \item the \emph{number of standard Young tableaux} of an integer partition\footnote{\FindStat{St000003}},
  \item the \emph{number of different cyclic shifts} of a binary word\footnote{\FindStat{St000543}},
  \item the \emph{maximal cardinality of a clique} in a simple unlabelled graph\footnote{\FindStat{St000097}}.
\end{itemize}

\noindent The fundamental idea of \ttFindStat is to
\begin{center}
  \emph{provide a tool for a computer-aided study of statistics on \\ combinatorial collections by taking into account combinatorial maps.}
\end{center}

\medskip

The question that started the project was: \emph{how to search the \ttOEIS for the number of descents of a permutation?}
A first attempt at an answer might be to
\begin{itemize}
  \item search for the generating function $\sum_{\pi \in \mathcal S_n}x^{\operatorname{des}(\pi)}$.
\end{itemize}
This works and reveals the \emph{Eulerian numbers}~\OEIS{A008292}.
But going from a statistic to its generating function means to ``ignore'' a lot of combinatorial information.
A second attempt could be to
\begin{itemize}
\item list all permutations in some order and then search for the resulting sequence.
\end{itemize}
Maybe the most obvious order is lexicographic.  Although this fails to reveal any information for the example at hand, the design of the \ttOEIS would in principle be capable of handling such queries.  It is clear, however, that this approach does not scale well.

\medskip

\noindent\ttFindStat\ provides, as its main application, the following feature.

\begin{feature}
  Given (a few values of) a combinatorial statistic $\alpha:\Set C\to\ZZ$,
  find combinatorial maps $\Mp_1:\Set C\to\Set C'$, $\Mp_2:\Set C'\to\Set C'', \Mp_3:\Set C''\to\Set C'''$, and a combinatorial statistic $\St: \Set C'''\to\ZZ$, all in the database, such that
  \begin{align}
    \alpha &= \St \circ \Mp_3 \circ \Mp_2 \circ \Mp_1.
    \tag{{\small search for values}}
    \intertext{The requirement of equality may be relaxed to requiring equidistribution on the finite ``pieces'' $\Set C_n$ of the collection $\Set C = \bigcup_n \Set C_n$.
  This is, for all~$n$,}
    \sum_{c\in\Set C_n} x^{\alpha(c)} &= \sum_{c\in\Set C_n} x^{\St \circ \Mp_3 \circ \Mp_2 \circ \Mp_1(c)}%\quad\text{for all $n$.}
    \tag{{\small search for distribution}}
  \end{align}
\end{feature}

We invite the reader to try this by visiting \FindStat{St000021} and to click on ``search for values'', and on ``search for distribution''.
\ttFindStat also supports a natural generalization of ``search for values'' and ``search for distribution'', and analogous features for maps are also available, see \FindStat{HowToUse} for details.

\subsection*{Accessing the database}

The dedicated website allows various ways of browsing the \ttFindStat\ database and to use its search engine.
We refer to \FindStat{HowToUse} for instructions and to \FindStat{CollectionsDatabase} for browsing the collections and their statistics and maps.
% 
% There are currently two ways to access the database.  The first is
% via the dedicated website, which works well also on smartphones or
% tablets.
% \todo{klingt billig in meinen Augen}
A second, more advanced possibility is to use the interface for the computer
algebra system \ttSageMath\footnote{\FindStat{SageInterface}}.
Of course, we explicitly encourage users of other computer algebra systems to also implement \ttFindStat\ interfaces.

\section{Usage examples}
\label{sec:usage}

\subsection{Identifying a statistic given a few values}

The original use case of \ttFindStat is to identify a statistic given
its values on a few elements of a collection.  For example, the following question was
raised on \ttmathoverflow\footnote{\mathoverflow{132338}}:
\begin{quote}
  I've come across a function from the set of integer partitions to
  the natural numbers which I don't recognise but which probably
  ought to be familiar.
\end{quote}
The function in question was given as $f(\emptyset)=1$ and
$f(\lambda)=\binom{i+j}{i} f(\mu)f(\nu)$, where $(i,j)$ are the
coordinates of a box such that $i+j$ is maximal, $\mu$ is obtained from $\lambda$ by removing the first $i$ rows, and $\nu$ is obtained by removing the first $j$ columns. It does not take
long to produce a few values of this statistic, for example
\begin{verbatim}
  [1] => 2,
  [2] => 3, [1,1] => 3,
  [3] => 4, [2,1] => 6, [1,1,1] => 4,
  [4] => 5, [3,1] => 8, [2,2]   => 6, [2,1,1] => 8, [1,1,1,1] => 5
\end{verbatim}
Querying the database using these values\footnote{\FindStat{StatisticFinder/IntegerPartitions}} yields a handful of matches.
Because so few values are given, some of these matches are
\emph{false positives}; they turn out not to match the given
definition.  However, we also obtain what we are looking for!
The following is equivalent to the accepted answer on
\ttmathoverflow:
\begin{center}
  \begin{tabular}{rccc}
    \newmap{Mp00043}{Integer partitions}{to Dyck path}{Dyck paths}{120pt} \\[5pt]
    \newmap{Mp00026}{Dyck paths}{to ordered tree}{Ordered trees}{120pt} \\[5pt]
    \newmap{St000085}{Ordered trees}{number of lin.\ extensions}{$\ZZ$}{120pt}
  \end{tabular}
\end{center}
This means: first traverse the boundary of the Ferrers diagram of the
partition from the bottom-left to the top-right to obtain a Dyck
path, prepending vertical and appending horizontal steps if necessary.
Then interpret the Dyck path as an ordered tree, using the
traditional preorder-traversal bijection.  Finally, return the number
of linear extensions of this tree.

\medskip

We emphasize in this example, that all involved maps and also the statistic are well-known and classical.
But it is unclear at a first glance that the given definition of a statistic matches the composition
\[
  \tt{St000085}\ \circ\ \tt{Mp00026}\ \circ\ \tt{Mp00043}\ .
\]
The \ttFindStat\ search engine enables the user to automatize such discoveries.

\subsection{Identifying an equidistributed statistic}

It may happen that the statistic of interest cannot be obtained as a
composition of maps and a statistic known to \ttFindStat.  In this
case one may check the relaxed condition whether an
\Dfn{equidistributed statistic} can be found.  For example, consider
the set $\Set T_n$ of (unordered, rooted) leaf-labelled binary trees
with $n+1$ leaves.  For a tree $T\in\Set T_n$, we are interested in the
statistic measuring the distance $d(T)$ of the leaf labelled $1$ from
the root.

Leaf-labelled binary trees are not a collection in the database, but
there is a well-known natural bijection $\mu:\Set M_n\to\Set T_n$
between $\Set M_n$, the set of perfect matchings of $\{1,\dots,2n\}$,
and these trees, see~\cite[Example 5.2.6]{MR1676282}.  However,
querying the database for the statistic $d\circ\mu$ on perfect
matchings does not yield any result.

\medskip

One may then try to find an equidistributed statistic.  In
the case at hand, we query the database for a statistic $\beta$ such that
\[
\sum_{M\in\Set M_n} x^{\beta(M)} = \sum_{M\in\Set M_n} x^{d\circ\mu(M)},
\]
and obtain the very promising coincidence
\begin{center}
  \begin{tabular}{rccc}
    \newmap{St000838}{Perfect matchings}{number of terminal right-hand endpoints}{$\ZZ$\ .}{180pt}
  \end{tabular}
\end{center}
% \begin{result}
%   \stat{St000838}{Perfect matchings}{%
%   The number of terminal right-hand endpoints when the vertices are written in order.}
% \end{result}
In the following, it is more convenient to use the statistic recording the number of \emph{initial left-hand endpoints} of a perfect matching when the vertices are written in order.
It is not hard to see that this statistic, regarded as a statistic $s(T)$ on leaf labelled binary trees using the bijection $\mu$, records the smallest label of a leaf whose
sibling is also a leaf, minus~$1$.

Thus, it remains to find a bijection $\tau:\Set T_n\to\Set T_n$  such
that $s(T) = d\circ\tau(T)$.  It turns out that this is not the end
of the story.  In fact, using a (not completely obvious) variation of the bijection $\mu$, one can prove, for all~$n$, that
\[
\sum_{T\in\Set T_n} x^{s(T)} y^{d(T)} =%
\sum_{T\in\Set T_n} x^{d(T)} y^{s(T)}.%,\quad\text{for all $n$}.
\]

\subsection{Refining equidistribution results}

Given two equidistributed statistics $\alpha$ and $\beta$, it may be interesting to find two further statistics $\gamma$ and $\delta$, such that even $(\alpha,\gamma)$ and $(\beta,\delta)$ have the same distribution, that is
\[
\sum_{c\in\Set C_n} x^{\alpha(c)} y^{\gamma(c)} =%
\sum_{c\in\Set C_n} x^{\beta(c)} y^{\delta(c)},\quad\text{for all $n$}.
\]

In the past, such refinements were often overlooked, as witnessed by the fact that the symmetry of the joint distribution of the number of crossings and the number of nestings in perfect matchings was discovered about 20 years after the equidistribution of the two statistics was first demonstrated.
Indeed, lacking a bijection that shows the equidistribution of $\alpha$ and $\beta$, how could one find statistics $\gamma$ and $\delta$ except by luck or great intuition?

\medskip

To illustrate, the following question was raised in the Viennese combinatorics seminar in November 2018:
\begin{quote}
  Are there any equidistribution results for triples of permutation
  statistics $(\varepsilon, \sigma, \mu)$, such that $\varepsilon$ is
  Eulerian (as, for example, the number of descents), $\sigma$ is a
  Stirling statistic (that is, equidistributed with the
  number of cycles) and $\mu$ is a Mahonian statistic (that is,
  equidistributed with the Major index)?
\end{quote}

One may use \ttFindStat to discover such coincidences.
Using the \ttSageMath interface, one compiles three lists containing the Eulerian statistics, the Stirling statistics and the Mahonian statistics, respectively.
One then checks for each pair from the first list whether there are two statistics from the second list refining the equidistribution,  by testing equality of the first few bivariate generating functions.
One then repeats this procedure with the third list and arrives at the following conjecture which has, to the best of our knowledge, not appeared in the literature.

\begin{conjecture}
  Let
\begin{itemize}
  \item $\operatorname{cyc}$ be the number of
    cycles\footnote{\FindStat{St000031}} and $\operatorname{sal}$ be
    the number of saliances\footnote{\FindStat{St000007}} of a
    permutation,
  \item $\operatorname{srt}$ be the sorting
    index\footnote{\FindStat{St000224}} and $\operatorname{ninv}$ be
    the number of non-inversions\footnote{\FindStat{St000246}} of a
    permutation, and
  \item $\operatorname{dfc}$ be the number of
    deficiencies\footnote{\FindStat{St000703}} and $\operatorname{leh}$
    be the number of repeated entries in the Lehmer
    code\footnote{\FindStat{St001298}} of a permutation.
  \end{itemize}
  Then
  \[
  \sum_{\pi \in \mathcal S_n}%
  x^{\operatorname{cyc}(\pi)}%
  y^{\operatorname{srt}(\pi)}%
  z^{\operatorname{dfc}(\pi)}%
  = \sum_{\sigma \in \mathcal S_n}%
  x^{\operatorname{sal}(\pi)}%
  y^{\operatorname{ninv}(\pi)}%
  z^{\operatorname{leh}(\pi)}.%
  \]
\end{conjecture}

\subsection{Two concrete research examples}

\subsection*{Guessing asymptotic behaviour}

In~\cite{ST2019}, Thomas Kahle and the second author present experimental investigations of the asymptotics of permutation statistics of the following form.
Assume \ttFindStat contains a permutation statistic $\beta : \Perm_n \longrightarrow \ZZ$ with all values given for $2 \leq n \leq N$ for some~$N$, say $N \in \{6, 7,8\}$.
One may then
\begin{itemize}
  \item compute the generating functions $\sum_{\pi \in \mathcal S_n}x^{\beta(\pi)}$ and the mean and variance of associated random variable $X_\beta^{(n)}$ for $2 \leq n \leq N$, and
  \item use Lagrange interpolation with the computed data points to guess (Laurent) polynomial formulas for the mean and variance of $X_\beta^{(n)}$ as a function of~$n$.
\end{itemize}
We refer to~\cite{ST2019} for concrete results and further considerations.

\subsection*{Finding bijective proofs}

In~\cite{MRS2018}, the authors and René Marczinzik give combinatorial interpretations of several homological properties of Nakayama algebras in terms of Dyck path statistics.
The starting point was that several generating functions for homological properties on Nakayama algebras were found in the \ttOEIS.
Moreover, a natural bijection between certain Nakayama algebras and Dyck paths is well-known.
Using \ttFindStat, we discovered bijections on Dyck paths that map these homological properties to classical Dyck path statistics.
We refer to~\cite{MRS2018} for details.

\subsection{Searching for keywords}

One of the most straightforward (and useful) ways to use \ttFindStat is to search
for a keyword.  In case you have forgotten how the precise definition
of a statistic or map goes, chances are good that you can identify it
using a suitable keyword.  This could be a word occurring in its name
(such as \lq promotion\rq), an algebraic structure you recall to be
necessary for the definition (such as \lq character\rq), or perhaps
a mathematician commonly associated with the statistic (such as \lq
Euler\rq).

\section{Status of the database}

The original version of the \ttFindStat\ database was initiated in August 2011 by Chris Berg and the second author.
At the previous FPSAC presentation in 2014, the database contained 175 statistics.
Since then, we putted a lot of effort into adding new statistics; over the past years \emph{we added roughly one statistic per day}.
We refer to \FindStat{Contributors} for a growth chart of the combinatorial statistics in the database.
As of April 2019, the database contains
\begin{center}
  \textbf{1387 statistics and 146 maps on 18 collections by 70 contributors}.
\end{center}
This allows to test any given statistic data against millions of compositions of maps $\Mp_1,\Mp_2,\Mp_3$ and statistics~$\beta$ of the form $\St \circ \Mp_3 \circ \Mp_2 \circ \Mp_1$ using the search engine.
For articles referencing the database and for additional ways of using it in research, we refer to \FindStat{Citations}.

\subsection{Perspectives}

The main challenge we need to tackle is that of scalability.
We would like to make many more combinatorial collections available, and we would like to include many more combinatorial maps.

\paragraph{More combinatorial collections.}

% As of March 2019, there are $18$ collections supported by \ttFindStat.
Technically, there are rather few prerequisites
necessary to add a new collection, and supporting a collection does
not cost much in terms of performance and memory.  However,
\ttFindStat works best with collections whose finite pieces have
moderate size (with \coll{Permutations} perhaps being a reasonable
upper bound).  Even more important is the availability of a number of
natural maps, which establish connections to the other collections in
the database.

\paragraph{More combinatorial maps.}

Adding more combinatorial maps poses larger technical difficulties.
Currently, upon initializing the database, \ttFindStat has to
\begin{itemize}
\item determine, for each collection, the set of elements that are
  actually considered when processing queries, and
\item precompute the compositions of all combinations of (currently)
  $4$~individual maps on these elements.
\end{itemize}
Unfortunately, adding new maps may result in a significant slowdown of this initialization process, and also a significant increase in memory usage.
It is one of our main short-term goals to solve this issue.

\subsection{Participation}

\textbf{This is a collaborative project}!
It is very simple to contribute to the database.
Everyone is welcome to add new statistics at \FindStat{NewStatistic}, suggest new combinatorial maps, enhance the wiki pages of the collections, and to propose improvements, suggestions and additional ideas.

\printbibliography

\end{document}
