|
|
A306200
|
|
Number of unlabeled rooted semi-identity trees with n nodes.
|
|
24
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
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.
|
|
LINKS
|
|
|
EXAMPLE
|
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)))))
|
|
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)):
|
|
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]];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|