A317785 Number of locally connected rooted trees with n nodes.

1, 1, 1, 1, 2, 2, 4, 4, 7, 8, 12, 14, 21, 24, 34, 42, 55, 67, 91, 109, 144, 177, 228, 281, 366, 448, 579, 720, 916, 1142

Offset: 1

Author

Gus Wiseman, Aug 06 2018

Keywords

• nonn
• more

Comments

An unlabeled rooted tree is locally connected if the branches directly under any given node are connected as a hypergraph.

Examples

			The a(11) = 12 locally connected rooted trees:
  ((((((((((o))))))))))
  ((((((((o)(o))))))))
  (((((((o))((o)))))))
  ((((((o)))(((o))))))
  (((((o))))((((o)))))
  ((((((o)(o)(o))))))
  (((((o))((o)(o)))))
  ((((o))((o))((o))))
  ((((o)(o)(o)(o))))
  (((o))((o)(o)(o)))
  (((o)(o))((o)(o)))
  ((o)(o)(o)(o)(o))
		

Links

• Gus Wiseman, All 42 locally connected rooted trees with 16 nodes.

Crossrefs

Cf. A000081, A276625, A286518, A286520, A301700, A304714, A316473, A316475, A317077, A317078, A317708, A317787.

Programs

Mathematica

multijoin[mss__]:=Join@@Table[Table[x, {Max[Count[#, x]&/@{mss}]}], {x, Union[mss]}];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Union[Append[Delete[s,List/@c[[1]]],multijoin@@s[[c[[1]]]]]]]]];
rurt[n_]:=If[n==1,{{}},Join@@Table[Select[Union[Sort/@Tuples[rurt/@ptn]],Or[Length[#]==1,Length[csm[#]]==1]&],{ptn,IntegerPartitions[n-1]}]];
Table[Length[rurt[n]],{n,10}]