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,5

Comments

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

Links

Table of n, a(n) for n=1..30.

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

Example

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))

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}]

Crossrefs

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

Sequence in context: A002865 A085811 A187219 * A014810 A318771 A363726

Adjacent sequences: A317782 A317783 A317784 * A317786 A317787 A317788

Keyword

nonn,more

Author

Gus Wiseman, Aug 06 2018

Status

approved