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

Partitions

A partition splits up a natural number into a sum of nonincreasing positive naturals. In the modular forms post we discussed the Dedekind function.

Of course that is an infinite product that is hard to compute. It is hard to read off the coefficients especially for large n. Imagine asking specifically how many different partitions there are for 1000. It blows up pretty fast.



The above gives a pretty good approximation to its growth. For 1000 it is 1.4% off.

Still that's an estimate and exactly how good it is is questionable. There are also some infinite convergent sums, but that again has the same issues as infinite products.

In January, Ono said

"I can take any number, plug it into P, and instantly calculate the partitions of that number. P does not return gruesome numbers with infinitely many decimal places. It’s the finite, algebraic formula that we have all been looking for."

Apparently it is done with a "self similarity" of some specific subsequences. I'll just refer to the paper, but it is pretty clearly epic.

Edit: November 10, 2011

He gave a colloquium today. He explained the connection with Maass forms and mock theta functions.
http://en.wikipedia.org/wiki/Mock_modular_form