number of weighted trivalent trees

Question

Given a trivalent tree (graph without loops with valence of 3+ at each vertex) on N marked points, let's assign to each vertex the number (its valence - 3)! (note the ! at the end). Take the product of these numbers over all vertices in the graph. Sum the resulting products over all trivalent graphs on N marked points. The answer seems to be $(N-2)^{N-2}$. I would guess this is well-known. Is there something I can reference? Thanks.

Answer 1

This is just building off the previous discussion -- I will just give some indication of why Dan's $f$ and $g$ are Legendre transforms of each other. This is essentially a fleshed out version of some of what Frédéric was saying that I wanted to work out in detail -- it would look too small and ugly as a comment.

We're going to use some basic facts about the Lambert W-function.Lambert W-function and the Legendre transformation, but nothing past what you can find in those Wikipedia links.

First, showing that $f$ and $g$ are Legendre transforms of each other is essentially showing that their derivatives are compositional inverses of each other. So we will show this for $f^\prime$ and $g^\prime$, and not use anything else about the Legendre transformation.

The Lambert $W$ function $W(x)$ is defined by the functional equation $x=W e^W$. You recognize it's coming into play when you start seeing $n^n$ terms, as they show up in the taylor expansion of it and simple expressions related to it. In particular, wikipedia tells us that:

$$\left(\frac{W}{x}\right)^r = e^{-rW}=\sum_{n\geq 0} r(n+r)^{(n-1)} \frac{(-x)^n}{n!}$$

The first equation is the functional equation, and in general to get the taylor expression you want to use Lagrange inversion and the functional equation.

In any case, if we set $r=-1$, take $0^0=1$ and hopefully not make any sign errors, we should obtain

$$g^\prime(x)=1-e^{W(-x)}.$$ Simple calculus gives $$f^\prime=-(1-x)\ln(1-x).$$ From these expressions it is immediate that $f^\prime(g^\prime(x))=x$ by using the functional equation for $W$.

Answer 2

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".