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 A = \{ 1,2, \ldots , n \}, where n is a positive natural number. Find the number of endofunctions f: A \rightarrow A satisfying the idempotent property, i.e. f \circ f = f.

It turns out that finding a solution to the above problem is equivalent to counting the number of forests with n nodes and height at most 1, 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: f has at least one fixed point.

Proof: Pick any i \in A and let f(i) = j, where j \in A. Then, using the idempotent property, we have f(f(i)) = f(i), which implies f(j) = j. Therefore, j is a fixed point, and this proves our lemma.

Lemma 2: The elements in A that are not fixed points are mapped to fixed points of f.

Proof: Supposej \in A is not a fixed point such that f(j) = k.  Then, using the idempotent property again, we immediately have f(f(j)) = f(j), which implies f(k) = k, thereby establishing the fact that k itself is a fixed point. Hence, j (which is not a fixed point) is mapped to some fixed point of f.

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

Now, the solution is right before our eyes! Suppose f has m fixed points. Then there are \displaystyle \binom{n}{m} ways of choosing them. And, each of the remaining n - m elements of A that are not fixed points are to be mapped to any one of the m fixed points. And, there are a total of m^{n-m} ways of doing that. So, summing over all m, our final answer is \displaystyle \sum_{m=0}^{n} \binom{n}{m} m^{n-m}.

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 a_n of combinatorial structures of some type on an n-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 a_n by rolling them into a single analytic function, such as

\displaystyle A(x) = \sum_{n \geq 0} \frac{a_n x^n}{n!},

(this the so-called “exponential” generating function of \{a_n\}_{n \geq 0}). In many cases of interest, the function A(x) 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 a_n, 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 A(x) and B(x) are generating functions for counting combinatorial structures of type (or species) A and B, then what types of structures would the function A(x) + B(x) “count”?  How about A(x)B(x)? Composition A(B(x))?

The case of A(x) + B(x) is easy: writing

\displaystyle A(x) + B(x) = \sum_{n \geq 0} \frac{a_n x^n}{n!} + \sum_{n \geq 0} \frac{b_n x^n}{n!} = \sum_{n \geq 0} \frac{(a_n + b_n) x^n}{n!},

and thinking of a_n as counting structures of type A on an n-element set, and b_n as counting structures of type B, the quantity a_n + b_n counts elements in the disjoint union of the sets of A-structures and B-structures.

In the categorical approach we will discuss later, we actually think of structure types (or species of structure) A as functors, which take an n-element set S to the set A\left[S\right] of structures of type A on S. 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 f: S \to T from one n-element set to another, then it should always be possible to “transport” A-structures on S to A-structures on T, simply by relabeling points along the bijection f. So, let us define a species to be a functor

A: FB \to Set

where FB is the category of finite sets and bijections (not all functions, just bijections!), and Set is the category of sets. In enumerative combinatorics, the set A\left[S\right] 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 A to map into other categories C, not just Set (“C-valued species”). But if we stick for now just to set-valued species A, B, then we define the species A + B by the functorial formula

\displaystyle (A + B)\left[S\right] = A\left[S\right] \sqcup B\left[S\right]

where \sqcup 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:

\displaystyle A(x) B(x) = (\sum_{j \geq 0} \frac{a_j x^j}{j!})(\sum_{k \geq 0} \frac{b_k x^k}{k!}) = \sum_{n \geq 0} (\sum_{j + k = n} \frac{n!}{j! k!} a_j b_k) \frac{x^n}{n!}

The question is: what type of structure does the expression \displaystyle \sum_{j+k = n} \frac{n!}{j! k!} a_j b_k “count”? Look at the individual terms: the binomial coefficient \displaystyle \frac{n!}{j! k!} describes the number of ways of decomposing an n-element set into two disjoint subsets, one with j elements and the other with k, where j and k add to n. Then, a_j is the number of ways of putting an A-structure on the j-element part, and b_k is the number of B-structures on the k-element part.

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

\displaystyle (A \otimes B)\left[S\right] = \bigsqcup_{T \sqcup U = S} A\left[T\right] \times B\left[U\right]

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

Finally, let’s look at composition A(B(x)). Here we make the technical assumption that b_0 = 0 (no B-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 A, B: FB \to Fin be species (functors from finite sets and bijections to finite sets), and assume B\left[\emptyset\right] = \emptyset. The substitution product A \circ B is defined by the formula

\displaystyle (A \circ B)\left[S\right] = \sum_{E \in Eq(S)} A\left[S/E\right] \times \prod_{c \in S/E} B\left[c\right]

This clearly requires some explanation. The sum here denotes disjoint union, and Eq(S) denotes the set of equivalence relations on the finite set S. So E here is an equivalence relation, which partitions S into nonempty sets c (E-equivalence classes). And the quotient S/E denotes the set of such equivalence classes (so we think of each class c as a point of S/E). What this formula says is that a structure of type A \circ B on S consists of a partition of S into a bunch of non-empty blobs, a B-structure on each blob, and then an A-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:

\displaystyle E(x) = \exp(x) = \sum_{n \geq 0} \frac{x^n}{n!}

F(x) = x

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

For F, we have f_n = 0 unless n = 1, where f_1 = 1. So F is the species for the one-element set structure (meaning that F\left[S\right] = \emptyset unless S has cardinality 1, in which case F\left[S\right] = \{S\}).

Okay, on to Vishal’s example. He was counting the number of idempotent functions f: S \to S, 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 f: S \to S, first as Vishal did, by thinking of the elements of S as ‘nodes’, and then drawing a directed edge from node x to node y if f(x) = y. (Then, by idempotence of f, y will be a fixed point of f. Let’s agree not to bother drawing an edge from y to itself, if y 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 f, 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 S: a partition of S 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 F \otimes E structure; we’ll suggestively write this structure type as X \otimes \exp(X).

In this picture of idempotent f, 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 “E-structure”, nothing more.

So, putting all this together, we picture an idempotent function on S as a partition or equivalence relation on S, 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

E \circ (F \otimes E)

or more suggestively, \exp \circ (X \otimes \exp(X)). The exponential generating function is, of course, e^{x e^x}!

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 \{a_n\}, 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!