Stability | experimental |
---|---|

Maintainer | byorgey@cis.upenn.edu |

Safe Haskell | None |

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 -> 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 -> 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`

.

# 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

.
`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