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 = 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]
-
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
EXAMPLES:
sage: L = LazyPowerSeriesRing(QQ) sage: f = L() sage: loads(dumps(f)) Uninitialized lazy power series
-
arithmetic_product
(g, check_input=True)¶ Return the arithmetic product of
self
withg
.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:
g
– a cycle index series having the same parent asself
.check_input
– (default:True
) a Boolean which, when set toFalse
, will cause input checks to be skipped.
OUTPUT:
The arithmetic product of
self
withg
. This is a cycle index series defined in terms ofself
andg
such that ifself
andg
are the cycle index series of two speciesand
, 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:
- Andrew Gainer-Dewar (2013)
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.
-
coefficient_cycle_type
(t)¶ Returns the coefficient of a cycle type
t
inself
.EXAMPLES:
sage: from sage.combinat.species.generating_series import CycleIndexSeriesRing sage: p = SymmetricFunctions(QQ).power() sage: CIS = CycleIndexSeriesRing(QQ) 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
-
compositional_inverse
()¶ Return the compositional inverse of
self
if possible.(Specifically, if
self
is of the form.)
The compositional inverse is the inverse with respect to plethystic substitution. This is the operation on cycle index series which corresponds to substitution, a.k.a. partitional composition, on the level of species. See Section 2.2 of [BLL] for a definition of this operation.
EXAMPLES:
sage: Eplus = species.SetSpecies(min=1).cycle_index_series() sage: Eplus(Eplus.compositional_inverse()).coefficients(8) [0, p[1], 0, 0, 0, 0, 0, 0]
TESTS:
sage: Eplus = species.SetSpecies(min=2).cycle_index_series() sage: Eplus.compositional_inverse() Traceback (most recent call last): ... ValueError: not an invertible series
ALGORITHM:
Let
be a species satisfying
for
the species of singletons. (Equivalently,
and
.) Then there exists a (virtual) species
satisfying
.
It follows that
. Rearranging, we obtain the recursive equation
, which can be solved using iterative methods.
Warning
This algorithm is functional but can be very slow. Use with caution!
See also
The compositional inverse
of the species
of nonempty sets can be handled much more efficiently using specialized methods. These are implemented in
CombinatorialLogarithmSeries
.AUTHORS:
- Andrew Gainer-Dewar
-
count
(t)¶ Return the number of structures corresponding to a certain cycle type
t
.EXAMPLES:
sage: from sage.combinat.species.generating_series import CycleIndexSeriesRing sage: p = SymmetricFunctions(QQ).power() sage: CIS = CycleIndexSeriesRing(QQ) 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
-
expand_as_sf
(n, alphabet='x')¶ 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 callingexpand()
on the ith term ofself
.This relies on the (standard) interpretation of a cycle index series as a symmetric function in the power sum basis.
INPUT:
self
– a cycle index seriesn
– a positive integeralphabet
– a variable for the expansion (default:)
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]
-
functorial_composition
(g)¶ Returns the functorial composition of
self
andg
.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 inSimpleGraphSpecies()
: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)¶ Return the stretch of the cycle index series
self
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(QQ) sage: f = CIS([p([]), p([1]), p([2]), p.zero()]) sage: f.stretch(3).coefficients(10) [p[], 0, 0, p[3], 0, 0, p[6], 0, 0, 0]
-
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 not 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]]
-
-
sage.combinat.species.generating_series.
CycleIndexSeriesRing
(R)¶ Return the ring of cycle index series over
R
.This is the ring of formal power series
, where
is the ring of symmetric functions over
R
in the-basis. Its purpose is to house the cycle index series of species (in a somewhat nonstandard notation tailored to Sage): If
is a species, then the cycle index series of
is defined to be the formal power series
where
denotes the number of fixed points of the permutation
of
. We notice that this power series is “equigraded” (meaning that its
-coefficient is homogeneous of degree
). A more standard convention in combinatorics would be to use
instead of
, and drop the
(that is, evaluate the above power series at
); but this would be more difficult to implement in Sage, as it would be an element of a power series ring in infinitely many variables.
Note that is is just a
LazyPowerSeriesRing
(whose base ring is) 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) # This is not combinatorially ....: # meaningful. [1, 1, 1, 1]
TESTS: We test to make sure that caching works.
sage: R is CycleIndexSeriesRing(QQ) True
-
class
sage.combinat.species.generating_series.
CycleIndexSeriesRing_class
(R)¶ 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
-
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
EXAMPLES:
sage: L = LazyPowerSeriesRing(QQ) sage: f = L() sage: loads(dumps(f)) Uninitialized lazy power series
-
count
(n)¶ Return 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)¶ Return the number of structures on a set for size
i
for eachi
inrange(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)¶ Return the exponential generating series which is the functorial composition of
self
withy
.If
and
, then functorial composition
is defined as
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]
-
-
sage.combinat.species.generating_series.
ExponentialGeneratingSeriesRing
(R)¶ Return the ring of exponential generating series over
R
.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
-
class
sage.combinat.species.generating_series.
ExponentialGeneratingSeriesRing_class
(R)¶ 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
-
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
EXAMPLES:
sage: L = LazyPowerSeriesRing(QQ) sage: f = L() sage: loads(dumps(f)) Uninitialized lazy power series
-
count
(n)¶ Return 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)¶ Return the number of structures on a set for size
i
for eachi
inrange(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]
-
-
sage.combinat.species.generating_series.
OrdinaryGeneratingSeriesRing
(R)¶ Return the ring of ordinary generating series over
R
.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
-
class
sage.combinat.species.generating_series.
OrdinaryGeneratingSeriesRing_class
(R)¶ 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
-
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: [next(g) for i in range(5)] [1, 1, 2, 6, 24]