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)¶
Bases:
sage.structure.sage_object.SageObject
- algebraic_equation_system()¶
Return 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: sorted(B.digraph().vertex_iterator(), key=str) [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(base_ring=None)¶
Return the cycle index series for this species.
The cycle index series is a sequence of symmetric functions.
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()¶
Return 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: sorted(g, key=str) [Combinatorial species, Product of (Combinatorial species) and (Combinatorial species), Singleton species, Sum of (Singleton species) and (Product of (Combinatorial species) and (Combinatorial species))] sage: d = {sp: i for i, sp in enumerate(g)} sage: g.relabel(d) sage: g.canonical_label().edges() [(0, 3, None), (2, 0, None), (2, 0, None), (3, 1, None), (3, 2, None)]
- functorial_composition(g)¶
Return the functorial composition of
self
withg
.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(base_ring=None)¶
Return the generating series for this species.
This is an exponential generating series so the \(n\)-th 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()¶
Return
True
if this species has a nontrivial weighting associated with it.EXAMPLES:
sage: C = species.CycleSpecies() sage: C.is_weighted() False
- isotype_generating_series(base_ring=None)¶
Return the isotype generating series for this species.
The \(n\)-th 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() Traceback (most recent call last): ... NotImplementedError
- product(g)¶
Return the product of
self
andg
.EXAMPLES:
sage: P = species.PermutationSpecies() sage: F = P * P; F Product of (Permutation species) and (Permutation species)
- restricted(*args, **kwds)¶
Return the restriction of the species.
INPUT:
min
– optional integermax
– optional integer
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() Traceback (most recent call last): ... NotImplementedError
- sum(g)¶
Return the sum of
self
andg
.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()¶
Return 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)¶
Return 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