Series-Reduced Tree

Author

Eric W. Weisstein
March 25, 2022

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/Series-ReducedTree.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/Series-ReducedTree.html.

©2022 Wolfram Research, Inc. except for portions noted otherwise

Series-Reduced Trees

Counts

A000014

Length/@Table[GraphData/@GraphData["SeriesReduced",n],{n,12}]

Length/@Table[Select[GraphData/@GraphData["Tree",n],FreeQ[2]@*VertexDegree],{n,12}]

Counting function

A(x) = ((x-1)/x)*f(x) + ((1+x)/x^2)*g(x) - (1/x^2)*g(x)^2 where f(x) is g.f. for A059123 and g(x) is g.f. for A001678

Graphic

GraphicsGrid[Flatten[Partition[#,UpTo[10]]&/@Table[StyleGraphs[#,VertexSize->If[n==1,.02,{"Scaled",.06}]]&/@Select[GraphData/@GraphData["Tree",n],FreeQ[2]@*VertexDegree],{n,10}],1],Dividers->All,ImageSize->500]

Special cases

Select[GraphData["Classes"],GraphData[#]=!={}&&AllTrue[GraphData[#],Function[f,GraphData[f,"Tree"]&&FreeQ[GraphData[f,"VertexDegrees"],2]]]&]//Timing

Select[GraphData["Classes"],GraphData[#]=!={}&&AllTrue[GraphData[#,4;;],Function[f,GraphData[f,"Tree"]&&FreeQ[GraphData[f,"VertexDegrees"],2]]]&]//Timing

Rooted

G.f.: A(x) = ((x-1)/x)*f(x) + ((1+x)/x^2)*g(x) - (1/x^2)*g(x)^2 where f(x) is g.f. for A059123 and 1+g(x) is g.f. for A001678.

A001679

Number of series-reduced rooted trees with n nodes.

1, 1, 1, 0, 2, 2, 4, 6, 12, 20, 39, 71, 137, 261, 511, 995, 1974, 3915, 7841, 15749, 31835, 64540, 131453, 268498, 550324, 1130899, 2330381, 4813031, 9963288, 20665781, 42947715, 89410092, 186447559, 389397778, 814447067, 1705775653, 3577169927

A059123

Number of homeomorphically irreducible rooted trees (also known as series-reduced rooted trees, or rooted trees without nodes of degree 2) with n >= 1 nodes.

0, 1, 1, 0, 2, 2, 4, 6, 12, 20, 39, 71, 137, 261, 511, 995, 1974, 3915, 7841, 15749, 31835, 64540, 131453, 268498, 550324, 1130899, 2330381, 4813031, 9963288, 20665781, 42947715, 89410092, 186447559, 389397778, 814447067, 1705775653

G.f.: 1 + ((1+x)/x)*f(x) - (f(x)^2+f(x^2))/(2*x) where 1+f(x) is g.f. for A001678

f[x_]:=((x^2)/((1+x)Product[(((1-(x^k)))^(a[k+1])),{k,20}]))

ser=Rest[CoefficientList[Series[1 + ((1+x)/x)*f[x] - (f[x]^2+f[x^2])/(2*x),{x,0,5}],x]]

Sort[Solve[Thread[ser==Array[a,5],Array[a,5]]][[1]]][[All,2]]

Planted

A001678

0, 0, 1, 0, 1, 1, 2, 3, 6, 10, 19, 35, 67, 127,

x^2/((1+x)*Product_{k>0}(1-x^k)^a(k+1))

ser=Rest[CoefficientList[Series[((x^2)/((1+x)Product[(((1-(x^k)))^(a[k+1])),{k,20}])),{x,0,10}],x]];

Sort[Solve[Thread[ser==Array[a,10],Array[a,10]]][[1]]][[All,2]]