OFFSET
1,3
COMMENTS
An unlabeled rooted tree is powerful if either it is a single node or a single node with a single powerful tree as a branch, or if the branches of the root all appear with multiplicities greater than 1 and are themselves powerful trees.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 1..8000
EXAMPLE
The a(7) = 11 powerful rooted trees:
((((((o))))))
(((((oo)))))
((((ooo))))
((((o)(o))))
(((oooo)))
((ooooo))
(((o))((o)))
((oo)(oo))
((o)(o)(o))
(oo(o)(o))
(oooooo)
MAPLE
h:= proc(n, k, t) option remember; `if`(k=0, binomial(n+t, t),
`if`(n=0, 0, add(h(n-1, k-j, t+1), j=2..k)))
end:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
add(b(n-i*j, i-1)*h(a(i), j, 0), j=0..n/i)))
end:
a:= proc(n) option remember; `if`(n<2, n, b(n-1$2)+a(n-1)) end:
seq(a(n), n=1..50); # Alois P. Heinz, Aug 31 2018
MATHEMATICA
purt[n_]:=If[n==1, {{}}, Join@@Table[Select[Union[Sort/@Tuples[purt/@ptn]], Or[Length[#]==1, Min@@Length/@Split[#]>1]&], {ptn, IntegerPartitions[n-1]}]];
Table[Length[purt[n]], {n, 10}]
(* Second program: *)
h[n_, k_, t_] := h[n, k, t] = If[k == 0, Binomial[n + t, t], If[n == 0, 0, Sum[h[n - 1, k - j, t + 1], {j, 2, k}]]];
b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 1, 0, Sum[b[n - i*j, i - 1]* h[a[i], j, 0], {j, 0, n/i}]]];
a[n_] := a[n] = If[n < 2, n, b[n - 1, n - 1] + a[n - 1]];
Array[a, 50] (* Jean-François Alcover, May 10 2021, after Alois P. Heinz *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Gus Wiseman, Aug 05 2018
EXTENSIONS
a(27)-a(45) from Alois P. Heinz, Aug 31 2018
STATUS
approved