Math.Combinatorics.Species.CycleIndex
 Contents Miscellaneous
Description
An instance of Species for cycle index series. For details on cycle index series, see "Combinatorial Species and Tree-Like Structures", chapter 1.
Synopsis
 zToEGF :: CycleIndex -> EGF zToGF :: CycleIndex -> GF zCoeff :: CycleIndex -> CycleType -> Rational zFix :: CycleIndex -> CycleType -> Integer aut :: CycleType -> T intPartitions :: Integer -> [CycleType] cyclePower :: CycleType -> Integer -> CycleType
Documentation
 zToEGF :: CycleIndex -> EGF Source
Convert a cycle index series to an exponential generating function: F(x) = Z_F(x,0,0,0,...).
 zToGF :: CycleIndex -> GF Source
Convert a cycle index series to an ordinary generating function: F~(x) = Z_F(x,x^2,x^3,...).
 zCoeff :: CycleIndex -> CycleType -> Rational Source
Extract a particular coefficient from a cycle index series.
 zFix :: CycleIndex -> CycleType -> Integer Source

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 :: CycleType -> T Source
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.
 intPartitions :: Integer -> [CycleType] Source

Generate 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 :: CycleType -> Integer -> CycleType Source

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