A060313 Number of homeomorphically irreducible rooted trees (also known as series-reduced rooted trees, or rooted trees without nodes of degree 2) on n labeled nodes.

1, 2, 0, 16, 25, 576, 2989, 51584, 512649, 8927200, 130956001, 2533847328, 48008533885, 1059817074512, 24196291364925, 609350187214336, 16135860325700881, 459434230368302016, 13788624945433889593, 439102289933675933600, 14705223056221892676741

Offset

1,2

References

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983.

Links

G. C. Greubel, Table of n, a(n) for n = 1..400

David Callan, A sign-reversing involution to count labeled lone-child-avoiding trees, arXiv:1406.7784 [math.CO], (30-June-2014).

Eric Weisstein's World of Mathematics, Series-reduced tree.

Gus Wiseman, Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.

Formula

a(n) = n*(n-2)!*Sum_{k=0..n-2} (-1)^k*binomial(n, k)*(n-k)^(n-k-2)/(n-k-2)!, n>1.

E.g.f.: x*(exp( - LambertW(-x/(1+x))) - (LambertW(-x/(1+x))/2 )^2).

a(n) ~ n^(n-1) * (1-exp(-1))^(n+1/2). - Vaclav Kotesovec, Oct 05 2013

E.g.f.: -(1+x)*LambertW(-x/(1+x)) - (x/2)*LambertW(-x/(1+x))^2. - G. C. Greubel, Mar 07 2020

Example

From Gus Wiseman, Jan 22 2020: (Start)
The a(1) = 1 through a(4) = 16 trees (in the format root[branches], empty column shown as dot) are:
  1  1[2]  .  1[2,3,4]
     2[1]     1[2[3,4]]
              1[3[2,4]]
              1[4[2,3]]
              2[1,3,4]
              2[1[3,4]]
              2[3[1,4]]
              2[4[1,3]]
              3[1,2,4]
              3[1[2,4]]
              3[2[1,4]]
              3[4[1,2]]
              4[1,2,3]
              4[1[2,3]]
              4[2[1,3]]
              4[3[1,2]]
(End)

Maple

seq( `if`(n=1, 1, n*(n-2)!*add((-1)^k*binomial(n, k)*(n-k)^(n-k-2)/(n-k-2)!, k=0..n-2)), n=1..20); # G. C. Greubel, Mar 07 2020

Mathematica

f[n_] := If[n < 2, 1, n(n - 2)!Sum[(-1)^k*Binomial[n, k](n - k)^(n - 2 - k)/(n - 2 - k)!, {k, 0, n - 2}]]; Table[ f[n], {n, 19}] (* Robert G. Wilson v, Feb 12 2005 *)
sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];
lrt[set_]:=If[Length[set]==0, {}, Join@@Table[Apply[root, #]&/@Join@@Table[Tuples[lrt/@stn], {stn, sps[DeleteCases[set, root]]}], {root, set}]];
Table[Length[Select[lrt[Range[n]], Length[#]!=2&&FreeQ[Z@@#, _Integer[_]]&]], {n, 6}] (* Gus Wiseman, Jan 22 2020 *)

Prog

(Magma) [1] cat [n*Factorial(n-2)*(&+[(-1)^k*Binomial(n, k)*(n-k)^(n-k-2)/Factorial(n-k-2): k in [0..n-2]]): n in [2..20]] // G. C. Greubel, Mar 07 2020
(Sage) [1]+[n*factorial(n-2)*sum((-1)^k*binomial(n, k)*(n-k)^(n-k-2)/factorial( n-k-2) for k in (0..n-2)) for n in (2..20)] # G. C. Greubel, Mar 07 2020

Crossrefs

The unlabeled unrooted version is A000014.

The unrooted version is A005512.

The unlabeled version is A001679 or A059123.

The lone-child-avoiding version is A060356.

Labeled rooted trees are A000169.

Cf. A000669, A001678, A108919, A254382, A331489, A331578.

Sequence in context: A354416 A057375 A009045 * A371893 A015154 A346119

Adjacent sequences: A060310 A060311 A060312 * A060314 A060315 A060316

Keyword

easy,nonn

Author

Vladeta Jovovic, Mar 27 2001

Status

approved