Generating Series¶

This file makes a number of extensions to lazy power series by endowing them with some semantic content for how they’re to be interpreted.

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/combinatse10.html. One notable difference is that we use power-sum symmetric functions as the coefficients of our cycle index series.

TESTS:

sage: from sage.combinat.species.stream import Stream, _integers_from
sage: from sage.combinat.species.generating_series import CycleIndexSeriesRing
sage: p = SFAPower(QQ)
sage: CIS = CycleIndexSeriesRing(QQ)

sage: geo1 = CIS((p([1])^i  for i in _integers_from(0)))
sage: geo2 = CIS((p([2])^i  for i in _integers_from(0)))
sage: s = geo1 * geo2
sage: s[0]
p[]
sage: s[1]
p[1] + p[2]
sage: s[2]
p[1, 1] + p[2, 1] + p[2, 2]
sage: s[3]
p[1, 1, 1] + p[2, 1, 1] + p[2, 2, 1] + p[2, 2, 2]

Whereas the coefficients of the above test are homogeneous with respect to total degree, the following test groups with respect to weighted degree where each variable x_i has weight i.

sage: def g():
...       for i in _integers_from(0):
...           yield p([2])^i
...           yield p(0)
sage: geo1 = CIS((p([1])^i  for i in _integers_from(0)))
sage: geo2 = CIS(g())
sage: s = geo1 * geo2
sage: s[0]
p[]
sage: s[1]
p[1]
sage: s[2]
p[1, 1] + p[2]
sage: s[3]
p[1, 1, 1] + p[2, 1]
sage: s[4]
p[1, 1, 1, 1] + p[2, 1, 1] + p[2, 2]

class sage.combinat.species.generating_series.CycleIndexSeries(A, stream=None, order=None, aorder=None, aorder_changed=True, is_initialized=False, name=None)¶

Bases: sage.combinat.species.series.LazyPowerSeries

coefficient_cycle_type(t)¶

Returns the coefficient of a cycle type t.

EXAMPLES:

sage: from sage.combinat.species.generating_series import CycleIndexSeriesRing
sage: p = SFAPower(QQ)
sage: CIS = CycleIndexSeriesRing(p)
sage: f = CIS([0, p([1]), 2*p([1,1]),3*p([2,1])])
sage: f.coefficient_cycle_type([1])
1
sage: f.coefficient_cycle_type([1,1])
2
sage: f.coefficient_cycle_type([2,1])
3

count(t)¶

Returns the number of structures corresponding to a certain cycle type.

EXAMPLES:

sage: from sage.combinat.species.generating_series import CycleIndexSeriesRing
sage: p = SFAPower(QQ)
sage: CIS = CycleIndexSeriesRing(p)
sage: f = CIS([0, p([1]), 2*p([1,1]),3*p([2,1])])
sage: f.count([1])
1
sage: f.count([1,1])
4
sage: f.count([2,1])
6

functorial_composition(g)¶

Returns the functorial composition of self and g.

If $F$ , $G$ , and $H$ are combinatorial species such that ` H = F Box G $, then the cycle index series `Z_H = Z_F \Box Z_G$ is defined as

EXAMPLES:

sage: S = species.SimpleGraphSpecies()
sage: S.cycle_index_series().coefficients(5)
[p[],
 p[1],
 p[1, 1] + p[2],
 4/3*p[1, 1, 1] + 2*p[2, 1] + 2/3*p[3],
 8/3*p[1, 1, 1, 1] + 4*p[2, 1, 1] + 2*p[2, 2] + 4/3*p[3, 1] + p[4]]

generating_series()¶

EXAMPLES:

sage: P = species.PartitionSpecies()
sage: cis = P.cycle_index_series()
sage: f = cis.generating_series()
sage: f.coefficients(5)
[1, 1, 1, 5/6, 5/8]

isotype_generating_series()¶

EXAMPLES:

sage: P = species.PermutationSpecies()
sage: cis = P.cycle_index_series()
sage: f = cis.isotype_generating_series()
sage: f.coefficients(10)
[1, 1, 2, 3, 5, 7, 11, 15, 22, 30]

stretch(k)¶

Returns the stretch of a cycle index series by a positive integer $k$ .

If

$f = \sum_{n=0}^{\infty} f_n(x_1, x_2, \ldots, x_n),$

then the stretch $g$ of $f$ by $k$ is

$g = \sum_{n=0}^{\infty} f_n(x_k, x_{2k}, \ldots, x_{nk}).$

EXAMPLES:

sage: from sage.combinat.species.generating_series import CycleIndexSeriesRing
sage: p = SFAPower(QQ)
sage: CIS = CycleIndexSeriesRing(p)
sage: f = CIS([p([1])])
sage: f.stretch(3).coefficients(10)
[p[3], 0, 0, p[3], 0, 0, p[3], 0, 0, p[3]]

weighted_composition(y_species)¶

Returns the composition of this cycle index series with the cycle index series of y_species where y_species is a weighted species. Note that this is basically the same algorithm as composition except we can’t use the optimization that the powering of cycle index series commutes with ‘stretching’.

EXAMPLES:

sage: E = species.SetSpecies(); C = species.CycleSpecies()
sage: E_cis = E.cycle_index_series()
sage: E_cis.weighted_composition(C).coefficients(4)
[p[], p[1], p[1, 1] + p[2], p[1, 1, 1] + p[2, 1] + p[3]]
sage: E(C).cycle_index_series().coefficients(4)
[p[], p[1], p[1, 1] + p[2], p[1, 1, 1] + p[2, 1] + p[3]]

class sage.combinat.species.generating_series.CycleIndexSeriesRing_class(R)¶: Bases: sage.combinat.species.series.LazyPowerSeriesRing

class sage.combinat.species.generating_series.ExponentialGeneratingSeries(A, stream=None, order=None, aorder=None, aorder_changed=True, is_initialized=False, name=None)¶

Bases: sage.combinat.species.series.LazyPowerSeries

count(n)¶

Returns the number of structures of size n.

EXAMPLES:

sage: from sage.combinat.species.generating_series import ExponentialGeneratingSeriesRing
sage: R = ExponentialGeneratingSeriesRing(QQ)
sage: f = R([1])
sage: [f.count(i) for i in range(7)]
[1, 1, 2, 6, 24, 120, 720]

counts(n)¶

Returns the number of structures on a set for size i for i in range(n).

EXAMPLES:

sage: from sage.combinat.species.generating_series import ExponentialGeneratingSeriesRing
sage: R = ExponentialGeneratingSeriesRing(QQ)
sage: f = R(range(20))
sage: f.counts(5)
[0, 1, 4, 18, 96]

functorial_composition(y)¶

Returns the exponential generating series which is the functorial composition of self with y.

If $f = \sum_{n=0}^{\infty} f_n \frac{x^n}{n!}$ and $g = \sum_{n=0}^{\infty} f_n \frac{x^n}{n!}$ , then functorial composition $f \Box g$ is defined as

$f \Box g = \sum_{n=0}^{\infty} f_{g_n} \frac{x^n}{n!}$

REFERENCES:

Section 2.2 of BLL.

EXAMPLES:

sage: G = species.SimpleGraphSpecies()
sage: g = G.generating_series()
sage: g.coefficients(10)
[1, 1, 1, 4/3, 8/3, 128/15, 2048/45, 131072/315, 2097152/315, 536870912/2835]

class sage.combinat.species.generating_series.ExponentialGeneratingSeriesRing_class(R)¶: Bases: sage.combinat.species.series.LazyPowerSeriesRing

class sage.combinat.species.generating_series.OrdinaryGeneratingSeries(A, stream=None, order=None, aorder=None, aorder_changed=True, is_initialized=False, name=None)¶

Bases: sage.combinat.species.series.LazyPowerSeries

count(n)¶

Returns the number of structures on a set of size n.

EXAMPLES:

sage: from sage.combinat.species.generating_series import OrdinaryGeneratingSeriesRing
sage: R = OrdinaryGeneratingSeriesRing(QQ)
sage: f = R(range(20))
sage: f.count(10)
10

counts(n)¶

Returns the number of structures on a set for size i for i in range(n).

EXAMPLES:

sage: from sage.combinat.species.generating_series import OrdinaryGeneratingSeriesRing
sage: R = OrdinaryGeneratingSeriesRing(QQ)
sage: f = R(range(20))
sage: f.counts(10)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

class sage.combinat.species.generating_series.OrdinaryGeneratingSeriesRing_class(R)¶: Bases: sage.combinat.species.series.LazyPowerSeriesRing

sage.combinat.species.generating_series.factorial_gen()¶

A generator for the factorials starting at 0.

EXAMPLES:

sage: from sage.combinat.species.generating_series import factorial_gen
sage: g = factorial_gen()
sage: [g.next() for i in range(5)]
[1, 1, 2, 6, 24]

Generating Series¶

Previous topic

Next topic

This Page

Navigation

Generating Series¶

Previous topic

Next topic

This Page

Quick search

Navigation