For examples of scientific usage, you may consult a presentation that we compiled for the FPSAC 2019 conference.

The database

Collections

We call the set of combinatorial objects of some specific type a (combinatorial) collection. You can find the different combinatorial collections we consider in our collections database. While the collections we consider are infinite, they all are naturally decomposed into finite parts by what we call levels. For instance, there are infinitely many permutations, but for every level $n$, there are only finitely many permutations of the set $\{1,\dots,n\}$.

Statistics

A (combinatorial) statistic is a function $\mathsf{st}:\mathcal{C} \rightarrow \mathbb{Z}$, where $\mathcal{C}$ is a combinatorial collection. In our database we collect statistics that have some combinatorial significance (in a weak sense). You can see all the registered statistics in the statistics database.

Maps

A (combinatorial) map is a function $f: \mathcal C \rightarrow \mathcal C'$ between combinatorial collections $\mathcal C$ and $\mathcal C'$. As for statistics, we only consider maps have a combinatorial significance (again in a weak sense). This could mean the map is defined by natural properties of the collections (e.g. the dual poset of a poset Mp00125 or the shape of a standard tableaux Mp00083) or that it has significance in research (e.g. the Foata bijection on permutations Mp00067). You can see a list of all registered maps in our maps database.

Data storage

Statistics and maps are stored in the database as a finite amount of its images (and not as an algorithm that generates it). As a consequence, statistics or maps can only be found on the images that are provided. If you notice missing values that you know, we encourage you to add them to the database in order to make them accessible to others.

The FindStat search engine

In addition to providing access to the stored data in the database, the FindStat engine takes into account compositions of maps such as the inverse of the reverse of a permutation

MapsDatabase/Mp00066oMp00064

and statistics that are reached via compositions of maps such as the number of descents of the inverse of the reverse of a permutation

StatisticsDatabase/St000021oMp00066oMp00064.

The search engine can of course not take infinitely many compositions into account.

Map weights

Each map has an assigned weight that you can see when visiting the page of the specific map. For instance, the Foata bijection has weight 21. The weight of a composition of maps is the sum of their weights. The engine computes all valid compositions of weight at most 100. Weights are chosen by hand in a way to maximize the number of "interesting" compositions while keeping the (otherwise exponentially growing) total number of compositions manageable.

Newly submitted maps always are assigned a weight of 51. Since the computation time of all compositions is very sensitive to weight changes, these can only be changed by editors.

Composition identities

We also compute identities between map compositions of the form $f_1 \circ \dots \circ f_k = g_1 \circ \dots \circ g_\ell$ based on the information of the given finitely many images. You can see them when clicking on show experimental identities, for example at MapsDatabase/Mp00064.

Please note that the displayed identities are only computed on a finite number of element-image-pairs and not on the abstract maps. This is why we call them experimental.

Using the finder

(The map finder works similarly to the statistic finder which we discuss below. Feel free to try to search for your favorite map from Dyck paths to permutations.)

Searching for statistics

Given some data for a statistic $\mathsf{st}: \mathcal{C} \rightarrow \mathbb{Z}$, the statistic finder searches its database for possible compositions of statistics and maps matching the given data.

Example

Imagine you have some data for a statistic $\mathsf{st}:$ Dyck paths $= \mathcal{D} \longrightarrow \mathbb{Z}$:

$$\begin{align} [1, 0, 1, 0, 1, 0, 1, 0] &\mapsto 16 \\ [1, 0, 1, 0, 1, 1, 0, 0] &\mapsto 5 \\ [1, 0, 1, 1, 0, 0, 1, 0] &\mapsto 6 \\ [1, 0, 1, 1, 0, 1, 0, 0] &\mapsto 3 \\ [1, 0, 1, 1, 1, 0, 0, 0] &\mapsto 1 \end{align}$$

and you are interested in finding a combinatorial interpretation. The statistic finder can point you in the right direction.

You go to StatisticFinder?Domain=DyckPaths and input the data by assigning to the Dyck path $[1,0,1,0,1,0,1,0]$ the value $16$ etc. Alternatively, you can click on all-at-once and provide your data there in the following way:

[1, 0, 1, 0, 1, 0, 1, 0] => 16
[1, 0, 1, 0, 1, 1, 0, 0] => 5
[1, 0, 1, 1, 0, 0, 1, 0] => 6
[1, 0, 1, 1, 0, 1, 0, 0] => 3
[1, 0, 1, 1, 1, 0, 0, 0] => 1

We finally hit search for statistic and obtain a result page.

Searching for distributions

As already mentioned, the combinatorial collections we consider are partitioned into finite levels. The generating function of a statistic $\mathsf{st} : \mathcal{C} \longrightarrow \mathbb{Z}$ is the family $(f_n)_n$ of (Laurent) polynomials given by

$$f_n(q) = \sum_{x \in \mathcal{C}_n} q^{\mathsf{st}(x)}$$
where $\mathcal{C}_n$ is a level of $\mathcal{C}$. The distribution search allows to search for generating functions (or rather statistic distributions).

Example

Imagine you computed $f_2(q)=1+q$ and $f_3(q)=1+2q+2q^2+q^3$ as generating functions on permutations of length $2$ and $3$. You can search for statistics with these generating functions by visiting StatisticFinder?Domain=Permutations. There, check the box labeled distribution search. The appearing brackets indicate that we now perform a distribution search. You can also click on all-at-once and enter your data by hand in the following way:

[1,2]
[2,1]
====> 0;1
[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]
====> 0;1;1;2;2;3

After entering your data you click on search for statistic and you see the following result page.

Your distribution search does not need to follow the levels of a collection, and you also can specify fixed values. For instance, if you also know that $\mathsf{st}([3,2,1])=0$, you can include this information in your distribution search:

[1,2]
[2,1]
====> 0;1
[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
====> 1;1;2;2;3
[3,2,1] => 0

Comparing the result page with the one from before you will notice that this more specific search indeed finds a subset of the results from before.

Contributing to FindStat

Everyone with knowledge on combinatorial statistics is invited to contribute by adding a new statistic or map or editing existing statistics or maps. Any statistic or map which is relevant in someone's research is worth being contained in the database. You do not necessarily need to create an account in order to contribute, but we recommend doing so.

It is only possible to contribute statistics on collections that are implemented in FindStat and maps between them.

Every new statistic and map is "verified" by the editores. This verification is not meant to be a mathematical verification, but only a quick check that the provided data appears to be meaningful and the formatting is correct. Yet to be verified statistics and maps can be found at the PendingStatistics and PendingMaps pages.

New collections

If you would like to contribute a new collection that can be used in FindStat, please contact us via info@findstat.org.