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(min=1)
sage: T.define(leaf + internal_node*L(T))
sage: T.isotype_generating_series()[0:6] # needs sage.modules
[0, 1, q, q^2 + q, q^3 + 3*q^2 + q, q^4 + 6*q^3 + 6*q^2 + q]
>>> from sage.all import *
>>> q = QQ['q'].gen()
>>> leaf = species.SingletonSpecies()
>>> internal_node = species.SingletonSpecies(weight=q)
>>> L = species.LinearOrderSpecies(min=Integer(1))
>>> T = species.CombinatorialSpecies(min=Integer(1))
>>> T.define(leaf + internal_node*L(T))
>>> T.isotype_generating_series()[Integer(0):Integer(6)] # needs sage.modules
[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) # needs sage.modules
q^3 + 3*q^2 + q
>>> from sage.all import *
>>> T.isotype_generating_series().coefficient(Integer(4)) # needs sage.modules
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)[source]#
Bases:
SageObject
- algebraic_equation_system()[source]#
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() # needs sage.graphs [-node3^2 + node1, -node1 + node3 + (-z)]
>>> from sage.all import * >>> B = species.BinaryTreeSpecies() >>> B.algebraic_equation_system() # needs sage.graphs [-node3^2 + node1, -node1 + node3 + (-z)]
sage: sorted(B.digraph().vertex_iterator(), key=str) # needs sage.graphs [Combinatorial species with min=1, Product of (Combinatorial species with min=1) and (Combinatorial species with min=1), Singleton species, Sum of (Singleton species) and (Product of (Combinatorial species with min=1) and (Combinatorial species with min=1))]
>>> from sage.all import * >>> sorted(B.digraph().vertex_iterator(), key=str) # needs sage.graphs [Combinatorial species with min=1, Product of (Combinatorial species with min=1) and (Combinatorial species with min=1), Singleton species, Sum of (Singleton species) and (Product of (Combinatorial species with min=1) and (Combinatorial species with min=1))]
sage: B.algebraic_equation_system()[0].parent() # needs sage.graphs Multivariate Polynomial Ring in node0, node1, node2, node3 over Fraction Field of Univariate Polynomial Ring in z over Rational Field
>>> from sage.all import * >>> B.algebraic_equation_system()[Integer(0)].parent() # needs sage.graphs Multivariate Polynomial Ring in node0, node1, node2, node3 over Fraction Field of Univariate Polynomial Ring in z over Rational Field
- composition(g)[source]#
EXAMPLES:
sage: S = species.SetSpecies() sage: S(S) Composition of (Set species) and (Set species)
>>> from sage.all import * >>> S = species.SetSpecies() >>> S(S) Composition of (Set species) and (Set species)
- cycle_index_series(base_ring=None)[source]#
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() # needs sage.modules sage: g[0:4] # needs sage.modules [p[], p[1], p[1, 1] + p[2], p[1, 1, 1] + p[2, 1] + p[3]]
>>> from sage.all import * >>> P = species.PermutationSpecies() >>> g = P.cycle_index_series() # needs sage.modules >>> g[Integer(0):Integer(4)] # needs sage.modules [p[], p[1], p[1, 1] + p[2], p[1, 1, 1] + p[2, 1] + p[3]]
- digraph()[source]#
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 # needs sage.graphs Multi-digraph on 4 vertices sage: sorted(g, key=str) # needs sage.graphs [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)} # needs sage.graphs sage: g.relabel(d) # needs sage.graphs sage: g.canonical_label().edges(sort=True) # needs sage.graphs [(0, 3, None), (2, 0, None), (2, 0, None), (3, 1, None), (3, 2, None)]
>>> from sage.all import * >>> X = species.SingletonSpecies() >>> B = species.CombinatorialSpecies() >>> B.define(X+B*B) >>> g = B.digraph(); g # needs sage.graphs Multi-digraph on 4 vertices >>> sorted(g, key=str) # needs sage.graphs [Combinatorial species, Product of (Combinatorial species) and (Combinatorial species), Singleton species, Sum of (Singleton species) and (Product of (Combinatorial species) and (Combinatorial species))] >>> d = {sp: i for i, sp in enumerate(g)} # needs sage.graphs >>> g.relabel(d) # needs sage.graphs >>> g.canonical_label().edges(sort=True) # needs sage.graphs [(0, 3, None), (2, 0, None), (2, 0, None), (3, 1, None), (3, 2, None)]
- functorial_composition(g)[source]#
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()[0:5] # needs sage.modules [1, 1, 2, 4, 11]
>>> from sage.all import * >>> E = species.SetSpecies() >>> E2 = E.restricted(min=Integer(2), max=Integer(3)) >>> WP = species.SubsetSpecies() >>> P2 = E2*E >>> G = WP.functorial_composition(P2) >>> G.isotype_generating_series()[Integer(0):Integer(5)] # needs sage.modules [1, 1, 2, 4, 11]
- generating_series(base_ring=None)[source]#
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[: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
>>> from sage.all import * >>> P = species.PermutationSpecies() >>> g = P.generating_series() >>> g[:Integer(4)] [1, 1, 1, 1] >>> g.counts(Integer(4)) [1, 1, 2, 6] >>> P.structures([Integer(1),Integer(2),Integer(3)]).list() [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] >>> len(_) 6
- is_weighted()[source]#
Return
True
if this species has a nontrivial weighting associated with it.EXAMPLES:
sage: C = species.CycleSpecies() sage: C.is_weighted() False
>>> from sage.all import * >>> C = species.CycleSpecies() >>> C.is_weighted() False
- isotype_generating_series(base_ring=None)[source]#
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[0:4] # needs sage.libs.flint [1, 1, 2, 3] sage: g.counts(4) # needs sage.libs.flint [1, 1, 2, 3] sage: P.isotypes([1,2,3]).list() # needs sage.libs.flint [[2, 3, 1], [2, 1, 3], [1, 2, 3]] sage: len(_) # needs sage.libs.flint 3
>>> from sage.all import * >>> P = species.PermutationSpecies() >>> g = P.isotype_generating_series() >>> g[Integer(0):Integer(4)] # needs sage.libs.flint [1, 1, 2, 3] >>> g.counts(Integer(4)) # needs sage.libs.flint [1, 1, 2, 3] >>> P.isotypes([Integer(1),Integer(2),Integer(3)]).list() # needs sage.libs.flint [[2, 3, 1], [2, 1, 3], [1, 2, 3]] >>> len(_) # needs sage.libs.flint 3
- isotypes(labels, structure_class=None)[source]#
EXAMPLES:
sage: F = CombinatorialSpecies() sage: F.isotypes([1,2,3]).list() Traceback (most recent call last): ... NotImplementedError
>>> from sage.all import * >>> F = CombinatorialSpecies() >>> F.isotypes([Integer(1),Integer(2),Integer(3)]).list() Traceback (most recent call last): ... NotImplementedError
- product(g)[source]#
Return the product of
self
andg
.EXAMPLES:
sage: P = species.PermutationSpecies() sage: F = P * P; F Product of (Permutation species) and (Permutation species)
>>> from sage.all import * >>> P = species.PermutationSpecies() >>> F = P * P; F Product of (Permutation species) and (Permutation species)
- restricted(*args, **kwds)[source]#
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()[0:5] [0, 0, 0, 1/6, 1/24]
>>> from sage.all import * >>> S = species.SetSpecies().restricted(min=Integer(3)); S Set species with min=3 >>> S.structures([Integer(1),Integer(2)]).list() [] >>> S.generating_series()[Integer(0):Integer(5)] [0, 0, 0, 1/6, 1/24]
- structures(labels, structure_class=None)[source]#
EXAMPLES:
sage: F = CombinatorialSpecies() sage: F.structures([1,2,3]).list() Traceback (most recent call last): ... NotImplementedError
>>> from sage.all import * >>> F = CombinatorialSpecies() >>> F.structures([Integer(1),Integer(2),Integer(3)]).list() Traceback (most recent call last): ... NotImplementedError
- sum(g)[source]#
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]]
>>> from sage.all import * >>> P = species.PermutationSpecies() >>> F = P + P; F Sum of (Permutation species) and (Permutation species) >>> F.structures([Integer(1),Integer(2)]).list() [[1, 2], [2, 1], [1, 2], [2, 1]]
- weight_ring()[source]#
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
>>> from sage.all import * >>> species.SetSpecies().weight_ring() Rational Field
- weighted(weight)[source]#
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
>>> from sage.all import * >>> t = ZZ['t'].gen() >>> C = species.CycleSpecies(); C Cyclic permutation species >>> C.weighted(t) Cyclic permutation species with weight=t