A034940 Number of rooted labeled triangular cacti with 2n+1 nodes (n triangles).

1, 3, 75, 5145, 688905, 152193195, 50174679555, 23089081640625, 14140034726843025, 11119632520038117075, 10920803043967635894075, 13100477280449146440878025, 18849023772776126861572265625, 32038907667175368299033846026875, 63516199119599233704934379969701875

Offset: 0

Author

Christian G. Bower, Oct 15 1998

Keywords

• nonn
• eigen

Examples

			E.g. a(3) = 5!! 7^3 = (1*3*5) * 343 = 5145.
From _Peter Bala_, Jul 31 2012: (Start)
Relation with rows of A214406: F(x) := A(exp(x)).
(d/dx)^1(F) = F/(1-F^2)
(d/dx)^2(F)) = F*(1 + F^2)/(1 - F^2)^3
(d/dx)^3(F)) = F*(1 + 8*F^2 + 3*F^4)/(1 - F^2)^5
(d/dx)^4(F)) = F*(1 + 33*F^2 + 71*F^4 + 15*F^6)/(1 - F^2)^7
(End)
		

References

• F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 307. (4.2.44)

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..100
• Maryam Bahrani and Jérémie Lumbroso, Enumerations, Forbidden Subgraph Characterizations, and the Split-Decomposition, arXiv:1608.01465 [math.CO], 2016.
• Wikipedia, Lagrange Inversion Theorem
• Index entries for sequences related to cacti

Crossrefs

Cf. A003080, A000169, A214406.

Programs

Mathematica

a[n_] := (2*n-1)!!*(2*n+1)^n; Table[a[n], {n, 0, 11}] (* Jean-François Alcover, May 13 2013, after Noam D. Elkies *)

PARI

a(n) = (2*n+1)^n*(2*n)!/(2^n*n!); \\ Andrew Howroyd, Aug 30 2018

Formula

a(n) = b(2*n+1) where e.g.f. of b satisfies B(x)=x*exp(B(x)^2/2).

The closed form a(n) = (2n-1)!! (2n+1)^n can be obtained from the generating function. - Noam D. Elkies, Dec 16 2002

From Peter Bala, Jul 31 2012: (Start)

E.g.f. A(x) = series reversion of x*exp(-1/2*x^2) = sum {n >= 0} a(n)*x^(2*n+1)/(2*n+1)! = x + 3*x^3/3! + 75*x^5/5! + .... The Lagrange inversion formula gives a(n) = (2*n+1)^n*(2*n)!/(2^n*n!).

A(x)^2 = T(x^2), where T denotes the tree function T(x) := sum {n >= 1} n^(n-1)*x^n/n!. A(x)^r = sum {n >= 0} r*(2*n+r)^(n-1)*x^(2*n+r)/(2^n*n!).

x = A(x)*exp(-1/2*A(x)^2). dA/dx = exp(1/2*A^2)/(1-A^2).

Let the function F(x) = A(exp(x)). Then dF/dx = F/(1-F^2). More generally, (d/dx)^(n+1)(F) is a rational function in F(x) given by (d/dx)^(n+1)(F) = F*R(n,F^2)/(1-F^2)^(2*n+1), where R(n,x) is the n-th row generating polynomial of A214406.

(End)

Extensions

a(10) corrected by Jean-François Alcover, May 13 2013

a(12)-a(14) from Alois P. Heinz, Jul 08 2015