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 = SymmetricFunctions(QQ).power()
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]
Bases: sage.combinat.species.series.LazyPowerSeries
EXAMPLES:
sage: L = LazyPowerSeriesRing(QQ)
sage: f = L()
sage: loads(dumps(f))
Uninitialized lazy power series
Return the arithmetic product of self with g.
For species and
such that
,
their arithmetic product is the species
of “
-assemblies of cloned
-structures”.
This operation is defined and several examples are given in [MM].
The cycle index series for can be computed in terms of the component series
and
,
as implemented in this method.
INPUT:
OUTPUT:
The arithmetic product of self with g. This is a cycle
index series defined in terms of self and g such that
if self and g are the cycle index series of two species
and
, their arithmetic product is the cycle index series
of the species
.
EXAMPLES:
For the species of (oriented) cycles and
the species of nonempty linear orders,
corresponds
to the species of “regular octopuses”; a
-structure is a cycle of some length, each of whose elements
is an ordered list of a length which is consistent for all the lists in the structure.
sage: C = species.CycleSpecies().cycle_index_series()
sage: Lplus = species.LinearOrderSpecies(min=1).cycle_index_series()
sage: RegularOctopuses = C.arithmetic_product(Lplus)
sage: RegOctSpeciesSeq = RegularOctopuses.generating_series().counts(8)
sage: RegOctSpeciesSeq
[0, 1, 3, 8, 42, 144, 1440, 5760]
It is shown in [MM] that the exponential generating function for regular octopuses satisfies
(where
is
the sum of the divisors of
).
sage: RegOctDirectSeq = [0] + [sum(divisors(i))*factorial(i-1) for i in range(1,8)]
sage: RegOctDirectSeq == RegOctSpeciesSeq
True
AUTHORS:
REFERENCES:
[MM] | (1, 2) M. Maia and M. Mendez. “On the arithmetic product of combinatorial species”. Discrete Mathematics, vol. 308, issue 23, 2008, pp. 5407-5427. Arxiv math/0503436v2. |
Returns the coefficient of a cycle type t.
EXAMPLES:
sage: from sage.combinat.species.generating_series import CycleIndexSeriesRing
sage: p = SymmetricFunctions(QQ).power()
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
Returns the number of structures corresponding to a certain cycle type.
EXAMPLES:
sage: from sage.combinat.species.generating_series import CycleIndexSeriesRing
sage: p = SymmetricFunctions(QQ).power()
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
Returns the expansion of a cycle index series as a symmetric function in n variables.
Specifically, this returns a LazyPowerSeries whose ith term is obtained by calling expand() on the ith term of self.
This relies on the (standard) interpretation of a cycle index series as a symmetric function in the power sum basis.
INPUT:
EXAMPLES:
sage: from sage.combinat.species.set_species import SetSpecies
sage: SetSpecies().cycle_index_series().expand_as_sf(2).coefficients(4)
[1, x0 + x1, x0^2 + x0*x1 + x1^2, x0^3 + x0^2*x1 + x0*x1^2 + x1^3]
Returns the functorial composition of self and g.
If and
are species, their functorial composition is the species
obtained by setting
.
In other words, an
-structure on a set
of labels is an
-structure whose labels are the set of all
-structures on
.
It can be shown (as in section 2.2 of [BLL]) that there is a corresponding operation on cycle indices:
This method implements that operation on cycle index series.
EXAMPLES:
The species of simple graphs can be expressed in terms of a functorial
composition:
, where
is the SubsetSpecies.
This is how it is implemented in SimpleGraphSpecies():
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]]
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]
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]
Returns the stretch of a cycle index series by a positive integer
.
If
then the stretch of
by
is
EXAMPLES:
sage: from sage.combinat.species.generating_series import CycleIndexSeriesRing
sage: p = SymmetricFunctions(QQ).power()
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]]
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]]
Returns the ring of cycle index series. Note that is is just a LazyPowerSeriesRing whose elements have some extra methods.
EXAMPLES:
sage: from sage.combinat.species.generating_series import CycleIndexSeriesRing
sage: R = CycleIndexSeriesRing(QQ); R
Cycle Index Series Ring over Symmetric Functions over Rational Field in the powersum basis
sage: R([1]).coefficients(4)
[1, 1, 1, 1]
TESTS: We test to make sure that caching works.
sage: R is CycleIndexSeriesRing(QQ)
True
Bases: sage.combinat.species.series.LazyPowerSeriesRing
EXAMPLES:
sage: from sage.combinat.species.generating_series import CycleIndexSeriesRing
sage: R = CycleIndexSeriesRing(QQ); R
Cycle Index Series Ring over Symmetric Functions over Rational Field in the powersum basis
sage: R == loads(dumps(R))
True
Bases: sage.combinat.species.series.LazyPowerSeries
EXAMPLES:
sage: L = LazyPowerSeriesRing(QQ)
sage: f = L()
sage: loads(dumps(f))
Uninitialized lazy power series
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]
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]
Returns the exponential generating series which is the functorial composition of self with y.
If and
, then
functorial composition
is defined as
REFERENCES:
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]
Returns the ring of ordinary generating series. Note that is is just a LazyPowerSeriesRing whose elements have some extra methods.
EXAMPLES:
sage: from sage.combinat.species.generating_series import ExponentialGeneratingSeriesRing
sage: R = ExponentialGeneratingSeriesRing(QQ); R
Lazy Power Series Ring over Rational Field
sage: R([1]).coefficients(4)
[1, 1, 1, 1]
sage: R([1]).counts(4)
[1, 1, 2, 6]
TESTS: We test to make sure that caching works.
sage: R is ExponentialGeneratingSeriesRing(QQ)
True
Bases: sage.combinat.species.series.LazyPowerSeriesRing
EXAMPLES:
sage: from sage.combinat.species.generating_series import ExponentialGeneratingSeriesRing
sage: R = ExponentialGeneratingSeriesRing(QQ)
sage: R == loads(dumps(R))
True
Bases: sage.combinat.species.series.LazyPowerSeries
EXAMPLES:
sage: L = LazyPowerSeriesRing(QQ)
sage: f = L()
sage: loads(dumps(f))
Uninitialized lazy power series
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
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]
Returns the ring of ordinary generating series. Note that is is just a LazyPowerSeriesRing whose elements have some extra methods.
EXAMPLES:
sage: from sage.combinat.species.generating_series import OrdinaryGeneratingSeriesRing
sage: R = OrdinaryGeneratingSeriesRing(QQ); R
Lazy Power Series Ring over Rational Field
sage: R([1]).coefficients(4)
[1, 1, 1, 1]
sage: R([1]).counts(4)
[1, 1, 1, 1]
TESTS: We test to make sure that caching works.
sage: R is OrdinaryGeneratingSeriesRing(QQ)
True
Bases: sage.combinat.species.series.LazyPowerSeriesRing
EXAMPLES:
sage: from sage.combinat.species.generating_series import OrdinaryGeneratingSeriesRing
sage: R = OrdinaryGeneratingSeriesRing(QQ)
sage: R == loads(dumps(R))
True
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]