MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Could you clarify? I cannot see how to interpret your question to get 27 such trees with five marked points. – Richard Stanley Jun 5 '11 at 3:15
I initially interpreted a labeling as placing a 6 next to each vertex; now I see it as placing 0!=1 to vertices of degree 3, 1 to degree 4 vertices, 2 to degree 5 vertices, and so on. I think there is a condition that is left out, perhaps determining how leaves are placed, that might relate this to number of spanning trees. Gerhard "Ask Me About System Design" Paseman, 2011.06.04 – Gerhard Paseman Jun 5 '11 at 3:57
up vote 3 down vote accepted

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

share|cite|improve this answer
Thank you very much, everyone. Paul's answer in particular completely resolves my question. Here is a direct reformulation of his argument. Let $a_n$ be the weighted number of graphs with $n+1$ marked points divided by $n!$ and $f(x)=x+\sum_{n\ge2}a_n x^n$. From the natural recursion for $a_n$, $$f(x)=x+f(x)+(f(x)-1)\sum_{k=1}^{\infty}\frac{f(x)^k}{k} \quad\longrightarrow\quad (1-f(x))\ln(1-f(x))=-x.$$ Thus, $f(x)=1-e^{W(-x)}$. Using the $r=-1$ case of the above formula then gives $a_n=(n-1)^{(n-1)}/n!$. – Aleksey Jun 7 '11 at 20:41

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

share|cite|improve this answer
I do not know of representations of the symmetric group $S_n$ of dimension $(n-3)!$ or $(n-2)^(n-2)$ (I know only of representations of the symmetric group $S_n$ of dimension $(n-2)!$ or $(n-1)^(n-1)$). This would be needed to interpret this identity using the Koszul duality of cyclic operads. If you just want to prove it analytically, you should write these functions using $\log$ and the Lambert $W$-function. – F. C. Jun 5 '11 at 17:39
This is indeed related to moduli spaces (of stable maps). The structure coefficients in formulas for genus 0 Gromov-Witten invariants are sums over $N$ marked trivalent trees. These can be bounded by the number of weighted trees in my question. I can show this number is bounded above by $C^N\cdot N!$, which is good enough for me. However, instead of adding another half a page proving this, I thought I might be able to quote something from the literature (and then apply Stirling's formula to get $C^N\cdot N!$). Since valence - 3 is so natural for trivalent, I thought this formula were known... – Aleksey Jun 5 '11 at 19:49
This Legendre transform, or rather the inversion formula obtained by derivating both sides, is related to the results and conjectures of Indeed, the PreLie operad (dimension $n^{n-1}$ in degree $n$) contains a subspace of dimension $(n-2)!$ (related to the cyclic Lie operad), which conjecturally generates a free sub-operad (of dimension $(n-1)^{n-1}$ in degree $n$). – F. C. Jun 6 '11 at 8:07

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.