A306200 Number of unlabeled rooted semi-identity trees with n nodes.

0, 1, 1, 2, 4, 8, 18, 41, 98, 237, 591, 1488, 3805, 9820, 25593, 67184, 177604, 472177, 1261998, 3388434, 9136019, 24724904, 67141940, 182892368, 499608724, 1368340326, 3756651116, 10336434585, 28499309291, 78727891420, 217870037932, 603934911859, 1676720329410

Offset: 0

Author

Gus Wiseman, Jan 29 2019

Keywords

• nonn

Comments

A rooted tree is a semi-identity tree if the non-leaf branches of the root are all distinct and are themselves semi-identity trees.

Examples

			The a(1) = 1 through a(7) = 8 trees:
  o  (o)  (oo)   (ooo)    (oooo)     (ooooo)
          ((o))  ((oo))   ((ooo))    ((oooo))
                 (o(o))   (o(oo))    (o(ooo))
                 (((o)))  (oo(o))    (oo(oo))
                          (((oo)))   (ooo(o))
                          ((o(o)))   (((ooo)))
                          (o((o)))   ((o)(oo))
                          ((((o))))  ((o(oo)))
                                     ((oo(o)))
                                     (o((oo)))
                                     (o(o(o)))
                                     (oo((o)))
                                     ((((oo))))
                                     (((o(o))))
                                     ((o)((o)))
                                     ((o((o))))
                                     (o(((o))))
                                     (((((o)))))
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..2166

Crossrefs

Cf. A000081, A004111, A276625, A301700, A306201, A316471, A316474, A317708, A317712, A317718.

Programs

Maple

b:= proc(n, i) option remember; `if`(n=0 or i=1, 1,
      add(b(n-i*j, i-1)*binomial(a(i), j), j=0..n/i))
    end:
a:= n-> `if`(n=0, 0, b(n-1$2)):
seq(a(n), n=0..35);  # Alois P. Heinz, Jan 29 2019

Mathematica

ursit[n_]:=Join@@Table[Select[Union[Sort/@Tuples[ursit/@ptn]],UnsameQ@@DeleteCases[#,{}]&],{ptn,IntegerPartitions[n-1]}];
Table[Length[ursit[n]],{n,10}]
(* Second program: *)
b[n_, i_] := b[n, i] = If[n == 0 || i == 1, 1,
     Sum[b[n - i*j, i - 1]*Binomial[a[i], j], {j, 0, n/i}]];
a[n_] := If[n == 0, 0, b[n - 1, n - 1]];
a /@ Range[0, 35] (* Jean-François Alcover, May 10 2021, after Alois P. Heinz *)

Extensions

More terms from Alois P. Heinz, Jan 29 2019