| Copyright | (c) Brent Yorgey 2010 |
|---|---|
| License | BSD-style (see LICENSE) |
| Maintainer | byorgey@cis.upenn.edu |
| Stability | experimental |
| Safe Haskell | None |
| Language | Haskell2010 |
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.
- 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 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 -> 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
Orphan instances
| Species CycleIndex Source # | An interpretation of species expressions as cycle index series.
For the definition of the |