Combinatorial Species

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 1 to the leaves and of q 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 4 nodes, one has a single internal node, three have two internal nodes, and one has three internal nodes.

class sage.combinat.species.species.GenericCombinatorialSpecies(min=None, max=None, weight=None)
__add__(g)

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]]
__call__(g)

EXAMPLES:

sage: S = species.SetSpecies()
sage: S(S)
Composition of (Set species) and (Set species)
__cmp__(x)

EXAMPLES:

sage: S = species.SingletonSpecies()
sage: E = species.EmptySetSpecies()
sage: S == S
True
sage: S == E
False
__eq__(x)

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
__getstate__()

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)]
__hash__()

Returns a hash of the unique info tuple.

EXAMPLES:

sage: hash(species.SetSpecies()) #random
-152204909943771174
__init__(min=None, max=None, weight=None)

TESTS:

sage: P = species.PermutationSpecies(size=3)
sage: P._weight
1
sage: P._min
3
sage: P._max
4
__mul__(g)

Returns the product of self and g.

EXAMPLES:

sage: P = species.PermutationSpecies()
sage: F = P * P; F
Product of (Permutation species) and (Permutation species)
__pow__(n)

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
__repr__()

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
__setstate__(state)

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
__weakref__
list of weak references to the object (if defined)
_add_to_digraph(d)

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)]
_check(n=5)

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
_common_parent(parents)

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
_get_series(series_ring_class, prefix, base_ring=None)

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]
_series_helper(series_ring_class, prefix, base_ring=None)

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:

  • series_ring_class - A class for the series ring such as ExponentialGeneratingSeriesRing, etc.
  • prefix - The string prefix associated with the generating series such as “cis” for the cycle index series. This prefix appears in the methods that are implemented in the subclass.
  • base_ring - The ring in which the coefficients of the generating series live. If it is not specified, then it is determined by the weight of the species.

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]
_unique_info()

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)
algebraic_equation_system()

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
composition(g)

EXAMPLES:

sage: S = species.SetSpecies()
sage: S(S)
Composition of (Set species) and (Set species)
cycle_index_series()

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]]
digraph()

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)]
functorial_composition(g)

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]
generating_series()

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
is_weighted()

Returns True if this species has a nontrivial weighting associated with it.

EXAMPLES:

sage: C = species.CycleSpecies()
sage: C.is_weighted()
False
isotype_generating_series()

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
isotypes(labels, structure_class=None)

EXAMPLES:

sage: F = CombinatorialSpecies()
sage: F.isotypes([1,2,3]).list()
...
NotImplementedError
product(g)

Returns the product of self and g.

EXAMPLES:

sage: P = species.PermutationSpecies()
sage: F = P * P; F
Product of (Permutation species) and (Permutation species)
restricted(min=None, max=None)

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]
structures(labels, structure_class=None)

EXAMPLES:

sage: F = CombinatorialSpecies()
sage: F.structures([1,2,3]).list()
...
NotImplementedError
sum(g)

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]]
weight_ring()

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
weighted(weight)

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

Previous topic

Generating Series

Next topic

Recursive Species

This Page