Skip to main content
2 of 2
added 661 characters in body; added 1 characters in body
Dan Petersen
  • 40.3k
  • 2
  • 114
  • 201

I think Alex is using some terminology from moduli spaces without mentioning it and that the question should be interpreted as follows. We are interested in counting trees such that each internal vertex has degree at least three. A "marked point" on the graph means an extremal vertex. The marked points should be labeled, but the internal vertices are not. Finally we assign a weight to each internal vertex by $(\mathrm{valence} - 3)!$ and take the product of all weights. For example when $N=5$:

  • There is one unlabeled graph with a single internal vertex (a star), which admits a unique labeling. This is counted with multiplicity $(5-2)! = 2$.

  • There is one unlabeled graph with two internal vertices, which admits $\binom{5}{3} = 10$ distinct labelings. Here all vertices have valence at most four so all weights are 1.

  • There is one unlabeled graph with three internal vertices, which admits 15 distinct labelings up to isomorphism. All weights are one again.

So we get the sum 27. I would be interested to know some context for this question.


Here is an equivalent reformulation of the problem. Define the two power series $$f = \frac{x^2} 2 - \sum_{n\geq 3} (n-3)!\frac{x^n}{n!}$$ and $$g = \frac{x^2}2+\sum_{n \geq 3}(n-2)^{n-2}\frac{x^n}{n!}.$$ Your assertion is equivalent to that $f$ and $g$ are Legendre transforms of each other. I looked at this a bit but couldn't show it, perhaps because I do not even see a way of finding a closed formula for $g$. The connection between Legendre transforms and enumeration of trees is explained in E. Getzler, "Operads and moduli spaces of genus zero Riemann surfaces" section 5, as well as in the introduction of E. Getzler, "The semiclassical approximation for modular operads".

Dan Petersen
  • 40.3k
  • 2
  • 114
  • 201