Counting Trees

Let be the Combinatorial Structure of Trees. Let be the Exponential Generating Function for rooted trees. Let be the Exponential Generating Function for doubly rooted trees. Let be the Combinatorial Structure of maps:

Lemma

Proof

Note that

as we can pick one vertex to be the root; then build rooted trees on other vertices; and finally connect to the roots of the trees in . As we conclude

Lemma

Proof

For any , build the Combinatorial Product

and then connect their roots in order. We now view just the endpoints as being the roots. Also, in any doubly rooted tree, the distance between the two roots is some (edges). Thus we conclude

Let be a map. It will have periodic points (such that ) and wandering points (not periodic). We can thus build rooted trees from with edges defined by:

where each tree is rooted at the periodic point. We order these trees by how permutes the periodic points. We conclude that maps with periodic points are in bijection with

Also it is easy to see that every map has at least one periodic point. We conclude

Theorem

There are trees on .

Proof

Note that

Thus the number of doubly rooted trees on is (by the lemma) However, double rooting is just times the number of trees, so the number of trees on has to be