species- Computational combinatorial species





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



zToEGF :: CycleIndex -> EGFSource

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

zToGF :: CycleIndex -> GFSource

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

zCoeff :: CycleIndex -> CycleType -> RationalSource

Extract a particular coefficient from a cycle index series.

zFix :: CycleIndex -> CycleType -> IntegerSource

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.


aut :: CycleType -> TSource

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

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 :: CycleType -> Integer -> CycleTypeSource

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