# FindStat - the Combinatorial Statistic Finder.¶

The FindStat database can be found at:

sage: findstat()
The Combinatorial Statistic Finder (https://www.findstat.org/)


Fix the following three notions:

• A combinatorial collection is a set $$S$$ with interesting combinatorial properties,

• a combinatorial map is a combinatorially interesting map $$f: S \to S'$$ between combinatorial collections, and

• a combinatorial statistic is a combinatorially interesting map $$s: S \to \ZZ$$.

You can use the sage interface to FindStat to:

• identify a combinatorial statistic or map given the values on a few small objects,

• obtain more terms, formulae, references, etc. for a given statistic or map,

• edit statistics and maps and submit new statistics.

AUTHORS:

• Martin Rubey (2015): initial version.

• Martin Rubey (2020): rewrite, adapt to new FindStat API

## The main entry points¶

 findstat() search for matching statistics. findmap() search for matching maps.

## A guided tour¶

### Retrieving information¶

The most straightforward application of the FindStat interface is to gather information about a combinatorial statistic. To do this, we supply findstat() with a list of (object, value) pairs. For example:

sage: PM = PerfectMatchings
sage: r = findstat([(m, m.number_of_nestings()) for n in range(6) for m in PM(2*n)]); r # optional -- internet
0: St000042oMp00116 (quality [100, 100])
1: St000041 (quality [20, 100])
...


The result of this query is a list (presented as a sage.databases.oeis.FancyTuple) of matches. Each match consists of a FindStatCompoundStatistic $$s: S \to \ZZ$$ and an indication of the quality of the match.

The precise meaning of the result is as follows:

The composition $$f_n \circ ... \circ f_2 \circ f_1$$ applied to the objects sent to FindStat agrees with all (object, value) pairs of $$s$$ in the database.

Suppose that the quality of the match is $$(q_a, q_d)$$. Then $$q_a$$ is the percentage of (object, value) pairs that are in the database among those which were sent to FindStat, and $$q_d$$ is the percentage of (object, value) pairs with distinct values in the database among those which were sent to FindStat.

Put differently, if quality is not too small it is likely that the statistic sent to FindStat equals $$s \circ f_n \circ ... \circ f_2 \circ f_1$$. If $$q_a$$ is large, but $$q_b$$ is small, then there were many matches, but while the sought for statistic attains many distinct values, the match found by FindStat covers only (object, value) pairs for few values.

In the case at hand, for the match St000041, the list of maps is empty. We can retrieve the description of the statistic from the database as follows:

sage: print(r[1].statistic().description())                                 # optional -- internet
The number of nestings of a perfect matching.

This is the number of pairs of edges $((a,b), (c,d))$ such that $a\le c\le d\le b$. i.e., the edge $(c,d)$ is nested inside $(a,b)$...


We can check the references:

sage: r[1].statistic().references()                                         # optional -- internet
0: [1]  de Médicis, A., Viennot, X. G., Moments des $q$-polynômes de Laguerre et la bijection de Foata-Zeilberger [[MathSciNet:1288802]]
1: [2]  Simion, R., Stanton, D., Octabasic Laguerre polynomials and permutation statistics [[MathSciNet:1418763]]...


If you prefer, you can look at this information also in your browser:

sage: r[1].statistic().browse()                                             # optional -- webbrowser


Another interesting possibility is to look for equidistributed statistics. Instead of submitting a list of (object, value) pairs, we pass a list of pairs (objects, values):

sage: r = findstat([(PM(2*n), [m.number_of_nestings() for m in PM(2*n)]) for n in range(5)], depth=0); r # optional -- internet
0: St000041 (quality [99, 100])
1: St000042 (quality [99, 100])


This results tells us that the database contains another entry that is equidistributed with the number of nestings on perfect matchings of size at most $$10$$, namely the number of crossings. Note that there is a limit on the number of elements FindStat accepts for a query, which is currently $$1000$$. Queries with more than $$1000$$ elements are truncated.

Let us now look at a slightly more complicated example, where the submitted statistic is the composition of a sequence of combinatorial maps and a statistic known to FindStat. We use the occasion to advertise yet another way to pass values to FindStat:

sage: r = findstat(Permutations, lambda pi: pi.saliances()[0], depth=2); r  # optional -- internet
0: St000476oMp00099oMp00127 (quality [100, 100])
1: St001497oMp00119oMp00127 with offset 1 (quality [100, 100])
2: St000147oMp00027oMp00127 (quality [96, 100])
3: St000054oMp00064oMp00062 with offset 1 (quality [88, 100])
4: St000740oMp00062 with offset 1 (quality [87, 100])
...


Note that some of the matches are up to a global offset, which is then given. For example, we have:

sage: r[4].info()                                                           # optional -- internet
after adding 1 to every value
and applying
Mp00062: Lehmer-code to major-code bijection: Permutations -> Permutations
to the objects (see .compound_map() for details)

St000740: The last entry of a permutation.

among the values you sent, 87 percent are actually in the database,
among the distinct values you sent, 100 percent are actually in the database


Let us pick another particular result:

sage: s = next(s for s in r if s.statistic().id() == 51); s                 # optional -- internet
St000051oMp00061oMp00069 (quality [87, 86])


To obtain the value of the statistic sent to FindStat on a given object, apply the maps in the list in the given order to this object, and evaluate the statistic on the result. For example, let us check that the result given by FindStat agrees with our statistic on the following permutation:

sage: pi = Permutation([3,1,4,5,2]); pi.saliances()[0]
3


We first have to find out, what the maps and the statistic actually do:

sage: print(s.statistic().description())                                    # optional -- internet
The size of the left subtree of a binary tree.

sage: print(s.statistic().sage_code())                                      # optional -- internet
def statistic(T):
return T[0].node_number()

sage: print("\n\n".join(m.sage_code() for m in s.compound_map()))           # optional -- internet
def mapping(sigma):
return sigma.complement()

def mapping(sigma):
return sigma.increasing_tree_shape()


So, the following should coincide with what we sent FindStat:

sage: pi.complement().increasing_tree_shape()[0].node_number()
3


### Editing and submitting statistics¶

Of course, often a statistic will not be in the database:

sage: s = findstat([(d, randint(1,1000)) for d in DyckWords(4)]); s         # optional -- internet
St000000: a new statistic on Dyck paths


In this case, and if the statistic might be “interesting”, please consider submitting it to the database using FindStatStatistic.submit().

Also, you may notice omissions, typos or even mistakes in the description, the code and the references. In this case, simply replace the value by using FindStatFunction.set_description(), FindStatStatistic.set_code() or FindStatFunction.set_references_raw(), and then FindStatStatistic.submit() your changes for review by the FindStat team.

## Classes and methods¶

class sage.databases.findstat.FindStat

The Combinatorial Statistic Finder.

FindStat is a class preserving user information.

browse()

Open the FindStat web page in a browser.

EXAMPLES:

sage: findstat().browse()                                           # optional -- webbrowser

login()

Open the FindStat login page in a browser.

EXAMPLES:

sage: findstat().login()                                            # optional -- webbrowser

set_user(name=None, email=None)

Set the user for the session.

INPUT:

• name – the name of the user.

• email – an email address of the user.

This information is used when submitting a statistic with FindStatStatistic.submit().

EXAMPLES:

sage: findstat().set_user(name="Anonymous", email="[email protected]")


Note

It is usually more convenient to login into the FindStat web page using the login() method.

user_email()

Return the user name used for submissions.

EXAMPLES:

sage: findstat().set_user(name="Anonymous", email="[email protected]")
sage: findstat().user_email()
'[email protected]'

user_name()

Return the user name used for submissions.

EXAMPLES:

sage: findstat().set_user(name="Anonymous", email="[email protected]")
sage: findstat().user_name()
'Anonymous'

class sage.databases.findstat.FindStatCollection(parent, id, data, sageconstructor_overridden)

A FindStat collection.

FindStatCollection is a class representing a combinatorial collection available in the FindStat database.

Its main use is to allow easy specification of the combinatorial collection when using findstat. It also provides methods to quickly access its FindStat web page (browse()), check whether a particular element is actually in the range considered by FindStat (in_range()), etc.

INPUT:

One of the following:

• a string eg. ‘Dyck paths’ or ‘DyckPaths’, case-insensitive, or

• an integer designating the FindStat id of the collection, or

• a sage object belonging to a collection, or

• an iterable producing a sage object belonging to a collection.

EXAMPLES:

sage: from sage.databases.findstat import FindStatCollection
sage: FindStatCollection("Dyck paths")                                  # optional -- internet
Cc0005: Dyck paths

sage: FindStatCollection(5)                                             # optional -- internet
Cc0005: Dyck paths

sage: FindStatCollection(DyckWord([1,0,1,0]))                           # optional -- internet
Cc0005: Dyck paths

sage: FindStatCollection(DyckWords(2))                                  # optional -- internet
a subset of Cc0005: Dyck paths

sage: FindStatCollection(DyckWords)                                     # optional -- internet
Cc0005: Dyck paths

browse()

Open the FindStat web page of the collection in a browser.

EXAMPLES:

sage: from sage.databases.findstat import FindStatCollection
sage: FindStatCollection("Permutations").browse()                   # optional -- webbrowser

element_level(element)

Return the level of an element.

EXAMPLES:

sage: from sage.databases.findstat import FindStatCollection
sage: cc = FindStatCollection("Perfect Matchings")                  # optional -- internet
sage: cc.element_level(PerfectMatching([[1,2],[3,4],[5,6]]))        # optional -- internet
6

elements_on_level(level)

Return an iterable over the elements on the given level.

EXAMPLES:

sage: from sage.databases.findstat import FindStatCollection
sage: FindStatCollection("Perfect Matchings").elements_on_level(4)  # optional -- internet
Perfect matchings of {1, 2, 3, 4}

first_terms(function, level=None)

Compute the first few terms of the given function, possibly restricted to a level, as a lazy list.

INPUT:

• function – a callable

• level – (optional), the level to restrict to

OUTPUT:

A lazy list of pairs of the form (object, value).

EXAMPLES:

sage: from sage.databases.findstat import FindStatCollection
sage: c = FindStatCollection("GelfandTsetlinPatterns")              # optional -- internet
sage: c.first_terms(lambda x: 1)[:10].list()                        # optional -- internet
[([[1, 0], [0]], 1),
([[1, 0], [1]], 1),
([[2, 0], [0]], 1),
([[2, 0], [1]], 1),
([[2, 0], [2]], 1),
([[1, 1], [1]], 1),
([[1, 0, 0], [0, 0], [0]], 1),
([[1, 0, 0], [1, 0], [0]], 1),
([[1, 0, 0], [1, 0], [1]], 1),
([[3, 0], [0]], 1)]

from_string()

Return a function that returns the object given a FindStat representation.

OUTPUT:

The function that produces the sage object given its FindStat representation as a string.

EXAMPLES:

sage: from sage.databases.findstat import FindStatCollection
sage: c = FindStatCollection("Posets")                              # optional -- internet
sage: p = c.from_string()('([(0, 2), (2, 1)], 3)')                  # optional -- internet
sage: p.cover_relations()                                           # optional -- internet
[[0, 2], [2, 1]]

sage: c = FindStatCollection("Binary Words")                        # optional -- internet
sage: w = c.from_string()('010101')                                 # optional -- internet
sage: w in c._data["Code"].elements_on_level(6)                     # optional -- internet
True

id()

Return the FindStat identifier of the collection.

OUTPUT:

The FindStat identifier of the collection as an integer.

EXAMPLES:

sage: from sage.databases.findstat import FindStatCollection
sage: c = FindStatCollection("GelfandTsetlinPatterns")              # optional -- internet
sage: c.id()                                                        # optional -- internet
18

id_str()

Return the FindStat identifier of the collection.

OUTPUT:

The FindStat identifier of the collection as a string.

EXAMPLES:

sage: from sage.databases.findstat import FindStatCollection
sage: c = FindStatCollection("GelfandTsetlinPatterns")              # optional -- internet
sage: c.id_str()                                                    # optional -- internet
u'Cc0018'

in_range(element)

Check whether an element of the collection is in FindStat’s precomputed range.

INPUT:

• element – a sage object that belongs to the collection.

OUTPUT:

True, if element is used by the FindStat search engine, and False if it is ignored.

EXAMPLES:

sage: from sage.databases.findstat import FindStatCollection
sage: c = FindStatCollection("GelfandTsetlinPatterns")              # optional -- internet
sage: c.in_range(GelfandTsetlinPattern([[2, 1], [1]]))              # optional -- internet
True
sage: c.in_range(GelfandTsetlinPattern([[3, 1], [1]]))              # optional -- internet
True
sage: c.in_range(GelfandTsetlinPattern([[7, 1], [1]]))              # optional -- internet
False

is_element(element)

Return whether the element belongs to the collection.

EXAMPLES:

sage: from sage.databases.findstat import FindStatCollection
sage: cc = FindStatCollection("Perfect Matchings")                  # optional -- internet
sage: cc.is_element(PerfectMatching([[1,2],[3,4],[5,6]]))           # optional -- internet
True

sage: cc.is_element(SetPartition([[1,2],[3,4],[5,6]]))              # optional -- internet
False

is_supported()

Check whether the collection is fully supported by the interface.

EXAMPLES:

sage: from sage.databases.findstat import FindStatCollection
sage: FindStatCollection(1).is_supported()                          # optional -- internet
True

sage: FindStatCollection(24).is_supported()                         # optional -- internet, random
False

levels_with_sizes()

Return a dictionary from levels to level sizes.

EXAMPLES:

sage: from sage.databases.findstat import FindStatCollection
sage: cc = FindStatCollection("Perfect Matchings")                  # optional -- internet
sage: cc.levels_with_sizes()                                        # optional -- internet
OrderedDict([(2, 1), (4, 3), (6, 15), (8, 105), (10, 945)])

name(style='singular')

Return the name of the FindStat collection.

INPUT:

• a string – (default:”singular”) can be “singular”, or “plural”.

OUTPUT:

The name of the FindStat collection, in singular or in plural.

EXAMPLES:

sage: from sage.databases.findstat import FindStatCollection
sage: FindStatCollection("Binary trees").name()                     # optional -- internet
u'Binary tree'

sage: FindStatCollection("Binary trees").name(style="plural")       # optional -- internet
u'Binary trees'

to_string()

Return a function that returns a FindStat representation given an object.

OUTPUT:

The function that produces the string representation as needed by the FindStat search webpage.

EXAMPLES:

sage: from sage.databases.findstat import FindStatCollection
sage: p = Poset((range(3), [[0, 1], [1, 2]]))                       # optional -- internet
sage: c = FindStatCollection("Posets")                              # optional -- internet
sage: c.to_string()(p)                                              # optional -- internet
'([(0, 1), (1, 2)], 3)'

class sage.databases.findstat.FindStatCollections

The class of FindStat collections.

The elements of this class are combinatorial collections in FindStat as of January 2020. If a new collection was added to the web service since then, the dictionary _SupportedFindStatCollections in this module has to be updated accordingly.

EXAMPLES:

sage: from sage.databases.findstat import FindStatCollections
sage: sorted(c for c in FindStatCollections())                          # optional -- internet
[Cc0001: Permutations,
Cc0002: Integer partitions,
Cc0005: Dyck paths,
Cc0006: Integer compositions,
Cc0007: Standard tableaux,
Cc0009: Set partitions,
Cc0010: Binary trees,
Cc0012: Perfect matchings,
Cc0013: Cores,
Cc0014: Posets,
Cc0017: Alternating sign matrices,
Cc0018: Gelfand-Tsetlin patterns,
Cc0019: Semistandard tableaux,
Cc0020: Graphs,
Cc0021: Ordered trees,
Cc0022: Finite Cartan types,
Cc0023: Parking functions,
Cc0024: Binary words,
Cc0025: Plane partitions,
Cc0026: Decorated permutations,
Cc0027: Signed permutations,
Cc0028: Skew partitions]

Element

alias of FindStatCollection

class sage.databases.findstat.FindStatCombinatorialMap

A class serving as common ancestor of FindStatStatistic and FindStatCompoundStatistic.

class sage.databases.findstat.FindStatCombinatorialStatistic

A class providing methods to retrieve the first terms of a statistic.

This class provides methods applicable to instances of FindStatStatistic, FindStatCompoundStatistic and FindStatStatisticQuery.

first_terms()

Return the first terms of the (compound) statistic as a dictionary.

OUTPUT:

A dictionary from sage objects representing an element of the appropriate collection to integers.

This method is overridden in FindStatStatisticQuery.

EXAMPLES:

sage: findstat(41).first_terms()[PerfectMatching([(1,6),(2,5),(3,4)])]        # optional -- internet
3

first_terms_str(max_values=1200)

Return the first terms of the statistic in the format needed for a FindStat query.

OUTPUT:

A string, where each line is of the form object => value, where object is the string representation of an element of the appropriate collection as used by FindStat and value is an integer.

EXAMPLES:

sage: print(findstat(41).first_terms_str(max_values=4))             # optional -- internet
[(1,2)] => 0
[(1,2),(3,4)] => 0
[(1,3),(2,4)] => 0
[(1,4),(2,3)] => 1

generating_functions(style='polynomial')

Return the generating functions of the statistic as a dictionary.

The keys of this dictionary are the levels for which the generating function of of the statistic can be computed from the known data. Each value represents a generating function for one level, as a polynomial, as a dictionary, or as a list of coefficients.

INPUT:

• a string – (default:”polynomial”) can be “polynomial”, “dictionary”, or “list”.

OUTPUT:

• if style is "polynomial", the generating function is returned as a polynomial.

• if style is "dictionary", the generating function is returned as a dictionary representing the monomials of the generating function.

• if style is "list", the generating function is returned as a list of coefficients of the generating function. In this case, leading and trailing zeros are omitted.

EXAMPLES:

sage: st = findstat(41)                                             # optional -- internet
sage: st.generating_functions()                                     # optional -- internet
{2: 1,
4: q + 2,
6: q^3 + 3*q^2 + 6*q + 5,
8: q^6 + 4*q^5 + 10*q^4 + 20*q^3 + 28*q^2 + 28*q + 14}

sage: st.generating_functions(style="dictionary")                   # optional -- internet
{2: {0: 1},
4: {0: 2, 1: 1},
6: {0: 5, 1: 6, 2: 3, 3: 1},
8: {0: 14, 1: 28, 2: 28, 3: 20, 4: 10, 5: 4, 6: 1}}

sage: st.generating_functions(style="list")                         # optional -- internet
{2: [1], 4: [2, 1], 6: [5, 6, 3, 1], 8: [14, 28, 28, 20, 10, 4, 1]}


Search the OEIS for the generating function of the statistic.

INPUT:

• search_size (default:32) the number of integers in the sequence. If this is chosen too big, the OEIS result may be corrupted.

• verbose (default:True) if true, some information about the search are printed.

OUTPUT:

EXAMPLES:

sage: st = findstat(41)                                             # optional -- internet

sage: st.oeis_search()                                              # optional -- internet
Searching the OEIS for "1  2,1  5,6,3,1  14,28,28,20,10,4,1"
0: A067311: Triangle read by rows: T(n,k) gives number of ways of arranging n chords on a circle with k simple intersections ...

class sage.databases.findstat.FindStatCompoundMap(id, domain=None, codomain=None, check=True)

Initialize a compound statistic.

INPUT:

• id – a padded identifier

• domain– (optional), the domain of the compound map

• codomain– (optional), the codomain of the compound map

• check – whether to check that domains and codomains fit

If domain and codomain are given and check is False, they are not fetched from FindStat.

If id is the empty string, domain must be provided, and the identity map on this collection is returned.

browse()

Open the FindStat web page of the compound map in a browser.

EXAMPLES:

sage: findmap(62).browse()                                          # optional -- webbrowser

codomain()

Return the codomain of the compound map.

EXAMPLES:

sage: findmap("Mp00099oMp00127").codomain()                         # optional -- internet
Cc0005: Dyck paths

domain()

Return the domain of the compound map.

EXAMPLES:

sage: findmap("Mp00099oMp00127").domain()                           # optional -- internet
Cc0001: Permutations

id_str()

Return the padded identifier of the compound map.

EXAMPLES:

sage: findmap("Mp00099oMp00127").id_str()                           # optional -- internet
'Mp00099oMp00127'

maps()

Return the maps occurring in the compound map as a list.

EXAMPLES:

sage: findmap("Mp00099oMp00127").maps()                             # optional -- internet
[Mp00127: left-to-right-maxima to Dyck path, Mp00099: bounce path]

class sage.databases.findstat.FindStatCompoundStatistic(id, domain=None, check=True)

Initialize a compound statistic.

INPUT:

• id – a padded identifier

• domain – (optional), the domain of the compound statistic

• check – whether to check that domains and codomains fit

If the domain is given and check is False, it is not fetched from FindStat.

browse()

Open the FindStat web page of the compound statistic in a browser.

EXAMPLES:

sage: from sage.databases.findstat import FindStatCompoundStatistic
sage: FindStatCompoundStatistic("St000042oMp00116").browse()        # optional -- webbrowser

compound_map()

Return the compound map which is part of the compound statistic.

EXAMPLES:

sage: findstat("St000051oMp00061oMp00069").compound_map()           # optional -- internet
Mp00061oMp00069

domain()

Return the domain of the compound statistic.

EXAMPLES:

sage: findstat("St000042oMp00116").domain()                         # optional -- internet
Cc0012: Perfect matchings

id_str()

Return the padded identifier of the compound statistic.

EXAMPLES:

sage: findstat("St000042oMp00116").id_str()                         # optional -- internet
'St000042oMp00116'

statistic()

Return the statistic of the compound statistic.

EXAMPLES:

sage: findstat("St000041oMp00116").statistic()                      # optional -- internet
St000041: The number of nestings of a perfect matching.

class sage.databases.findstat.FindStatFunction(id, data=None, function=None)

A class providing the common methods of FindStatMap and FindStatStatistic.

This class provides methods to access and modify properties of a single statistic or map of the FindStat database.

description()

Return the description of the statistic or map.

OUTPUT:

A string. For statistics, the first line is used as name.

EXAMPLES:

sage: print(findstat(51).description())                             # optional -- internet
The size of the left subtree of a binary tree.

domain()

Return the FindStat domain of the statistic or map.

OUTPUT:

The domain of the statistic or map as an instance of FindStatCollection.

EXAMPLES:

sage: findstat(51).domain()                                         # optional -- internet
Cc0010: Binary trees

sage: findmap(62).domain()                                          # optional -- internet
Cc0001: Permutations

id()

Return the FindStat identifier of the statistic or map.

OUTPUT:

The FindStat identifier of the statistic or map, as an integer.

EXAMPLES:

sage: findstat(51).id()                                             # optional -- internet
51

id_str()

Return the FindStat identifier of the statistic or map.

OUTPUT:

The FindStat identifier of the statistic or map, as a string.

EXAMPLES:

sage: findstat(51).id_str()                                         # optional -- internet
u'St000051'

name()

Return the name of the statistic or map.

OUTPUT:

A string. For statistics, this is just the first line of the description.

EXAMPLES:

sage: findstat(51).name()                                           # optional -- internet
u'The size of the left subtree of a binary tree.'

references()

Return the references associated with the statistic or map.

OUTPUT:

An instance of sage.databases.oeis.FancyTuple, each item corresponds to a reference.

EXAMPLES:

sage: findstat(41).references()                                     # optional -- internet
0: [1]  de Médicis, A., Viennot, X. G., Moments des $q$-polynômes de Laguerre et la bijection de Foata-Zeilberger [[MathSciNet:1288802]]
1: [2]  Simion, R., Stanton, D., Octabasic Laguerre polynomials and permutation statistics [[MathSciNet:1418763]]

references_raw()

Return the unrendered references associated with the statistic or map.

EXAMPLES:

sage: print(findstat(41).references_raw())                          # optional -- internet
[1]  [[MathSciNet:1288802]]
[2]  [[MathSciNet:1418763]]

reset()

Discard all modification of the statistic or map.

EXAMPLES:

sage: s = findmap(62)                                               # optional -- internet
sage: s.set_name(u"Möbius"); s                                      # optional -- internet
Mp00062(modified): Möbius
sage: s.reset(); s                                                  # optional -- internet
Mp00062: Lehmer-code to major-code bijection

sage_code()

Return the sage code associated with the statistic or map.

OUTPUT:

An empty string or a string of the form:

def statistic(x):
...


or:

def mapping(x):
...


EXAMPLES:

sage: print(findstat(51).sage_code())                               # optional -- internet
def statistic(T):
return T[0].node_number()

set_description(value)

Set the description of the statistic or map.

INPUT:

• a string – for statistics, this is the name of the statistic followed by its description on a separate line.

This information is used when submitting the statistic or map with submit().

EXAMPLES:

sage: q = findstat([(d, randint(1, 1000)) for d in DyckWords(4)])             # optional -- internet
sage: q.set_description("Random values on Dyck paths.\nNot for submission.")  # optional -- internet
sage: print(q.description())                                                  # optional -- internet
Random values on Dyck paths.
Not for submission.

set_references_raw(value)

Set the references associated with the statistic or map.

INPUT:

• a string – each reference should be on a single line, and consist of one or more links to the same item.

FindStat will automatically resolve the links, if possible. A complete list of supported services can be found at <https://findstat.org/NewStatistic>.

This information is used when submitting the statistic with submit().

EXAMPLES:

sage: q = findstat([(d, randint(1, 1000)) for d in DyckWords(4)])   # optional -- internet
sage: q.set_references_raw("[[arXiv:1102.4226]]\n[[oeis:A000001]]") # optional -- internet
sage: q.references()                                                # optional -- internet
0: [[arXiv:1102.4226]]
1: [[oeis:A000001]]

set_sage_code(value)

Set the code associated with the statistic or map.

INPUT:

• a string – SageMath code producing the values of the statistic or map.

Contributors are encouraged to submit code for statistics using FindStatStatistic.set_code(). Modifying the “verified” SageMath code using this method is restricted to members of the FindStatCrew, for all other contributors this method has no effect.

EXAMPLES:

sage: q = findstat([(d, randint(1,1000)) for d in DyckWords(4)])              # optional -- internet
sage: q.set_sage_code("def statistic(x):\r\n    return randint(1,1000)")      # optional -- internet
sage: print(q.sage_code())                                                    # optional -- internet
def statistic(x):
return randint(1,1000)

class sage.databases.findstat.FindStatMap(parent, id)

A FindStat map.

FindStatMap is a class representing a combinatorial map available in the FindStat database.

This class provides methods to inspect various properties of these maps, in particular code().

EXAMPLES:

sage: from sage.databases.findstat import FindStatMap
sage: FindStatMap(116)                                                  # optional -- internet
Mp00116: Kasraoui-Zeng

browse()

Open the FindStat web page of the map in a browser.

EXAMPLES:

sage: from sage.databases.findstat import FindStatMap
sage: FindStatMap(116).browse()                                     # optional -- webbrowser

codomain()

Return the FindStat collection which is the codomain of the map.

OUTPUT:

The codomain of the map as a FindStatCollection.

EXAMPLES:

sage: from sage.databases.findstat import FindStatMap               # optional -- internet
sage: FindStatMap(27).codomain()                                    # optional -- internet
Cc0002: Integer partitions

edit()

Open the FindStat web page for editing the map in a browser.

properties_raw()

Return the properties of the map.

OUTPUT:

The properties as a string.

EXAMPLES:

sage: from sage.databases.findstat import FindStatMap               # optional -- internet
sage: FindStatMap(61).properties_raw()                              # optional -- internet

set_name(value)

Set the name of the map.

INPUT:

• a string – the new name of the map.

This information is used when submitting the map with submit().

set_properties_raw(value)

Set the properties of the map.

EXAMPLES:

sage: from sage.databases.findstat import FindStatMap               # optional -- internet
sage: FindStatMap(61).set_properties_raw(u'surjective')             # optional -- internet
sage: FindStatMap(61).properties_raw()                              # optional -- internet
u'surjective'
sage: FindStatMap(61)                                               # optional -- internet
Mp00061(modified): to increasing tree
sage: FindStatMap(61).reset()                                       # optional -- internet
sage: FindStatMap(61)                                               # optional -- internet
Mp00061: to increasing tree

submit()

Open the FindStat web page for editing the map in a browser.

class sage.databases.findstat.FindStatMapQuery(data=None, values_of=None, distribution_of=None, domain=None, codomain=None, known_terms=None, function=None, depth=2, debug=False)

A class representing a query for FindStat (compound) maps.

class sage.databases.findstat.FindStatMaps(domain=None, codomain=None)

The class of FindStat maps.

The elements of this class are combinatorial maps currently in FindStat.

EXAMPLES:

We can print a sample map for each domain and codomain:

sage: from sage.databases.findstat import FindStatCollections, FindStatMaps
sage: ccs = sorted(FindStatCollections())[:3]                           # optional -- internet
sage: for cc_dom in ccs:                                                # optional -- internet
....:     for cc_codom in ccs:
....:         print(cc_dom.name(style="plural") + " -> " + cc_codom.name(style="plural"))
....:         try:
....:             print("    " + next(iter(FindStatMaps(cc_dom, cc_codom))).name())
....:         except StopIteration:
....:             pass
Permutations -> Permutations
Lehmer-code to major-code bijection
Permutations -> Integer partitions
Robinson-Schensted tableau shape
Permutations -> Dyck paths
left-to-right-maxima to Dyck path
Integer partitions -> Permutations
Integer partitions -> Integer partitions
conjugate
Integer partitions -> Dyck paths
to Dyck path
Dyck paths -> Permutations
to non-crossing permutation
Dyck paths -> Integer partitions
to partition
Dyck paths -> Dyck paths
reverse

Element

alias of FindStatMap

class sage.databases.findstat.FindStatMatchingMap(matching_map, quality, domain=None, codomain=None)

Initialize a FindStat map match.

INPUT:

• matching_map, a compound map identifier

• quality, the quality of the match, as provided by FindStat

• domain– (optional), the domain of the compound map

• codomain– (optional), the codomain of the compound map

EXAMPLES:

sage: from sage.databases.findstat import FindStatMatchingMap
sage: FindStatMatchingMap("Mp00099oMp00127", [83])                  # optional -- internet
Mp00099oMp00127 (quality [83])

quality()

Return the quality of the match, as provided by FindStat.

EXAMPLES:

sage: from sage.databases.findstat import FindStatMatchingMap
sage: FindStatMatchingMap("Mp00099oMp00127", [83]).quality()        # optional -- internet
[83]

class sage.databases.findstat.FindStatMatchingStatistic(matching_statistic, offset, quality, domain=None)

Initialize a FindStat statistic match.

INPUT:

• matching_statistic, a compound statistic identifier

• offset, the offset of the values, as provided by FindStat

• quality, the quality of the match, as provided by FindStat

• domain – (optional), the domain of the compound statistic

EXAMPLES:

sage: from sage.databases.findstat import FindStatMatchingStatistic
sage: FindStatMatchingStatistic("St000042oMp00116", 1, [17, 83])    # optional -- internet
St000042oMp00116 with offset 1 (quality [17, 83])

info()

Print a detailed explanation of the match.

EXAMPLES:

sage: from sage.databases.findstat import FindStatMatchingStatistic
sage: r = FindStatMatchingStatistic("St000042oMp00116", 1, [17, 83])          # optional -- internet
sage: r.info()                                                      # optional -- internet
after adding 1 to every value
and applying
Mp00116: Kasraoui-Zeng: Perfect matchings -> Perfect matchings
to the objects (see .compound_map() for details)

St000042: The number of crossings of a perfect matching.

among the values you sent, 17 percent are actually in the database,
among the distinct values you sent, 83 percent are actually in the database

offset()

Return the offset which has to be added to each value of the compound statistic to obtain the desired value.

EXAMPLES:

sage: from sage.databases.findstat import FindStatMatchingStatistic
sage: r = FindStatMatchingStatistic("St000042oMp00116", 1, [17, 83])          # optional -- internet
sage: r.offset()                                                    # optional -- internet
1

quality()

Return the quality of the match, as provided by FindStat.

The quality of a statistic match is a pair of percentages $$(q_a, q_d)$$, where $$q_a$$ is the percentage of (object, value) pairs that are in the database among those which were sent to FindStat, and $$q_d$$ is the percentage of (object, value) pairs with distinct values in the database among those which were sent to FindStat.

EXAMPLES:

sage: from sage.databases.findstat import FindStatMatchingStatistic
sage: r = FindStatMatchingStatistic("St000042oMp00116", 1, [17, 83])          # optional -- internet
sage: r.quality()                                                   # optional -- internet
[17, 83]

class sage.databases.findstat.FindStatStatistic(parent, id)

A FindStat statistic.

FindStatStatistic is a class representing a combinatorial statistic available in the FindStat database.

This class provides methods to inspect and update various properties of these statistics.

EXAMPLES:

sage: from sage.databases.findstat import FindStatStatistic
sage: FindStatStatistic(41)                                             # optional -- internet
St000041: The number of nestings of a perfect matching.

browse()

Open the FindStat web page of the statistic in a browser.

EXAMPLES:

sage: findstat(41).browse()                                         # optional -- webbrowser

code()

Return the code associated with the statistic or map.

OUTPUT:

A string. Contributors are encouraged to submit sage code in the form:

def statistic(x):
...


but the string may also contain code for other computer algebra systems.

EXAMPLES:

sage: print(findstat(41).code())                                    # optional -- internet
def statistic(x):
return len(x.nestings())

sage: print(findstat(118).code())                                   # optional -- internet
(* in Mathematica *)
tree = {{{{}, {}}, {{}, {}}}, {{{}, {}}, {{}, {}}}};
Count[tree, {{___}, {{___}, {{___}, {___}}}}, {0, Infinity}]

edit(max_values=1200)

Open the FindStat web page for editing the statistic or submitting a new statistic in a browser.

set_code(value)

Set the code associated with the statistic.

INPUT:

• a string – code producing the values of the statistic.

Contributors are encouraged to submit SageMath code in the form:

def statistic(x):
...


However, code for any other platform is accepted also.

This information is used when submitting the statistic with submit().

EXAMPLES:

sage: q = findstat([(d, randint(1,1000)) for d in DyckWords(4)])    # optional -- internet
sage: q.set_code("def statistic(x):\r\n    return randint(1,1000)") # optional -- internet
sage: print(q.code())                                               # optional -- internet
def statistic(x):
return randint(1,1000)

set_first_terms(values)

Update the first terms of the statistic.

INPUT:

• a list of pairs of the form (object, value) where object is a sage object representing an element of the appropriate collection and value is an integer.

This information is used when submitting the statistic with submit().

Warning

This method cannot check whether the given values are actually correct. Moreover, it does not even perform any sanity checks.

submit(max_values=1200)

Open the FindStat web page for editing the statistic or submitting a new statistic in a browser.

class sage.databases.findstat.FindStatStatisticQuery(data=None, values_of=None, distribution_of=None, domain=None, known_terms=None, function=None, depth=2, debug=False)

A class representing a query for FindStat (compound) statistics.

first_terms()

Return the pairs of the known terms which contain singletons as a dictionary.

EXAMPLES:

sage: PM = PerfectMatchings
sage: l = [(PM(2*n), [m.number_of_nestings() for m in PM(2*n)]) for n in range(5)]
sage: r = findstat(l, depth=0); r                                  # optional -- internet
0: St000041 (quality [99, 100])
1: St000042 (quality [99, 100])
sage: r.first_terms()                                              # optional -- internet
OrderedDict([([], 0), ([(1, 2)], 0)])

class sage.databases.findstat.FindStatStatistics(domain=None)

The class of FindStat statistics.

The elements of this class are combinatorial statistics currently in FindStat.

EXAMPLES:

We can print a list of the first few statistics currently in FindStat in a given domain:

sage: from sage.databases.findstat import FindStatStatistics
sage: for st, _ in zip(FindStatStatistics("Perfect Matchings"), range(3)):        # optional -- internet
....:     print("    " + st.name())
The number of nestings of a perfect matching.
The number of crossings of a perfect matching.
The number of crossings plus two-nestings of a perfect matching.

Element

alias of FindStatStatistic

sage.databases.findstat.findmap(*args, **kwargs)

Return matching maps.

INPUT:

Valid keywords are: domain, codomain, values, distribution, depth and max_values. They have the following meanings:

• depth – (default FINDSTAT_DEFAULT_DEPTH), an integer between 0 and FINDSTAT_MAX_DEPTH, specifying how many maps to apply to generate the given map.

• max_values – (default FINDSTAT_MAX_VALUES), an integer specifying how many values are sent to the finder.

• domain, codomain, an integer or string of the form Cc1234, designates the domain and codomain of the sought for maps.

• values, distribution, data specifying the values or distribution of values of the sought for maps. The keyword arguments depth and max_values are passed to the finder. The data may be specified in one of the following forms:

• a list of pairs of the form (object, value), or a dictionary from sage objects to sage objects.

• a list of pairs of the form (list of objects, list of values), or a single pair of the form (list of objects, list of values). In each pair there should be as many objects as values.

• a callable. In this case, the domain must be specified, also. The callable is then used to generate max_values (object, value) pairs.

The number of terms generated may also be controlled by passing an iterable collection, such as Permutations(3).

findmap also accepts at most three positional arguments as follows:

• a single positional argument, if none of domain, codomain, values or distribution are specified, is interpreted as a FindStat map identifier. If further arguments are given and it is a string, it is interpreted as a domain. If all this fails, it is interpreted as the specification of values.

• if two positional arguments are given, the first is interpreted as domain, and the second either as codomain or the specification of values.

• if three positional arguments are given, the first two are interpreted as domain and codomain, and the third as the specification of values.

OUTPUT:

An instance of a FindStatMap, FindStatMapQuery or FindStatMaps.

EXAMPLES:

A particular map can be retrieved by its Mp-identifier or number:

sage: findmap('Mp00062')                                                # optional -- internet
Mp00062: Lehmer-code to major-code bijection

sage: findmap(62)                                                       # optional -- internet
Mp00062: Lehmer-code to major-code bijection

sage: findmap("Mp00099oMp00127")                                        # optional -- internet
Mp00099oMp00127


The database can be searched by providing a list of pairs:

sage: l = [pi for n in range(5) for pi in Permutations(n)]
sage: q = findmap([(pi, pi.complement().increasing_tree_shape()) for pi in l], depth=2); q  # optional -- internet
0: Mp00061oMp00069 (quality [100])


or a dictionary:

sage: p = findmap({pi: pi.complement().increasing_tree_shape() for pi in l}, depth=2); p    # optional -- internet
0: Mp00061oMp00069 (quality [100])


Note however, that the results of these two queries need not compare equal, because we compare queries by the data sent, and the ordering of the data might be different.

Another possibility is to send a collection and a function. In this case, the function is applied to the first few objects of the collection:

sage: findmap("Permutations", lambda pi: pi.increasing_tree_shape(), depth=1)     # optional -- internet
0: Mp00061 (quality [100])


In rare cases, it may not be possible to guess the codomain of a map, in which case it can be provided as second argument or keyword argument:

sage: findmap("Dyck paths", "Perfect matchings", lambda D: [(a+1, b) for a,b in D.tunnels()]) # optional -- internet
0: Mp00146 (quality [100])

sage: findmap("Dyck paths", "Set partitions", lambda D: [(a+1, b) for a,b in D.tunnels()]) # optional -- internet
0: Mp00092oMp00146 (quality [50])


Finally, we can also retrieve all maps with a given domain or codomain:

sage: findmap("Cc0024")                                                 # optional -- internet
Set of combinatorial maps with domain Cc0024: Binary words used by FindStat

sage: findmap(codomain="Cores")                                         # optional -- internet
Set of combinatorial maps with codomain Cc0013: Cores used by FindStat

sage.databases.findstat.findstat(query=None, values=None, distribution=None, domain=None, depth=2, max_values=1000)

Return matching statistics.

INPUT:

One of the following:

• an integer or a string representing a valid FindStat identifier (e.g. 45 or ‘St000045’). The keyword arguments depth and max_values are ignored, values and distribution must be None.

• a list of pairs of the form (object, value), or a dictionary from sage objects to integer values. The keyword arguments depth and max_values are passed to the finder, values and distribution must be None.

• a list of pairs of the form (list of objects, list of values), or a single pair of the form (list of objects, list of values). In each pair there should be as many objects as values. The keyword arguments depth and max_values are passed to the finder.

• a collection and a list of pairs of the form (string, value), or a dictionary from strings to integer values. The keyword arguments depth and max_values are passed to the finder. This should only be used if the collection is not yet supported.

• a collection and a callable. The callable is used to generate max_values (object, value) pairs. The number of terms generated may also be controlled by passing an iterable collection, such as Permutations(3). The keyword arguments depth and max_values are passed to the finder.

OUTPUT:

An instance of a FindStatStatistic, represented by

• the FindStat identifier together with its name, or

• a list of triples, each consisting of

• the statistic

• a list of strings naming certain maps

• a number which says how many of the values submitted agree with the values in the database, when applying the maps in the given order to the object and then computing the statistic on the result.

EXAMPLES:

A particular statistic can be retrieved by its St-identifier or number:

sage: findstat('St000041')                                              # optional -- internet
St000041: The number of nestings of a perfect matching.

sage: findstat(51)                                                      # optional -- internet
St000051: The size of the left subtree of a binary tree.

sage: findstat('St000042oMp00116')                                      # optional -- internet
St000042oMp00116


The database can be searched by providing a list of pairs:

sage: l = [m for n in range(1, 4) for m in PerfectMatchings(2*n)]
sage: q = findstat([(m, m.number_of_nestings()) for m in l], depth=0); q          # optional -- internet
0: St000041 (quality [100, 100])


or a dictionary:

sage: p = findstat({m: m.number_of_nestings() for m in l}, depth=0); p  # optional -- internet
0: St000041 (quality [100, 100])


Note however, that the results of these two queries need not compare equal, because we compare queries by the data sent, and the ordering of the data might be different.

Another possibility is to send a collection and a function. In this case, the function is applied to the first few objects of the collection:

sage: findstat("Perfect Matchings", lambda m: m.number_of_nestings(), depth=0)    # optional -- internet
0: St000041 (quality [20, 100])


To search for a distribution, send a list of lists, or a single pair:

sage: PM = PerfectMatchings(10); findstat((PM, [m.number_of_nestings() for m in PM]), depth=0) # optional -- internet
0: St000042 (quality [100, 100])
1: St000041 (quality [9, 100])


Alternatively, specify the distribution parameter:

sage: findstat(12, distribution=lambda m: m.number_of_nestings(), depth=0) # optional -- internet
0: St000041 (quality [100, 100])
1: St000042 (quality [100, 100])


Note that there is a limit, FINDSTAT_MAX_VALUES, on the number of elements that may be submitted to FindStat, which is currently 1000. Therefore, the interface tries to truncate queries appropriately, but this may be impossible, especially with distribution searches:

sage: PM = PerfectMatchings(12); PM.cardinality()                       # optional -- internet
10395
sage: findstat((PM, [1 for m in PM]))                                   # optional -- internet
Traceback (most recent call last):
...
ValueError: E016: You passed too few elements (0 < 3) to FindStat!


Finally, we can also retrieve all statistics with a given domain:

sage: findstat("Cc0024")                                                # optional -- internet
Set of combinatorial statistics with domain Cc0024: Binary words in FindStat

sage: findstat(domain="Cores")                                          # optional -- internet
Set of combinatorial statistics with domain Cc0013: Cores in FindStat