login
Number of unlabeled lone-child-avoiding rooted trees with n vertices and more than two branches (of the root).
9

%I #20 May 10 2021 23:30:43

%S 0,0,0,1,1,2,3,6,10,20,36,70,134,263,513,1022,2030,4076,8203,16614,

%T 33738,68833,140796,288989,594621,1226781,2536532,5256303,10913196,

%U 22700682,47299699,98714362,206323140,431847121,905074333,1899247187,3990145833,8392281473

%N Number of unlabeled lone-child-avoiding rooted trees with n vertices and more than two branches (of the root).

%C Also the number of lone-child-avoiding rooted trees with n vertices and more than two branches.

%H 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Series-ReducedTree.html">Series-reduced tree.</a>

%H Gus Wiseman, <a href="https://oeis.org/A001678/a001678.txt">Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.</a>

%F For n > 1, a(n) = A001679(n) - A001678(n).

%e The a(4) = 1 through a(9) = 10 trees:

%e (ooo) (oooo) (ooooo) (oooooo) (ooooooo) (oooooooo)

%e (oo(oo)) (oo(ooo)) (oo(oooo)) (oo(ooooo))

%e (ooo(oo)) (ooo(ooo)) (ooo(oooo))

%e (oooo(oo)) (oooo(ooo))

%e (o(oo)(oo)) (ooooo(oo))

%e (oo(o(oo))) (o(oo)(ooo))

%e (oo(o(ooo)))

%e (oo(oo)(oo))

%e (oo(oo(oo)))

%e (ooo(o(oo)))

%t urt[n_]:=Join@@Table[Union[Sort/@Tuples[urt/@ptn]],{ptn,IntegerPartitions[n-1]}];

%t Table[Length[Select[urt[n],Length[#]>2&&FreeQ[#,{_}]&]],{n,10}]

%Y The not necessarily lone-child-avoiding version is A331233.

%Y The Matula-Goebel numbers of these trees are listed by A331490.

%Y A000081 counts unlabeled rooted trees.

%Y A001678 counts lone-child-avoiding rooted trees.

%Y A001679 counts topologically series-reduced rooted trees.

%Y A291636 lists Matula-Goebel numbers of lone-child-avoiding rooted trees.

%Y A331489 lists Matula-Goebel numbers of series-reduced rooted trees.

%Y Cf. A000014, A000669, A004250, A007097, A007821, A033942, A060313, A060356, A061775, A109082, A109129, A196050, A276625, A330943.

%K nonn

%O 1,6

%A _Gus Wiseman_, Jan 20 2020

%E a(37)-a(38) from _Jinyuan Wang_, Jun 26 2020

%E Terminology corrected (lone-child-avoiding, not series-reduced) by _Gus Wiseman_, May 10 2021