This file defines the main classes for working with combinatorial species, operations on them, as well as some implementations of basic species required for other constructions.
This code is based on the work of Ralf Hemmecke and Martin Rubey’s Aldor-Combinat, which can be found at http://www.risc.uni-linz.ac.at/people/hemmecke/aldor/combinat/index.html. In particular, the relevant section for this file can be found at http://www.risc.uni-linz.ac.at/people/hemmecke/AldorCombinat/combinatse8.html.
Weighted Species:
As a first application of weighted species, we count unlabeled
ordered trees by total number of nodes and number of internal
nodes. To achieve this, we assign a weight of to the
leaves and of
to internal nodes:
sage: q = QQ['q'].gen()
sage: leaf = species.SingletonSpecies()
sage: internal_node = species.SingletonSpecies(weight=q)
sage: L = species.LinearOrderSpecies(min=1)
sage: T = species.CombinatorialSpecies()
sage: T.define(leaf + internal_node*L(T))
sage: T.isotype_generating_series().coefficients(6)
[0, 1, q, q^2 + q, q^3 + 3*q^2 + q, q^4 + 6*q^3 + 6*q^2 + q]
Consider the following:
sage: T.isotype_generating_series().coefficient(4)
q^3 + 3*q^2 + q
This means that, among the trees on nodes, one has a
single internal node, three have two internal nodes, and one has
three internal nodes.
Returns the sum of self and g.
EXAMPLES:
sage: P = species.PermutationSpecies()
sage: F = P + P; F
Sum of (Permutation species) and (Permutation species)
sage: F.structures([1,2]).list()
[[1, 2], [2, 1], [1, 2], [2, 1]]
EXAMPLES:
sage: S = species.SetSpecies()
sage: S(S)
Composition of (Set species) and (Set species)
EXAMPLES:
sage: S = species.SingletonSpecies()
sage: E = species.EmptySetSpecies()
sage: S == S
True
sage: S == E
False
Test equality between two species.
EXAMPLES:
sage: X = species.SingletonSpecies()
sage: X + X == X + X
True
sage: X == X
True
sage: X == species.EmptySetSpecies()
False
sage: X == X*X
False
sage: X = species.SingletonSpecies()
sage: E = species.EmptySetSpecies()
sage: L = CombinatorialSpecies()
sage: L.define(E+X*L)
sage: K = CombinatorialSpecies()
sage: K.define(E+X*L)
sage: L == K
True
This is used during the pickling process and returns a dictionary of the data needed to create this object during the unpickling process. It returns an (*args, **kwds) tuple which is to be passed into the constructor for the class of this species. Any subclass should define a _state_info list for any arguments which need to be passed in in the constructor.
EXAMPLES:
sage: C = species.CharacteristicSpecies(5)
sage: args, kwds = C.__getstate__()
sage: args
{0: 5}
sage: list(sorted(kwds.items()))
[('max', None), ('min', None), ('weight', 1)]
Returns a hash of the unique info tuple.
EXAMPLES:
sage: hash(species.SetSpecies()) #random
-152204909943771174
TESTS:
sage: P = species.PermutationSpecies(size=3)
sage: P._weight
1
sage: P._min
3
sage: P._max
4
Returns the product of self and g.
EXAMPLES:
sage: P = species.PermutationSpecies()
sage: F = P * P; F
Product of (Permutation species) and (Permutation species)
Returns this species to the power n. This uses a binary exponentiation algorithm to perform the powering.
EXAMPLES:
sage: X = species.SingletonSpecies()
sage: (X^2).generating_series().coefficients(4)
[0, 0, 1, 0]
sage: X^1 is X
True
sage: A = X^32
sage: A.digraph()
Multi-digraph on 6 vertices
Returns a string representation of this species.
EXAMPLES:
sage: CombinatorialSpecies()
Combinatorial species
sage: species.SetSpecies()
Set species
sage: species.SetSpecies(min=1)
Set species with min=1
sage: species.SetSpecies(min=1, max=4)
Set species with min=1, max=4
sage: t = ZZ['t'].gen()
sage: species.SetSpecies(min=1, max=4, weight=t)
Set species with min=1, max=4, weight=t
This is used during unpickling to recreate this object from the data provided by the __getstate__ method.
TESTS:
sage: C2 = species.CharacteristicSpecies(2)
sage: C4 = species.CharacteristicSpecies(4)
sage: C2
Characteristic species of order 2
sage: C2.__setstate__(C4.__getstate__()); C2
Characteristic species of order 4
Adds this species as a vertex to the digraph d along with any ‘children’ of this species. For example, sum species would add itself as a vertex and an edge between itself and each of its summands.
EXAMPLES:
sage: d = DiGraph(multiedges=True)
sage: X = species.SingletonSpecies()
sage: X._add_to_digraph(d); d
Multi-digraph on 1 vertex
sage: (X+X)._add_to_digraph(d); d
Multi-digraph on 2 vertices
sage: d.edges()
[(Sum of (Singleton species) and (Singleton species), Singleton species, None),
(Sum of (Singleton species) and (Singleton species), Singleton species, None)]
Returns True if the number of structures and isomorphism types generated is the same as the number found from the generating series.
EXAMPLES:
sage: P = species.PartitionSpecies()
sage: P._check()
True
Returns a parent that all of the parents in the given list of parents
EXAMPLES:
sage: C = species.CombinatorialSpecies()
sage: C._common_parent([QQ, ZZ['t']])
Univariate Polynomial Ring in t over Rational Field
Returns the generating / isotype generating / cycle index series ring. The purpose of this method is to restrict the result of _series_helper to self._min and self._max.
EXAMPLES:
sage: P = species.PermutationSpecies(min=2, max=4)
sage: P.generating_series().coefficients(8) #indirect doctest
[0, 0, 1, 1, 0, 0, 0, 0]
This code handles much of the common work involved in getting the generating series for this species (such has determining the correct base ring to pass down to the subclass, determining which method on the subclass to call to get the series object, etc.)
INPUT:
EXAMPLES:
sage: from sage.combinat.species.generating_series import OrdinaryGeneratingSeriesRing
sage: S = species.SetSpecies()
sage: itgs = S._series_helper(OrdinaryGeneratingSeriesRing, "itgs")
sage: itgs.coefficients(3)
[1, 1, 1]
sage: itgs = S._series_helper(OrdinaryGeneratingSeriesRing, "itgs", base_ring=RDF)
sage: itgs.coefficients(3)
[1.0, 1.0, 1.0]
Returns a tuple which should uniquely identify the species.
EXAMPLES:
sage: species.SetSpecies()._unique_info()
(<class 'sage.combinat.species.set_species.SetSpecies_class'>, None, None, 1)
sage: species.SingletonSpecies()._unique_info()
(<class 'sage.combinat.species.characteristic_species.SingletonSpecies_class'>,
None,
None,
1)
sage: X = species.SingletonSpecies()
sage: Y = X + X
sage: Y._unique_info()
(<class 'sage.combinat.species.sum_species.SumSpecies_class'>,
None,
None,
1,
Singleton species,
Singleton species)
Returns a system of algebraic equations satisfied by this species. The nodes are numbered in the order that they appear as vertices of the associated digraph.
EXAMPLES:
sage: B = species.BinaryTreeSpecies()
sage: B.algebraic_equation_system()
[-node3^2 + node1, -node1 + node3 - z]
sage: B.digraph().vertices()
[Combinatorial species,
Product of (Combinatorial species) and (Combinatorial species),
Singleton species,
Sum of (Singleton species) and (Product of (Combinatorial species) and (Combinatorial species))]
sage: B.algebraic_equation_system()[0].parent()
Multivariate Polynomial Ring in node0, node1, node2, node3 over Fraction Field of Univariate Polynomial Ring in z over Rational Field
EXAMPLES:
sage: S = species.SetSpecies()
sage: S(S)
Composition of (Set species) and (Set species)
Returns the cycle index series for this species.
EXAMPLES:
sage: P = species.PermutationSpecies()
sage: g = P.cycle_index_series()
sage: g.coefficients(4)
[p[], p[1], p[1, 1] + p[2], p[1, 1, 1] + p[2, 1] + p[3]]
Returns a directed graph where the vertices are the individual species that make up this one.
EXAMPLES:
sage: X = species.SingletonSpecies()
sage: B = species.CombinatorialSpecies()
sage: B.define(X+B*B)
sage: g = B.digraph(); g
Multi-digraph on 4 vertices
sage: g, labels = g.canonical_label(certify=True)
sage: list(sorted(labels.items()))
[(Combinatorial species, 0),
(Product of (Combinatorial species) and (Combinatorial species), 2),
(Singleton species, 1),
(Sum of (Singleton species) and (Product of (Combinatorial species) and (Combinatorial species)), 3)]
sage: g.edges()
[(0, 3, None), (2, 0, None), (2, 0, None), (3, 1, None), (3, 2, None)]
Returns the functorial composition of self with g.
EXAMPLES:
sage: E = species.SetSpecies()
sage: E2 = E.restricted(min=2, max=3)
sage: WP = species.SubsetSpecies()
sage: P2 = E2*E
sage: G = WP.functorial_composition(P2)
sage: G.isotype_generating_series().coefficients(5)
[1, 1, 2, 4, 11]
Returns the generating series for this species. This is an exponential generating series so the nth coefficient of the series corresponds to the number of labeled structures with n labels divided by n!.
EXAMPLES:
sage: P = species.PermutationSpecies()
sage: g = P.generating_series()
sage: g.coefficients(4)
[1, 1, 1, 1]
sage: g.counts(4)
[1, 1, 2, 6]
sage: P.structures([1,2,3]).list()
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
sage: len(_)
6
Returns True if this species has a nontrivial weighting associated with it.
EXAMPLES:
sage: C = species.CycleSpecies()
sage: C.is_weighted()
False
Returns the isotype generating series for this species. The nth coefficient of this series corresponds to the number of isomorphism types for the structures on n labels.
EXAMPLES:
sage: P = species.PermutationSpecies()
sage: g = P.isotype_generating_series()
sage: g.coefficients(4)
[1, 1, 2, 3]
sage: g.counts(4)
[1, 1, 2, 3]
sage: P.isotypes([1,2,3]).list()
[[2, 3, 1], [2, 1, 3], [1, 2, 3]]
sage: len(_)
3
EXAMPLES:
sage: F = CombinatorialSpecies()
sage: F.isotypes([1,2,3]).list()
...
NotImplementedError
Returns the product of self and g.
EXAMPLES:
sage: P = species.PermutationSpecies()
sage: F = P * P; F
Product of (Permutation species) and (Permutation species)
EXAMPLES:
sage: S = species.SetSpecies().restricted(min=3); S
Set species with min=3
sage: S.structures([1,2]).list()
[]
sage: S.generating_series().coefficients(5)
[0, 0, 0, 1/6, 1/24]
EXAMPLES:
sage: F = CombinatorialSpecies()
sage: F.structures([1,2,3]).list()
...
NotImplementedError
Returns the sum of self and g.
EXAMPLES:
sage: P = species.PermutationSpecies()
sage: F = P + P; F
Sum of (Permutation species) and (Permutation species)
sage: F.structures([1,2]).list()
[[1, 2], [2, 1], [1, 2], [2, 1]]
Returns the ring in which the weights of this species occur.
By default, this is just the field of rational numbers.
EXAMPLES:
sage: species.SetSpecies().weight_ring()
Rational Field
Returns a version of this species with the specified weight.
EXAMPLES:
sage: t = ZZ['t'].gen()
sage: C = species.CycleSpecies(); C
Cyclic permutation species
sage: C.weighted(t)
Cyclic permutation species with weight=t