Combinatorial species

Consider a species which assigns to each finite set some other finite set.

For example, assign to the set A, the set of all it's permutations.

Because a species only depends on the size of A, we get a list of integers  which describe the size of the output set. Put these together in an exponential generating function to get   . Addition, multiplication and composition of generating functions give operations on species.

Of course this doesn't take into account automorphisms. Let's say our species was trees that had elements of A as vertices. Then and  would appear different even though they are only off by a permutation of the three element set A. We can identify all of these together and get a isomorphism type generating function

In addition there is the more general function for a species called the cycle index series.

 is the number of cycles of length i in said permutation and  is the number of F structures on the n element set A which has such an automorphism.

You get a whole bunch of identities for all the operations you can perform on species.

To understand this function first look at it for a specific n. For example consider a cube. It has 24 automorphisms acting on 6 faces.

There is the identity which consists of 6 1-cycles. It therefore contributes 

There are 6 quarter turn face rotations which consist of 2 1-cycles and 1 4-cycle. It contributes 

There are 3 half turn face rotations which consist of 2 1-cycles and 2 2-cycles. It contributes 

There are 8 1/3 rotations around the main diagonal. This gives 2 3-cycles. You can see the pattern by now.

There are 6 180 degree rotations around the diagonal connecting the midpoints of opposite edges.

Add these all together and you get the cycle index function associated to this group of automorphisms acting on the set of 6 faces. Putting this with our previous definition of cycle index series you see that the species used here was the one that had   or 0 depending on whether that permutation of 6 elements was or was not a symmetry of the cube. 

http://en.wikipedia.org/wiki/Combinatorial_species

http://en.wikipedia.org/wiki/Cycle_index