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.
 A: 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.
A: 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.
