# How to count the number of cubic tree-level Feynman diagrams at $n$ points?

I'm following this paper: arXiv:0805.3993 [hep-ph] where it's said that the total number of distinct tree-level diagrams at $n$-points with cubic vertices only is $(2n-5)!!$

I want to know where this $(2n-5)!!$ comes from.

I'm trying to count the diagrams but it's getting difficult to generalize. Previously in the same paper the full tree amplitude is written as $$\mathcal{A}_n^\text{tree}(1,2,3,\ldots,n)=g^{n-2}\sum_{\mathcal{P}(2,3,\ldots,n)}\mathrm{Tr}[T^{a_1}T^{a_2}T^{a_3}\cdots{T}^{a_n}]A_n^\text{tree}(1,2,3,\ldots,n)$$ where the sum is over all noncyclic permutations of legs, which is equivalent to all permutations keeping leg 1 fixed. This would give $(n-1)!$ diagrams. For $n=4$ it's easy to see the overcounting: the possible arrangements are the $s$, $t$ and $u$ channels, $$(1,2)(3,4)\\(1,3)(2,4)\\(1,4)(2,3)$$ precisely $3!!=3\cdot1$ and the overcounting in the amplitude expression arises from $(a,b)=(b,a)$. With my notation I mean e.g. for $(1,2)(3,4)$:

For $n=5$, $$1(2,3)(4,5)\\ 1(2,4)(3,5)\\ 1(2,5)(3,4)\\ 2(3,4)(5,1)\\ 2(3,5)(1,4)\\ 2(3,1)(4,5)\\ 3(4,5)(1,2)\\ 3(4,1)(2,5)\\ 3(4,2)(5,1)\\ 4(5,1)(2,3)\\ 4(5,2)(3,1)\\ 4(5,3)(1,2)\\ 5(1,2)(3,4)\\ 5(1,3)(4,2)\\ 5(1,4)(2,3)$$ there are $5!!=5\cdot3\cdot1=15$ diagrams but now I don't see so clear how to extract the overcounting; similarly now in my notation $c(a,b)(d,e)$ means leg $c$ inserted in a propagator, e.g. for $3(4,5)(1,2)$:

For $n=6$ there are $7!!=7\cdot5\cdot3\cdot1=105$ diagrams but I guess the pattern should be able to be seen from the previous cases and taking into account that now there are two different topologies, i.e. $cd(a,b)(e,f)$ and $(a,b)(c,d)(e,f)$ where $cd\neq{dc}$. I feel like I'm in the right track but however not getting anywhere. I also tried to brute force a relation between the !! and the ! but only got $(2n-5)!!=2^{2-n}\frac{(n-1)(2n-4)!}{(n-1)!}$ which tells me nothing.

• I think you should add a note that you are counting the tree level diagrams. In case of the loop diagrams, this is much, much harder to count. – Andrii Magalich Jun 13 '16 at 19:30
• Yes, I wrote it in the title but I'll write it explicitly again in the body. Thanks – Cal Gibson Jun 13 '16 at 20:29

To obtain a diagram with $n$ external legs from a diagram with $n-1$ external legs, you can insert the external leg labelled $n$ into any of the $2n-5$ edges. That there are $2n-5$ edges in a diagram with $n-1$ external legs follows by induction, since there are $3$ edges in a diagram with $3$ external legs and the insertion of another external leg increases the number of edges by two.

You might want to try posting such questions on math.SE in the future, where a combinatorial question like this would most likely not have survived unanswered for two days.

User joriki has already provided a correct answer. Here we just add details and make some clarifying remarks.

I) Let $n\geq 3$ be an integer. Consider the set ${\cal T}(n)$ of connected trees with cubic vertices only and with $E_n=n$ external labelled lines with labels $1,\ldots, n$, and no labelling of internal lines and vertices. (We stress that loops are not allowed.) Clearly the number of vertices is $V_n=n\!-\!2$, and the number of internal lines is $I_n=n\!-\!3$, so the total number of lines is $$L_n~=~E_n+I_n~=~2n-3.\tag{1}$$ We want to prove by induction that $$|{\cal T}(n)|~=~(2n-5)!! \tag{2}$$ Obviously the formula holds for $n=3$ $$|{\cal T}(3)|~=~1.\tag{3}$$

II) Now let us consider the induction step. Consider a tree $T_{n-1}\in{\cal T}(n\!-\!1)$ with $L_{n-1}=2n-5$ lines. For each line

         |
|
|


in the tree $T_{n-1}$, we can add a vertex and an external line with the label $n$:

         |
n----|
|


It is clear that the new tree $T_n$ belongs to ${\cal T}(n)$.

III) Conversely, if $n\geq 4$, and if we have a tree $T_n\in {\cal T}(n)$, we can by removing the external line with the label $n$ (and its neighboring vertex) obtain a tree $T_{n-1}\in{\cal T}(n\!-\!1)$. We conclude that

$$|{\cal T}(n)|~=~(2n-5) |{\cal T}(n\!-\!1)|.\tag{4}$$

The sought-for formula (2) follows.