species-0.3.0.2: Computational combinatorial species

Stability experimental byorgey@cis.upenn.edu

Math.Combinatorics.Species.CycleIndex

Contents

Description

An interpretation of species expressions as cycle index series. For details on cycle index series, see "Combinatorial Species and Tree-Like Structures", chapter 1.

Synopsis

# Documentation

Convert a cycle index series to an exponential generating function: F(x) = Z_F(x,0,0,0,...).

Convert a cycle index series to an ordinary generating function: F~(x) = Z_F(x,x^2,x^3,...).

Extract a particular coefficient from a cycle index series.

Compute `fix F[n]`, i.e. the number of F-structures fixed by a permutation with cycle type n, given the cycle index series Z_F.

In particular, `fix F[n] = aut(n) * zCoeff Z_F n`.

# Miscellaneous

`aut js` is is the number of automorphisms of a permutation with cycle type `js` (i.e. a permutation which has `n` cycles of size `i` for each `(i,n)` in `js`). Another way to look at it is that there are `n!/aut js` permutations on n elements with cycle type `js`. The result type is a `FactoredRational.T`.

Enumerate all partitions of an integer. In particular, if `p` is an element of the list output by `intPartitions n`, then ```sum . map (uncurry (*)) \$ p == n```. The result type is `[CycleType]` since each integer partition of `n` corresponds to the cycle type of a permutation on `n` elements.

The partitions are generated in an order corresponding to the Ord instance for `Monomial`.

`cyclePower s n` computes the cycle type of sigma^n, where sigma is any permutation of cycle type s.

In particular, if s = (s_1, s_2, s_3, ...) (i.e. sigma has s_1 fixed points, s_2 2-cycles, ... s_k k-cycles), then

sigma^n_j = sum_{j*gcd(n,k) = k} gcd(n,k)*s_k