A Combinatorial Derivation of the

Number of Labeled Forests

David Callan Department of Statistics University of Wisconsin-Madison 1210 W. Dayton St. Madison, WI 53706-1693

                     callan@stat.wisc.edu

Abstract

Lajos Takács gave a somewhat formidable alternating sum expression for the number of forests of unrooted trees on n labeled vertices. Here we use a weight-reversing involution on suitable tree configurations to give a combinatorial derivation of Takács’ result.

Takács [1] used Lagrange inversion to obtain the alternating sum expression

\frac{n!}{n + 1} ∑_{j=0}^{⌊n/2⌋}(−1)^{j} \frac{(2j + 1)(n + 1)^{n−2j}}{2^{j}j!(n − 2j)!}  (1)

for the number of forests of unrooted trees on [n] = {1, 2, …, n} A001858. This contrasts with Cayley’s simple expression (n + 1)^{n−1} A000272 for the number of forests of rooted trees on [n]. Here we use well-known counts for forests of rooted trees to give a combinatorial derivation of Takács’s result: we present (1) as the total weight of certain weighted tree configurations in which forests of unrooted trees show up with weight +1 and we exhibit a weight-reversing involution that cancels out the weights of all other configurations. First, rewrite (1) as

∑_{0≤j≤n/2} (−1)^{j} \underbrace{\binom{n}{2j}(2j − 1)!!}_{A}  \underbrace{(2j + 1)(n + 1)^{(n+1)−(2j+1)−1}}_{B}  (2)

where (2j − 1)!! = 1 · 3 · 5 … (2j − 1) is the double factorial. The factor B is the number of forests on [0, n] consisting of 2j + 1 trees rooted at a specified set of 2j + 1 roots [2, Theorem 3.3, p. 17] (see also [3, §2.1] for a recent elegant proof). The factor A is the number of ways to select 2j elements from [n] and then divide them up into pairs; in other words, to form a perfect matching on some 2j elements of [n]. These 2j elements, together with 0, serve nicely as the specified roots to construct configurations counted by the product AB.

Define a partially-paired rooted (PPR, for short) n-forest to be a tree rooted at 0 and zero or more (unordered) pairs of rooted trees, the vertex sets of all the trees forming a partition of [0, n]. The pair-count of a PPR forest is its number of pairs of trees. The product AB is then the number of PPR n-forests with pair-count j. If we define the weight of a PPR forest of pair-count j to be (−1)^{j}, then the right hand side of (1) is the total weight of all PPR n-forests.

To include the objects we’re trying to count among these PPR n-forests, we suppose each tree in an unrooted forest to be rooted at its smallest vertex. Then forests of unrooted trees on [n] correspond precisely to PPR n-forests with pair-count 0 and each child of vertex 0 smaller than all its descendants (delete vertex 0 to get the forest of unrooted trees). A vertex v in a rooted tree is inversion-initiating if at least one descendant of v is < v, otherwise it is regular. Thus forests of unrooted trees on [n] appear as PPR n-forests with pair-count 0 and all children of vertex 0 regular. These special PPR forests are counted with weight 1 and here is the promised weight-reversing involution on the rest.

Given a PPR forest, let a denote the smallest vertex among all trees (if any) other than the one rooted at 0, let u be the root of a’s tree (u is possibly, but not necessarily, = a), and let v be the root of the other tree in its pair. At the same time, if 0 has any inversioninitiating children, let a′ be the smallest among all descendants of these inversion-initiating vertices, let v′ be the child of 0 of which a′ is a descendant, and let u′ (possibly = a′) be the child of v′ on the path from v′ to a′. See the illustration below where solid lines represent mandatory edges, vertical dotted lines optional edges, and diagonal dotted lines optional subtrees.

. . . . . .. . . . ._{. . . . .}_{. . . . .}_{. . . . .}_{. . . . .} . . . . .  . . . . .. . . . .. . . . ._{. . . . .}_{. . . . .}  . . . . . ^{pair of trees} 0  u  v v′ u′ a′  a • • • • •  • • •  • a′ is smallest descendant of an inversion-initiating child of 0  a is smallest vertex not a descendant of 0

At least one of a, a′ will exist unless the pair-count is 0 and all children of vertex 0 are regular; these are the special PPR forests, representing unrooted forests, and they survive. Choose the smaller of a, a′. If it’s a, add an edge from 0 to v and an edge from v to u so that vertex 0 acquires a new inversion-initiating child v (with a small descendant a) and the number of pairs of trees is reduced by 1. If it’s a′, delete the edges 0v′ and v′u′ to form a new pair of trees rooted at u′ and v′ (with a′ now the smallest vertex among all pairs of trees). In either case, the number of pairs of trees changes by 1, so the weight changes sign. The mapping is clearly an involution on all non-special PPR forests and so their weights cancel out. Thus (2) (= (1)) is the number of forests of unrooted trees on [n].

References

[1] L. Takács, On the number of distinct forests, SIAM J. Discrete Math. 3 (1990), 574–581.

[2] J. W. Moon, Counting Labelled Trees, Lectures Delivered to the Twelfth Biennial Seminar of the Canadian Mathematical Congress (Vancouver, 1969), Canadian Mathematical Monographs, No. 1, 1970.

[3] J. Pitman, Coalescent random forests, J. Combin. Theory Ser. A 85 (1999), 165–193.

2000 Mathematics Subject Classification: 05C05. Keywords: tree, labeled forest, partially-paired rooted n-forest, inversion-initiating vertex, weight-reversing involution.

(Concerned with sequence \underline{A001858}.)

Received October 3 2003; revised version received November 3 2003. Published in Journal of Integer Sequences January 15 2004.

Return to Journal of Integer Sequences home page.