Last summer, Todd and I discussed a problem and its solution, and I had wondered if it was fit enough to be in the POW-series (on this blog) when he mentioned that the problem might be somewhat too easy for that purpose. Of course, I immediately saw that he was right. But, a few days back, I thought it wouldn’t be bad if we shared this cute problem and its solution over here, the motivation being that *some* of our readers may perhaps gain something out of it. What is more, an analysis of an egf solution to the problem lends itself naturally to a discussion of combinatorial species. Todd will talk more about it in the second half of this post. Anyway, let’s begin.

PROBLEM: Suppose , where is a positive natural number. Find the number of endofunctions satisfying the idempotent property, i.e. .

It turns out that finding a solution to the above problem is equivalent to counting the *number of forests with* *nodes and height at most* , which I found here (*click only if you wish to see the answer*!) at the Online Encyclopedia of Integer Sequences. If you haven’t clicked on that link yet and wish to solve the problem on your own, then please stop reading beyond this point.

**SOLUTION:** There are two small (and related) observations that need to be made. And, both are easy ones.

Lemma 1:has at least one fixed point.

Proof:Pick any and let , where . Then, using the idempotent property, we have , which implies . Therefore, is a fixed point, and this proves our lemma.

Lemma 2:The elements in that arenotfixed points are mapped to fixed points of .

Proof:Suppose isnota fixed point such that . Then, using the idempotent property again, we immediately have , which implies , thereby establishing the fact that itself is a fixed point. Hence, (which is not a fixed point) is mapped to some fixed point of .

In both the lemmas above, the idempotent property “forces” everything.

Now, the solution is right before our eyes! Suppose has fixed points. Then there are ways of choosing them. And, each of the remaining elements of that are not fixed points are to be mapped to any one of the fixed points. And, there are a total of ways of doing that. So, summing over all , our final answer is .

### Exponential Generating Function and Introduction to Species

Hi; Todd here. Vishal asked whether I would discuss this problem from the point of view of exponential generating functions (or egf’s), and also from a categorical point of view, using the concept of *species* *of structure*, which gives the basis for a categorical or structural approach to generatingfunctionology.

I’ll probably need to write a new post of my own to do any sort of justice to these topics, but maybe I can whet the reader’s appetite by talking a little about the underlying philosophy, followed by a quick but possibly cryptic wrap-up which I could come back to later for illustrative purposes.

Enumerative combinatorics studies the problem of counting the number of combinatorial structures of some type on an -element set, such as the number of idempotent functions on that set, or the number of equivalence relations, and so on. A powerful idea in enumerative combinatorics is the idea of a generating function, where we study the series by rolling them into a single analytic function, such as

(this the so-called “exponential” generating function of ). In many cases of interest, the function will be recognizable in terms of operations familiar from calculus (addition, multiplication, differentiation, composition, etc.), and this can then be used to extract information about the series , such as explicit formulas, asymptotics, and so on. If you’ve never seen this idea in action, you should definitely take a look at Wilf’s book generatingfunctionology, or at the book Concrete Mathematics by Graham, Knuth and Patashnik.

Each of the basic operations one performs on analytic functions (addition, multiplication, composition, etc.) will, it turns out, correspond to some set-theoretic operation directly at the level of combinatorial structures, and one of the trade secrets of generating function technology is to have very clear *pictures* of the combinatorial structures being counted, and how these pictures are built up using these basic structural operations.

In fact, why don’t we start right now, and figure out what some of these structural operations would be? In other words, let’s ask ourselves: if and are generating functions for counting combinatorial structures of type (or species) and , then what types of structures would the function “count”? How about ? Composition ?

The case of is easy: writing

and thinking of as counting structures of type on an -element set, and as counting structures of type , the quantity counts elements in the disjoint union of the sets of -structures and -structures.

In the categorical approach we will discuss later, we actually think of structure types (or species of structure) as *functors*, which take an -element set to the set of structures of type on . Here, we have to be a little bit careful about what categories we’re talking about, but the general idea is that if we have a *bijection* from one -element set to another, then it should always be possible to “transport” -structures on to -structures on , simply by relabeling points along the bijection . So, let us define a *species* to be a functor

where is the category of finite sets and *bijections* (not all functions, just bijections!), and is the category of sets. In enumerative combinatorics, the set is normally assumed to be finite, but in other applications of the notion of species, we actually allow a lot more latitude, and allow the functor to map into other categories , not just (“-valued species”). But if we stick for now just to set-valued species , , then we define the species by the functorial formula

where denotes disjoint union. So addition of generating functions will correspond to the concrete operation of taking disjoint unions of sets of combinatorial species.

More interesting is the case of multiplication. Let’s calculate the product of two egf’s:

The question is: what type of structure does the expression “count”? Look at the individual terms: the binomial coefficient describes the number of ways of decomposing an -element set into two disjoint subsets, one with elements and the other with , where and add to . Then, is the number of ways of putting an -structure on the -element part, and is the number of -structures on the -element part.

This suggests a new operation on structure types: given structure types or species , we define a new species according to the formula

(that is, a structure of type on a set is an ordered pair, consisting of an -structure on a subset of and a -structure on its complement). This functorial operation is usually called the “convolution product” of the combinatorial species : it is the concrete set-theoretic operation which corresponds to multiplication of generating functions.

Finally, let’s look at composition . Here we make the technical assumption that (no -structures on the empty set!), so that we won’t have divergence issues blowing up in our faces: we want to remain safely within the realm of finitary structures. Okay, then, what type of combinatorial structure does *this* egf count?

Perhaps not surprisingly, this is rather more challenging than the previous two examples. In analytic function language, we are trying here to give a meaning to the Taylor coefficients of a composite function in terms of the Taylor coefficients of the original functions — for this, there is a famous formula attributed to Faà di Bruno, which we then want to interpret combinatorially. **If you don’t already know this but want to think about this on your own, then stop reading!** But I’ll just give away the answer, and say no more for now about where it comes from, although there’s a good chance you can figure it out just by staring at it for a while, possibly with paper and pen in hand.

**Definition:** Let be species (functors from finite sets and bijections to finite sets), and assume . The *substitution product* is defined by the formula

This clearly requires some explanation. The sum here denotes disjoint union, and denotes the set of equivalence relations on the finite set . So here is an equivalence relation, which partitions into nonempty sets (-equivalence classes). And the quotient denotes the set of such equivalence classes (so we think of each class as a point of ). What this formula says is that a structure of type on consists of a partition of into a bunch of non-empty blobs, a -structure on each blob, and then an -structure on the set of blobs.

It’s high time for an example! So let’s look at Vishal’s problem, and see if we can picture it in terms of these operations. We’re going to need some basic functions (or functors!) to apply these operations to, and out of thin air I’ll pluck the two basic ones we’ll need:

The first is the generating function for the series . So for the species , there’s just one structure of type for each set (in categorical language, the functor is the terminal functor). We can just think of that structure as the set itself, if we like, with no other structure appended thereon.

For , we have unless , where . So is the species for the one-element set structure (meaning that unless has cardinality 1, in which case ).

Okay, on to Vishal’s example. He was counting the number of idempotent functions , and now, as promised, I want to determine the corresponding egf. You might be able to find it by looking at his formula, but obviously I want to use the ideas I’ve developed thus far, which focuses much more on the *pictures*. So, let’s picture , first as Vishal did, by thinking of the elements of as ‘nodes’, and then drawing a directed edge from node to node if . (Then, by idempotence of , will be a fixed point of . Let’s agree not to bother drawing an edge from to itself, if is already a fixed point.)

In this picture, we get a directed graph which consists of a disjoint union of “sprouts”: little bushes, each rooted at a fixed point of , whose only other nodes are “leaves” joined to the root by an edge. We can simplify the picture a little: if you put a circle around each sprout, you don’t need the edges at all: just mark one of the points inside as the root, and you know what to do.

So we arrive at a picture of an idempotent function on : a partition of into a collection of (nonempty) blobs, and inside each blob, one of the points is marked “root”. In terms of our operations, what does it mean to mark a point in a blob? It just means: break the blob into two pieces, where one piece is given the structure of “one-element set”, and the other piece is just itself. In terms of the ideas developed above, this means each blob carries a structure; we’ll suggestively write this structure type as .

In this picture of idempotent , there is no extra combinatorial structure imposed on the set of blobs, beyond the set itself. In other words, in this picture, the set of blobs carries merely an “-structure”, nothing more.

So, putting all this together, we picture an idempotent function on as a partition or equivalence relation on , together with an assignment of a marked point in each equivalence class. In the language of species operations, we may therefore identify the structure type of idempotent functions with

or more suggestively, . The exponential generating function is, of course, !

In summary, the theory of species is a *functorial calculus* which projects onto its better-known “shadow”, the *functional calculus* of generating functions. That is to say, we lift operations on enumeration sequences , as embodied in their generating functions, directly up to the level of the sets we’re counting, where the functorial operations become both richer and more concrete. The functorial analogue of the generating function itself is called the “analytic functor” attached to the species (the species itself being the concrete embodiment of the enumeration).

Much more could be said, of course. Instead, here’s a little exercise which can be solved by working through the ideas presented here: write down the egf for the number of ways a group of people can be split into pairs, and give an explicit formula for this number. Those of you who have studied quantum field theory may recognize this already (and certainly the egf is very suggestive!) ; in that case, you might find interesting the paper by Baez and Dolan, From Finite Sets to Feynman Diagrams, where the functorial point of view is used to shed light on, e.g., creation and annihilation operators in terms of simple combinatorial operations.

The literature on species (in all its guises) is enormous, but I’d strongly recommend reading the original paper on the subject:

- André Joyal, Une théorie combinatoire des séries formelles, Adv. Math. 42 (1981), 1-82.

which I’ve actually referred to before, in connection with a POW whose solution involves counting tree structures. Joyal could be considered to be a founding father of what I would call the “Montreal school of combinatorics”, of which a fine representative text would be

- F. Bergeron, G. Labelle, and P. Leroux, Combinatorial Species and Tree-like Structures, Encyclopedia of Mathematics and its Applications 67, 1998.

More to come, I hope!

## 26 comments

Comments feed for this article

March 30, 2009 at 5:11 pm

Vishal LamaTodd,

My jaw almost dropped when I saw the egf solution to the idempotent endofunction problem! That was pretty fantastic! Also, it became crystal clear (after a little mulling) why that problem is equivalent to counting the number of forests with nodes and height at most . It only became clear after your drew pictures of those “sprouts”! :-)

And, to solve that little exercise you gave, asking one to count the number of ways a group of people can be divided into pairs, here’s the solution – thank you for reminding me about that factorial term that I earlier kept forgetting! We have a set of blobs, each of which contains exactly two people,

i.e.each blob is a 2-element set. The egf of each blob, therefore, is because there is exactly one way of putting two people in a group and so while for all other . Now, the set of blobs themselves don’t have any extra combinatorial structure; it is simply an “- structure.” So, the final egf is simply .And, extracting the coefficient of the -th term from the egf above, we get , which yields .

Your write-up has certainly whetted my appetite for species! I do hope you will write more on this topic in the future!

March 30, 2009 at 6:20 pm

Todd TrimbleThat’s right, Vishal! Interestingly, this species or structure type of possible pairings on a finite set shows up in quantum field theory (which I would like to eventually learn, with the help of the guys over at the n-Category Café), in connection with something called Wick’s theorem. The pairings are interpreted as Feynman diagrams for free (non-interacting) particles, if I’m not mistaken; see e.g. the text by Peskin and Schroeder, section 4.3.

Similar considerations allow one to easily deduce that the egf for the structure type of equivalence relations is .

One question which arises here is: why the

exponentialgenerating function? Who ordered those factorials in the denominator? I would like to talk about that as well.March 30, 2009 at 6:32 pm

Vishal LamaOk, let me see if I get this right. The structure type of equivalence relations on a set (say) corresponds to a set of blobs, each of which is just a subset of . So, each blob again is an -structure except that no blob can be empty (due to the definition of an equivalence relation!) Hence, the egf of each blob is . Now, the set of blobs itself is an structure. So, the final egf is just . Is that right?!

March 30, 2009 at 8:23 pm

Todd TrimbleExactly right!

March 30, 2009 at 8:42 pm

Vishal LamaSweet!

I am reading Baez and Dolan’s paper ‘From Finite Sets to Feynman Diagrams’, most of which, it seems, is quite accessible!

March 30, 2009 at 11:51 pm

Vishal LamaTodd,

In response to the following remark you made,

“

One question which arises here is: why the exponential generating function? Who ordered those factorials in the denominator?”does the following observation have a connection with it?

Baez and Dolan’s paper, that I mentioned above, defines the

cardinalityof a category, , as , where summation is done over ‘isomorphism classes of objects ‘ by choosing a representative object from each of those isomorphism classes and is the automorphism class of . So, clearly, if , then an isomorphism class consists of all -element sets, where . Now, choosing any -element set as a representative element from an isomorphism class, we have , which is of course the number ofpermutationsof an -element set! Hence, as the paper points out, we have .Is the above why we use exponential generating function?! I could be wrong here or that my observation is incomplete!

March 31, 2009 at 2:53 am

Todd TrimbleCertainly it’s related, Vishal. The suggests, as you surmise, symmetric groups. More specifically, the category FB of finite sets and bijections is (in the technical sense) equivalent to the category which is the disjoint union of finite symmetric groups . Thus, one could just as well think of a species (as defined in my post) as essentially a functor

which means in particular acts [on the left] on the -th value . The group also acts, for any set , on the set of -tuples [on the right]. The symbolic expression , which appears as a term in generating functions as power series, is itself given a functorial meaning, in which we take a quotient which in rough terms makes an identification which allows swapping back and forth between the left action and right action, in a manner reminiscent of taking a tensor product.

Whereas for ordinary generating functions, we don’t have a in the denominator. These tend to be more useful in situations where the sets involved have an implicit ordering attached, which would be broken by the action of symmetric groups: that is, the automorphism group of the

orderedset is the 1-element group, and that’s what we’d divide out by (so, 1 in the denominator, not n!). For example, the classic example of the use of ordinary generating functions is counting the number of binary trees with leaves, where a left-right ordering is explicitly taken into account. Because of this ordering, ordinary generating functions seem to be more appropriate for this problem than exponential generating functions.March 31, 2009 at 3:58 am

Miodrag MilenkovicAnother great book in this vein is the recently published Analytic Combinatorics by Flajolet and Sedgewick, sold in bound form, but amazingly still available as a pdf from http://algo.inria.fr/flajolet/Publications/books.html (the link on the page to the actual pfd – http://algo.inria.fr/flajolet/Publications/book.pdf)

April 2, 2009 at 2:17 am

BrentThis is very, very cool! Thanks for writing this, it’s a very readable and enlightening exposition. I already knew some generating function stuff (from Concrete Mathematics) but never knew the connection to category theory and combinatorial species.

April 2, 2009 at 3:17 am

Vishal LamaTodd,

In your last comment, you mentioned that “

the category FB of finite sets and bijections is (in the technical sense) equivalent to the category which is the disjoint union of finite symmetric groups.” I may be somewhat out of my depth here but I can’t resist asking a couple of questions!1) Do you have in mind an explicit “construction”,

i.e.functors between those two categories and the required natural isomorphisms, to show that the two categories are indeed equivalent?2) Are there other explicit “constructions”? If yes, is there some natural transformation lurking around?!

I especially hope the second question makes some sense!

April 2, 2009 at 1:15 pm

Todd TrimbleNo, it’s a very good question, Vishal. I think you know what “equivalence” of categories means technically (it’s not the same as “isomorphism”), but for the benefit of everyone, let’s remind ourselves: two categories C, D are equivalent if there is a functor F: C –> D and G: D –> C such that the composites FG: D –> D and GF: C –> C are (not necessarily equal to but) naturally isomorphic to identity functors 1_D and 1_C.

Thus, one also says that F: C –> D is an equivalence if there is a functor G: D –> C going back the other way, and isomorphisms FG ~ 1_D, GF ~ 1_C.

In the present situation, we are considering the subcategory P of FB = FinBij whose objects are the finite sets [n] = {1, …, n} (including [0], which is empty), and bijections between them. Of course, there is no bijection from [m] to [n] unless m = n, in which case we have hom([n], [n]) = S_n (permutation group). Thus, if you think of the group S_n as a one-object category (where the object is identified by the label n, and whose morphisms n –> n are the elements of S_n), then P is the same as the disjoint union of these groups-as-categories.

The claim is that the inclusion functor i: P –> FB is an equivalence. There is a famous result that under the axiom of choice, a functor F: C –> D is an equivalence if it is full, faithful, and if every object of D is isomorphic to F(c) for some object c of C. Here, the full faithfulness is just a consequence of how we defined P, and the last condition is clear: every object of FB bijects to some [n].

Let’s run through this result for this example. How do we construct a “quasi-inverse” G: FB –> P to F? Well, there’s no choice about the fact that G has to take a finite set S to [card(S)]. Now we have to define how G acts on morphisms; that is, if card(S) = card(T) = n and f: S –> T is a bijection, we have to define the corresponding bijection G(f): [n] –> [n]. Here, what one has to do is choose, for each S, a bijection h_S: S –> [n] (this is where axiom of choice comes in). Then we can define G(f) to be

(h_T) f (h_S)^{-1}: [n] –> [n].

I leave it to check that this definition is functorial. The requisite natural isomorphisms FG –> 1_{FB} and GF –> 1_P are defined using the choices of bijection h_S; again this is straightforward and left to the reader.

(If one prefers to work in a constructive setting, either for philosophic reasons or for reasons forced by the “internal logic” of some context, this obviously won’t do. Here one has little choice but to rewrite what we mean by “equivalence”, in a way which is constructively more manageable but gives back an equivalent notion in the classical setting. Here it gets a bit technical, but a buzzword, if you want to follow this up in the nLab, is “anafunctor”.)

Curiously, though, one can do a little better by working directly at the level of species. That is, if [C, D] denotes the category of functors from C to D (and natural transformations between them), then I can make an equivalence between [P, Set] and [FB, Set] more explicit. (The second category is the category of species; the first is often called the category of permutation representations.)

In one direction, it’s easy: define a functor i*: [FB, Set] –> [P, Set] by “restriction”, i.e., by taking a species X: FB –> Set to Xi: P –> Set.

In the other direction, one can take a (Kan) extension. It’s a neat trick: given a permutation representation Y: P –> Set, define Kan_i Y: FB –> Set by the formula

where ~ is the smallest equivalence relation in which , for any bijections g: [n] –> S, f: [n] –> [n], and . This construction, where the equivalence relation allows you to “slide” the action of f to the left or right, is an example of what is often called a (generalized) tensor product.

Anyway, the upshot is that i* and Kan_i are quasi-inverse to one another, and it is not hard to describe explicit isomorphisms i*Kan_i ~ 1, Kan_i i* ~ 1, where the 1’s are appropriate identity functors. So I guess this would be an answer to your question 2).

April 2, 2009 at 1:32 pm

Todd TrimbleBrent: great; thanks! There will be a follow-up post soon, but if this has piqued your interest, then you might find the references in this post even more interesting. Suffice it to say that when one starts “thinking species”, an awful lot of enumerative combinatorics stuff becomes plain as day.

April 2, 2009 at 4:44 pm

Todd TrimbleFrom the Secret Blogging Seminar, I just learned of the math blog Annoying Precision, which has some current discussion of egf’s (scroll down a bit), inspired by Zeilberger’s entry in the Princeton Companion to Mathematics. There some good little problems there which one could chew on from the standpoint of species. Here are just two:

(1) Show that the egf of involutions is .

Solution: picture an involution as a disjoint sum of 1-cycles and 2-cycles. The 1-cycles form one subset (with no extra combinatorial information needed: just an exp(X)-structure there), and the 2-cycles form another (where each 2-cycle is just a pair, so this subset has a pairing structure, i.e. an exp(X^2/2)-structure, as discussed in an earlier comment). So the species is just

with egf as shown above.

(2) What is the egf of?

Solution: The Taylor coefficients of , namely , count the number of ways of linearly ordering an -element set with (call such a linear order a

chain). So the egf above counts the ways of breaking a set up into a disjoint sum of chains. You could also describe it as counting the number of endofunctions such thatimplies or ; I don’t know of much nicer ways of putting it.

April 2, 2009 at 5:09 pm

Vishal LamaTodd,

Thanks a ton for all those comments! I will come back to them, some time soon. Just so you know, I had linked (a long time ago) to “Annoying Precision” from our blog using the name “t0rajir0u (AoPS)”! You need not have gone to Secret Blogging Seminar to find out about it! Of course, the fault is entirely mine. I should have chosen the name “Annoying Precision” instead of “t0rajir0u (AoPS)”. :-)

April 3, 2009 at 12:22 am

John ArmstrongI’ve only gotten around to reading through your section recently, Todd. I figure I may as well shamelessly self-promote an old post of mine about composing power series. Looking forward to more.

April 17, 2009 at 4:23 pm

Idempotent endofunctions « The Math Less Traveled[…] the comments, but I won’t be posting a solution later; for that I’ll just direct you to Vishal’s post where I got this problem. He goes on to discuss the relation to exponential generating functions […]

April 30, 2009 at 10:37 pm

Qiaochu YuanTodd: thanks for the plug! I wrote that entry before reading “Combinatorial Species,” which contains my favorite example of composing species: the species of all endofunctions (rather than just the idempotent ones) is the composite of the species of cycles and the species of directed trees. To see this, consider the “orbit” of a single element under an endofunction. Such an orbit must be eventually periodic, so write down the periodic elements first. Then all the other elements arrange themselves into directed trees mapping to an element of some periodic orbit, one for each element of each orbit. “Combinatorial Species” also contains a rather beautiful proof of Cayley’s formula along the same lines.

As far as the n! denominators in egfs, I really like Baez and Dolan’s explanation, but Rota’s “Finite Operator Calculus” contains an alternate explanation for the denominators of several classical forms of generating functions – Eulerian, Dirichlet – in terms of certain generalizations of binomial coefficients arising from the structure of certain locally finite posets. For example, the exponential generating function arises from the structure of the lattice of finite sets under inclusion, and the Dirichlet generating function arises from the structure of the lattice of cyclic groups under subgroup (if I recall correctly). I’m wondering to what extent the two explanations enrich each other. For example, can we think of the n^s denominator in a Dirichlet generating function as representing the group (Z/nZ)^s?

Vishal: thanks for the link! If you plan on updating the name, I’ve also moved to WordPress: you can now find me at http://qchu.wordpress.com.

June 4, 2009 at 11:46 am

Américo TavaresVishal,

This is basically an off-topic question.

I have checked (by hand and using the telescoping sum , where ) that is a solution of

Do you know whether is it possible to use a generator function in order to have an idea why this happens?

June 6, 2009 at 3:19 pm

Vishal LamaAmérico,

Sorry for this delayed response! At the grave risk of giving a curt reply, have you tried using ordinary generating functions (Herbert Wilf’s generatingfunctionology being an excellent resource) to solve that problem? From what I can see, the recurrence relation you gave should yield a first order ordinary differential equation, whose solution should be amenable to the standard methods used for solving such equations. [

Last line slightly edited.]June 6, 2009 at 3:40 pm

Américo TavaresVishal,

Thanks for your reply.

Actually I have not yet read Herbert Wilf’s generatingfunctionology.

I will start by reading it.

Américo

June 7, 2009 at 9:14 pm

hbm“Now, the solution is right before our eyes! Suppose has fixed points. Then there are ways of choosing them. And, each of the remaining elements of that are not fixed points are to be mapped to any one of the fixed points. And, there are a total of ways of doing that. So, summing over all , our final answer is .” [

Edited LaTeX code.]I am not sure, but I think you should count the number of onto functions from the remaining elements to the fixed points not just functions.

June 7, 2009 at 9:52 pm

Vishal Lamahbm,

It seems you are using the definition of an

ontofunction somewhat loosely, but I think I know what you are trying to say. Allow me to offer an example to see if I understand what you just wrote.Let . Suppose we have exactly two fixed points such that and . Then, according to you, the element should be mapped to both the fixed points, and . Is that right? More importantly, is that possible?

Am I missing something here?

June 20, 2009 at 7:43 am

GILA IV: The unreasonable effectiveness of generating functions in the combinatorial sciences « Annoying Precision[…] it is by no means comprehensive, this post over at Topological Musings is a good introduction to the basic ideas of species […]

June 24, 2009 at 9:59 am

GILA VI: The cycle index polynomials of the symmetric groups « Annoying Precision[…] The key is to identify a permutation with its functional graph; see the Topological Musings post I linked to for another discussion of this technique. This is a graph whose vertex set is the […]

June 30, 2009 at 5:52 am

Category theory and combinatorics « Portrait of the Mathematician[…] you probably have enough information on the theory to get through Todd and Vishal’s post dealing with species, in which the connection with generating functions is explained more clearly […]

July 24, 2009 at 10:22 pm

Introducing Math.Combinatorics.Species! « blog :: Brent -> [String][…] to read more about combinatorial species, I recommend reading the Wikipedia article, which is OK, this fantastic blog post, which is what introduced me to the wonderful world of species, or for a great dead-tree reference […]