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

1. The database

1.1. 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\}$.

1.2. 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.

1.3. 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.

1.4. Data storage

Statistics and maps are stored in the database as a finite amount of its images. 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.

Maps are stored in the database as a finite

2. The FindStat 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.

2.1. 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. (As of Feb 1, 2022, the engine computes roughly 3.5 million unique compositions of maps of weight at most 100, most of them being compositions of 4 or 5 maps in the database).

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 an editor.

2.2. Composition identities

We also compute identities between map compositions of the form $\mathsf{mp}_1 \circ \dots \circ \mathsf{mp}_k = \mathsf{mp}'_1 \circ \dots \circ \mathsf{mp}'_\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, so they might be wrong. This is why we call them experimental.

The above-mentioned 3.5 million compositions are only taking compositions "up to composition identities" into account.

3. 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.

3.1. 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 significance in that data. 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.

There, the first line says

• Your data matches 7 different statistics following compositions of up to 3 maps.

So, the statistic finder found 7 different statistics in the FindStat database that (partially) match your data. You can find details on all matches in the boxes on the result page. Each box contains the data of a matching statistic, sorted by result quality.

Let's look at the first box. The matching statistic is St000001. If we look at that statistic, we see

• Identifier:

• St000001: Permutations $\rightarrow \mathbb Z$.

Description:

• The number of reduced words for a permutation.

Although we entered data on Dyck paths, the first matching statistic is a statistic on permutations. How can that be? The answer is given when looking at the full match:

• Mapping:

• Mp00025: Dyck paths —to 132-avoiding permutation⟶ Permutations
St000001: Permutations ⟶ ℤ

Values:

• [1,0,1,0,1,0,1,0] => [4,3,2,1] => 16
[1,0,1,0,1,1,0,0] => [3,4,2,1] => 5
[1,0,1,1,0,0,1,0] => [4,2,3,1] => 6
[1,0,1,1,0,1,0,0] => [3,2,4,1] => 3
[1,0,1,1,1,0,0,0] => [2,3,4,1] => 1

So, the full match is not the statistic St000001 but rather the compound statistic St000001oMp00025 (this page also opens when you click on mapping).

• (load all 11 compositions to match this statistic)

we can also look at other compound statistics that involve St000001 and match our data. For instance, the next match is the compound statistic St000001oMp00064oMp00023 and so forth.

By default, the statistic finder includes all compositions of up to 3 map in its search. On the result page, you can click on (click to perform a complete search on your data) to perform a full search on all compositions that FindStat has computed (also see #Compositions). Note that a full search can take up to a few minutes of computation time, depending on the chosen collection and data.

3.2. Searching for distributions

As already mentioned in Collections, 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}$.

You can use the statistic finder's distribution search to find statistics with a given generating function.

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

(You can use the embedded Sage cell to help you with generating the elements, there's already code for this included in the cell.)

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.

4. Contributing to FindStat

Everyone with knowledge on combinatorial statistics can contribute by adding a new statistic or map or editing an existing statistic or map. 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.

4.1. Contributing statistics

Every contributed statistic must contain the following information:

1. Data for the statistic. We require a statistic to be defined and provided for at least 10 and at most 1200 elements (if possible, you should provide data for 1000 elements). Every entry contains one line and is of the form object_name => value. Here, object_name must be provided in the same way it is used in the StatisticsDatabase. If you are unsure how to correctly format the data and have Sage code for it, you can utilize the interactive Sage cell on the bottom of the page.

2. A detailed description of the statistic.

• The first line of the description serves as a title for the statistic, so it should be comprehensive and not contain any LaTeX.
3. The author's name.

• Sage or (pseudo-)code for computing the statistic.

• References to literature containing the statistic, especially when you use them in the description.

Every new statistic must first be "verified" by an editor. This verification is not meant to be a mathematical verification, but only a quick check that the provided statistic seems to be meaningful.

New statistics that aren't verified yet are listed under PendingStatistics.

4.2. Contributing maps

Every contributed map must contain the following information:

1. Domain and codomain, which are combinatorial collections.

2. A short but meaningful name.

3. A detailed description of the map.

4. Sage code for the map. Different from statistics, for maps we require a working Sage function to generate the map images. Your code should preferably be fast and simple and not raise errors on specific elements. The name of the function must be mapping.

5. The author's name.

• Mathematical properties the map has. Currently, the allowed properties are injective, surjective, bijective, involutive and graded. You can select them from the dropdown menu.

• References to literature containing the map.

Every new map must first be "verified" by an editor. To be verified, a map must be "meaningful" and the Sage code must be fast enough to compute all elements in low levels of the given collection in a reasonable amount of time.

New maps that aren't verified yet are listed under PendingMaps.

4.3. Creating and editing wiki pages

You must have signed up for an account in order to be allowed to create a new wiki page.

To create a new wiki page, simply type the page name into the URL. If possible you should use one of the given templates.

4.3.1. References

The macro for references can be used in the following 4 ways:

• Reference(identifier,author,title,publishing information) simply defines a reference
• Example: <<Reference("Nob12","A. Nobody","A proof of the Riemann hypothesis","Some journal '''1''' (2012)")>> renders as [Nob12].

• Reference(identifier,author,title,publishing information) defines a reference with some additional infos
• Example: <<Reference("Yes12","A. Yesbody","No proof of the Riemann hypothesis","Some journal '''2''' (2012)","Theorem 1")>> renders as [Yes12, Theorem 1].

• Reference(identifier) produces another instance of a reference
• Example: <<Reference("Yes12")>> renders as [Yes12].

• Reference(identifier) produces another instance of a reference plus some additional infos
• Example: <<Reference("Yes12","Theorem 3.14")>> renders as [Yes12, Theorem 3.14].

The list of references is produced by calling <<Reference>> without any parameters:

References:

[Nob12]   A. Nobody, A proof of the Riemann hypothesis, Some journal 1 (2012).

[Yes12]   A. Yesbody, No proof of the Riemann hypothesis, Some journal 2 (2012).

Interesting system pages