The solutions are in! I thought last week’s problem might have been a little more challenging than problems of previous weeks — the identity is just gorgeous, but not at all obvious (I don’t think!) without some correspondingly gorgeous combinatorial insight. Luckily, some of our readers came up with the goods, and their solutions provide a forum for discussing a beautiful circle of ideas, involving the inter-related combinatorics of trees and endofunctions.

I can’t decide which of the solutions we received I like best. They all bear a certain familial resemblance, but each has its own distinct personality. I’ll give two representative examples, and append some comments at the end. Both proofs are conceptual “bijective” proofs, in which the two sides of the identity represent two different ways of counting essentially the same combinatorial objects. And both rely on a famous theorem of Cayley, on the number of tree structures or spanning trees on n distinct labeled nodes (maybe this would be sufficient hint, if you still want to think about it some more by yourself!). Here, I’ll add a little spoiler space:

 

 

 

 

 

1. (Solution by David Eppstein) As is well known (see, e.g., http://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence), the number of different spanning trees on a set of n labeled nodes is n^{n-2}. Equivalently, the number of ways of choosing a spanning tree together with a specification of a single vertex s is n^{n-1}, and the number of ways of choosing a spanning tree together with a specification of two vertices s and t (possibly equal to each other) is n^n. So that’s the right hand side of the identity.

Now suppose you are given a tree T, and two nodes s and t. If s and t are different, let (s,u) be the first edge on the path in T from s to t; cutting T at that edge produces two disjoint subtrees, one containing one marked node s and the other containing two (possibly equal) marked nodes, namely t and the first node u on the path after s. Conversely, from this information (two trees, one containing a marked node s and the other containing two marks on nodes u and t) we can put together T simply by connecting the two trees by an edge (s,u). If j is the number of nodes in the tree containing s, the number of ways we can choose two disjoint marked subtrees in this way is

\displaystyle \sum_{j=1}^{n-1} {n\choose j} j^{j-1} (n-j)^{n-j},

almost the same as the left hand side of the identity, but missing the final term in the sum.

The final term comes from the case when the marked nodes s and t of tree T coincide. The number of ways this can happen is the same as the number of ways we can pick a single marked node of a tree, that is, n^{n-1}, which is the same as the final term in the left hand sum.

Thus, the left side counts (partitions of n vertices into two disjoint subtrees, one subtree having one marked node and one subtree having two possibly-equal marks) + (n-vertex trees with one marked node); the right side counts (n-vertex trees with two possibly-equal marks), and we have demonstrated a combinatorial equivalence between these two sets. \Box

2. (Solution by Sune Jakobsen) Consider all (n-1)-tuples a=(a_1,a_2,...,a_{n-1}), where each term is from the set \{1,2, \ldots, n\}. Since each of the n-1 terms can take n values, there are n^{n-1} such tuples.

Given a (n-1)-tuple, a, construct a graph as follows. Begin with a vertex labeled n. Then, for each vertex labeled k in the graph, if a_i=k, add a new vertex labeled i, and connect i and k by an edge. This graph must be a tree since each a_i only takes one value and a_n doesn’t exist.

Using this graph, I will count the number of (n-1)-tuples in another way. Let j be the number of vertices in such a tree graph. The vertices may be chosen in \displaystyle \binom{n-1}{j-1} ways, since the vertex labeled n is already one of them. Given the vertices, the tree can be formed in j^{j-2} ways, by Cayley’s theorem (see http://www.research.att.com/~njas/sequences/A000272). Given the tree graph, the values of the a_i‘s, for each vertex labeled i in the graph, can be chosen in one and only one way (namely, a_i is the label of the first vertex after i along the unique path from vertex i to vertex n). The remaining n-j components of the tuple are not among the vertex labels in the graph, so each takes on one of n-j possible values, giving (n-j)^{n-j} possibilities for the remaining components. Therefore the number of (n-1)-tuples must be:

\displaystyle n^{n-1} = \sum_{j=1}^{n} \binom{n-1}{j-1} j^{j-2} (n-j)^{n-j}

Multiplying both sides of the previous equation by n and using \displaystyle \frac{n}{j}\binom{n-1}{j-1} = \binom{n}{j}, the claim follows. \Box

 

Remarks:

1. I found this curious identity in HAKMEM, item 118. For those who don’t know, HAKMEM is a kind of archive of cool mathematical observations made by some of the original MIT computer “hackers” from the 60′s and 70′s, including Bill Gosper and Rick Schroeppel. This particular item is credited to Schroeppel, but the accompanying text is a bit cryptic in my view:

Differentiate ye^{-y} = x to get y + y x y' - x y' = 0. One observes the curious identity
\displaystyle \sum_{j=1}^n \binom{n}{j} j^{j-1} (n-j)^{(n-j)} = n^n (0^0 = 1)
and thus
\displaystyle y(x) = \sum_{n \geq 1} \frac{n^{n-1} x^n}{n!}.

Maybe it was just their style to record a lot of their observations in such terse, compact form, but it annoys me that these guys hide their light under a bushel in this way. No motivation whatsoever, even though (I’d be willing to bet) these guys knew about the connection to trees — they’re computer scientists, after all!

Personally, I find it easier to get from y = x e^y to \displaystyle y = \sum_{n=1}^\infty \frac{n^{n-1}x^n}{n!} by other means than through their intermediate identity. I feel sure that just about anyone who has played around with enumerative combinatorics, and with the combinatorics of trees in particular, could figure this one out.

For, as David pointed out in his solution, n^{n-1} is the number of spanning trees on the set [n] = \{1, 2, \ldots, n\} equipped with a distinguished vertex; I’ll call that vertex the root, and such structures rooted trees. (Incidentally, a spanning tree is by definition an acyclic subgraph of the complete graph on the set [n], such that any two elements of the set are connected or spanned by a path in the subgraph. The theorem of Cayley mentioned above is that there are n^{n-2} such spanning trees.) Thus,

\displaystyle y(x) = \sum_{n=1}^\infty \frac{n^{n-1} x^n}{n!}
is the exponential generating function (egf) for rooted trees.

 

On the other hand, it is not hard to see that the functional equation y = xe^y holds for the egf of rooted trees (and uniquely determines the power series of the egf). One just applies some basic principles; I’ll just say it briefly and hope it’s somewhat followable: a rooted tree structure on a finite set S is given by the selection of a root r \in S, together with a partition of the remainder S - \{r\} into equivalence classes and a choice of rooted tree structure on each class. (Severing the root results in a bunch of disjoint subtrees, whose roots are those vertices adjacent to the original root.) At the level of egf’s, selection of the root accounts for the factor x on the right of the functional equation, and if y is the egf for rooted trees, then the other factor e^y is the egf for the collection of ways of partitioning a set into nonempty classes and putting a rooted tree structure on each class. This is all part of the art and science of generatingfunctionology. It’s beautiful stuff.

 
Somehow I find this explanation much easier to understand than the machinations hinted at in HAKMEM 118.

2. David’s proof was actually the one I myself had in mind. I can’t say what inspired David, but I myself was inspired by an earlier reading of a beautiful (and in many respects revolutionary-for-its-time) article, on a systematic functorial approach to enumerative combinatorics:

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

In particular, I am very fond of the proof Joyal gives for Cayley’s theorem (which he credits to Gilbert Labelle), and this proof is in a line of thought which also leads to David’s solution. I’d like to present that proof now.

Labelle’s proof of Cayley’s theorem:

The expression n^n probably makes most people think of the number of functions f: [n] \to [n] from an n-element set to itself. The art of combinatorics lies in drawing appropriate pictures, so draw a picture (a graph) of such a function by drawing a directed edge from i to j = f(i) whenever i \neq j (cf. Sune’s solution). Starting from any vertex and iterating f enough times, you always eventually land in a cycle where points get revisited periodically, infinitely often. Let’s call those points periodic points; the function f acts as a permutation on periodic points. Now, for each periodic point p, consider the union of directed paths which end at p without hitting any other periodic points. This union forms a subgraph T_p which is a tree, rooted at p (again, cf. Sune’s solution). The entire set [n] is thereby partitioned into (equivalence) classes (the underlying vertex sets of the trees T_p), and the structure of a function f: [n] \to [n] thus determines the following data:

  • An equivalence relation on [n];
  • A rooted tree structure on each equivalence class;
  • A permutation structure on the set of equivalence classes (each tagged by the periodic point at the root).

Conversely, these three data determine a function, and the correspondence is bijective.

  • Remark: It’s not necessary to the proof, but let me add that by basic principles of generatingfunctionology, if p(x) is the egf for permutations [namely, \displaystyle p(x) = \frac1{1-x}], and if y(x) is the egf for rooted trees, then (p \circ y)(x) is the egf for structures given by such triplets of data. Thus, by the bijective correspondence, we have

    \displaystyle \sum_{n=0}^\infty \frac{n^n x^n}{n!} = (p \circ y)(x).

On the other hand, consider a tree structure T on n points, and suppose we also specify an ordered pair of such points (s, t), possibly equal. There is a unique path from s to t in T, which I’ll call the spine (of the “bipointed tree”); call the points along that path, including s and t, vertebrae. Now, for each point x \in T, there is a unique shortest path from x to the spine, terminating at a vertebra p. The union of all such paths which terminate at a vertebra p again forms a subtree T_p rooted at p. Again, the set of n points is partitioned by the (underlying vertex sets of) T_p , and the structure of a bipointed tree on an n-element set [n] is thus encoded [in bijective fashion] by

  • An equivalence relation on [n];
  • A rooted tree structure on each equivalence class;
  • A spine structure (that is, a linear ordering) on the roots which tag the equivalence classes.

However, the number of linear orderings on an n-element set, n!, is the same as the number of permutations on that set. We conclude that the number of bipointed tree structures on an n-element set is the same as the number of endofunctions, n^n. And, voilà! the number of tree structures on the n-element set must therefore be n^{n-2}. \Box

Note: regular solver Philipp Lampe, who submitted a solution similar to David’s, pointed out that there are no fewer than four proofs of Cayley’s theorem given in Aigner and Ziegler’s Proofs from The Book, which I referred to in an earlier post. At this point, I really wish I had that book! I’d be delighted if someone were to post one of those nice proofs in comments…

3. I’m not quite sure, but Sune’s solution just might be my current favorite, just because it makes obvious contact with the circle of ideas which embrace endofunctions, trees, and rooted trees (I think of the tuples there as endofunctions, or actually, partial endofunctions on (n-1)-element sets). In any event, my sincere thanks go to David, Philipp, and Sune for their insightful responses.

About these ads