cp's OEIS Frontend

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.

%I A060313 #33 Feb 16 2025 08:32:44
%S A060313 1,2,0,16,25,576,2989,51584,512649,8927200,130956001,2533847328,
%T A060313 48008533885,1059817074512,24196291364925,609350187214336,
%U A060313 16135860325700881,459434230368302016,13788624945433889593,439102289933675933600,14705223056221892676741
%N 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.
%D A060313 I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983.
%H A060313 G. C. Greubel, <a href="/A060313/b060313.txt">Table of n, a(n) for n = 1..400</a>
%H A060313 David Callan, <a href="http://arxiv.org/abs/1406.7784">A sign-reversing involution to count labeled lone-child-avoiding trees</a>, arXiv:1406.7784 [math.CO], (30-June-2014).
%H A060313 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Series-ReducedTree.html">Series-reduced tree.</a>
%H A060313 Gus Wiseman, <a href="https://docs.google.com/document/d/e/2PACX-1vS1zCO9fgAIe5rGiAhTtlrOTuqsmuPos2zkeFPYB80gNzLb44ufqIqksTB4uM9SIpwlvo-oOHhepywy/pub">Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.</a>
%F A060313 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.
%F A060313 E.g.f.: x*(exp( - LambertW(-x/(1+x))) - (LambertW(-x/(1+x))/2 )^2).
%F A060313 a(n) ~ n^(n-1) * (1-exp(-1))^(n+1/2). - _Vaclav Kotesovec_, Oct 05 2013
%F A060313 E.g.f.: -(1+x)*LambertW(-x/(1+x)) - (x/2)*LambertW(-x/(1+x))^2. - _G. C. Greubel_, Mar 07 2020
%e A060313 From _Gus Wiseman_, Jan 22 2020: (Start)
%e A060313 The a(1) = 1 through a(4) = 16 trees (in the format root[branches], empty column shown as dot) are:
%e A060313   1  1[2]  .  1[2,3,4]
%e A060313      2[1]     1[2[3,4]]
%e A060313               1[3[2,4]]
%e A060313               1[4[2,3]]
%e A060313               2[1,3,4]
%e A060313               2[1[3,4]]
%e A060313               2[3[1,4]]
%e A060313               2[4[1,3]]
%e A060313               3[1,2,4]
%e A060313               3[1[2,4]]
%e A060313               3[2[1,4]]
%e A060313               3[4[1,2]]
%e A060313               4[1,2,3]
%e A060313               4[1[2,3]]
%e A060313               4[2[1,3]]
%e A060313               4[3[1,2]]
%e A060313 (End)
%p A060313 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
%t A060313 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 *)
%t A060313 sps[{}]:={{}};sps[set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,___}];
%t A060313 lrt[set_]:=If[Length[set]==0,{},Join@@Table[Apply[root,#]&/@Join@@Table[Tuples[lrt/@stn],{stn,sps[DeleteCases[set,root]]}],{root,set}]];
%t A060313 Table[Length[Select[lrt[Range[n]],Length[#]!=2&&FreeQ[Z@@#,_Integer[_]]&]],{n,6}] (* _Gus Wiseman_, Jan 22 2020 *)
%o A060313 (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
%o A060313 (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
%Y A060313 The unlabeled unrooted version is A000014.
%Y A060313 The unrooted version is A005512.
%Y A060313 The unlabeled version is A001679 or A059123.
%Y A060313 The lone-child-avoiding version is A060356.
%Y A060313 Labeled rooted trees are A000169.
%Y A060313 Cf. A000669, A001678, A108919, A254382, A331489, A331578.
%K A060313 easy,nonn
%O A060313 1,2
%A A060313 _Vladeta Jovovic_, Mar 27 2001