A317718 Number of uniform relatively prime rooted trees with n nodes.

1, 1, 2, 4, 7, 13, 27, 55, 125, 278, 650, 1510, 3624, 8655, 21017, 51212, 125857, 310581, 770767, 1920226

Offset

1,3

Comments

An unlabeled rooted tree is uniform and relatively prime iff either it is a single node or a single node with a single uniform relatively prime branch, or the branches of the root have empty intersection (relatively prime) and equal multiplicities (uniform) and are themselves uniform relatively prime trees.

Links

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

A. David Christopher and M. Davamani Christober, Relatively Prime Uniform Partitions, Gen. Math. Notes, Vol. 13, No. 2, December, 2012, pp. 1-12.

Example

The a(6) = 13 uniform relatively prime rooted trees:
  (((((o)))))
  ((((oo))))
  (((o(o))))
  (((ooo)))
  ((o((o))))
  ((o(oo)))
  ((oooo))
  (o(((o))))
  (o((oo)))
  (o(o(o)))
  (o(ooo))
  ((o)((o)))
  (ooooo)

Mathematica

purt[n_]:=purt[n]=If[n==1, {{}}, Join@@Table[Select[Union[Sort/@Tuples[purt/@ptn]], Or[Length[#]==1, And[SameQ@@Length/@Split[#], Intersection@@#=={}]]&], {ptn, IntegerPartitions[n-1]}]];
Table[Length[purt[n]], {n, 20}]

Crossrefs

Cf. A000081, A001190, A004111, A072774, A301700, A317588.

Cf. A317705, A317707, A317708, A317709, A317710, A317711, A317712, A317717.

Sequence in context: A309050 A265580 A136408 * A357931 A103104 A103480

Adjacent sequences: A317715 A317716 A317717 * A317719 A317720 A317721

Keyword

nonn,more

Author

Gus Wiseman, Aug 05 2018

Status

approved