You are currently browsing the monthly archive for March 2009.

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!

I thought I would share with our chess-loving readers the following interesting (and somewhat well-known) mathematical chess paradox , apparently proving that 64=65, and the accompanying explanation offered by Prof. Christian Hesse, University of Stuttgart (Germany).  It shows a curious connection between the well-known Cassini’s identity (related to Fibonacci numbers) and the 8 \times 8 chessboard (8 being a Fibonacci number!). The connection can be exploited further to come up with similar paradoxes wherein any F_n \times F_n -square can always be “rerranged” to form a F_{n-1} \times F_{n+1} -rectangle such that the difference between their areas is either +1 or -1. Of course, for the curious reader there are plenty of such dissection problems listed in Prof David Eppstein’s Dissection page.

This being a mathematics blog, I’m sure a lot of readers out like to play Minesweeper. I’ve just obtained a personal best today (94 seconds on expert level) which, as Minesweeper buffs know, is nowhere close to world-class levels, but which made me happy anyway, as I’d never broken into the double digits before today!

It seems to me that world-class competitors must know some tricks with the mouse which I’ve never bothered to master, particularly because my laptop doesn’t have a mouse but rather a touchpad. This being the case, I keep my right index finger on the touchpad to guide the cursor, and the left index finger to click. I always left-click: that is, in my style of play, I [practically] never flag squares for bombs; I click only on non-bomb squares. For it’s well-known, or at least it should be, that the program doesn’t care if you identify where the bombs are — you get full credit for only identifying all the numbered squares.

To play in this style well, one needs to be fluent in a number of tactical tricks, which I don’t have good names for, but which in my personal argot I call things like “1-2-1”, “1-2-2-1”, “rule of three”, to name just a few. But that’s not what I set out to discuss, really. What I’d really like to hear from good players is: what opening strategies do you use?

The personal best I just set came after deciding on a new opening strategy. What I had been doing is clicking along border squares. Under that strategy, one could of course just keep clicking until one opens up an area, but often I would add to that the observation that if one clicked on a 1, thus leading to, e.g.,

x 1 x (–> border row)
x x x

then one could then click on the non-border square just adjacent to the 1, with only a 1 in 5 chance of setting off a bomb. If one then hits another 1:

x 1 x
x 1 x
x x x

then one can immediately open up the line of squares on the third rank, leading to a configuration such as

x 1 x
x 1 x
1 1 1

or better. This is often a cheap and quick way of opening up squares or otherwise getting a tactical toehold.

The new strategy I began using today is not to click along the border, but to click along the ranks or files adjacent to the border. Under this strategy, if one lands on a 1, leading to

x x x  (–> border row)
x 1 x
x x x

then one can click on the border square adjacent to the 1, with only a 1 in 8 chance of setting off a bomb. If one does not set off a bomb, that square has to be a 1:

x 1 x
x 1 x
x x x

and then one can proceed as before. So I’ve just lowered my odds of hitting a bomb, plus a very small fractional gain in processing time that comes with the certain knowledge that it’s a 1 if not a bomb. So far the strategy has paid off well!

I’d like to hear other people’s opening strategies, and also I’d like to know some statistics. For example, considered over the space of expert-level games, what is the probability of getting a 1, a 2, and so on? Does anyone know? (It seems this would be very difficult computing analytically — one is probably better off using a Monte Carlo simulation. But I don’t have the wherewithal to set that kind of thing up.)

Our other blog

Visitors to this blog

Blog Stats

  • 355,659 hits

Wikio Ranking

Wikio - Top Blogs - Sciences

Current Online Readers

Recent Comments

John Favors on Solution to POW-13: Highly…
Wayne J. Mann on Solution to POW-12: A graph co…
erneststephen on The 54th Carnival of Math…
anhtraisg on p^q + q^p is prime
prof dr drd horia or… on My first post
prof drd horia orasa… on My first post
prof dr mircea orasa… on Inequality with log
notedscholar on Self-referential Paradoxes, In…
prof dr mircea orasa… on Inequality with log
prof dr mircea orasa… on Inequality with log
prof dr mircea orasa… on 2010 in review
kenji on Basic category theory, I
prof dr mircea orasa… on Solution to POW-10: Another ha…
prof drd horia orasa… on Continued fraction for e
prof drd horia orasa… on Inequality with log

Archives

March 2009
M T W T F S S
 1
2345678
9101112131415
16171819202122
23242526272829
3031