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

Maintainer | byorgey@cis.upenn.edu |

An interpretation of species as ordinary generating functions, which count unlabelled structures.

- unlabelled :: SpeciesAST -> [Integer]

# Documentation

unlabelled :: SpeciesAST -> [Integer]Source

Extract the coefficients of an ordinary generating function as a
list of Integers. In particular,

is the
number of unlabelled `unlabelled`

s `!!`

n`s`

-structures on an underlying set of size
`n`

(`unlabelled s`

is guaranteed to be infinite). For example:

> take 10 $ unlabelled octopi [0,1,2,3,5,7,13,19,35,59]

gives the number of unlabelled octopi on 0, 1, 2, 3, ... 9 elements.

Actually, the above is something of a white lie, as you may have
already realized by looking at the input type of `unlabelled`

,
which is `SpeciesAST`

rather than the expected `GF`

. The reason
is that although products and sums of unlabelled species
correspond to products and sums of ordinary generating functions,
other operations such as composition and differentiation do not!
In order to compute an ordinary generating function for a species
defined in terms of composition and/or differentiation, we must
compute the cycle index series for the species and then convert
it to an ordinary generating function. So `unlabelled`

actually
works by first reifying the species to an AST and checking which
operations are used in its definition, and then choosing to work
with cycle index series or directly with (much faster) ordinary
generating functions as appropriate.