cp's OEIS Frontend

A317707 Number of powerful rooted trees with n nodes.

%I A317707 #20 May 10 2021 11:00:00
%S A317707 1,1,2,3,5,6,11,13,22,29,46,57,94,115,180,230,349,435,671,830,1245,
%T A317707 1572,2320,2894,4287,5328,7773,9752,14066,17547,25328,31515,45010,
%U A317707 56289,79805,99467,140778,175215,246278,307273,429421,534774,745776,927776,1287038
%N A317707 Number of powerful rooted trees with n nodes.
%C A317707 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.
%H A317707 Alois P. Heinz, <a href="/A317707/b317707.txt">Table of n, a(n) for n = 1..8000</a>
%e A317707 The a(7) = 11 powerful rooted trees:
%e A317707   ((((((o))))))
%e A317707   (((((oo)))))
%e A317707   ((((ooo))))
%e A317707   ((((o)(o))))
%e A317707   (((oooo)))
%e A317707   ((ooooo))
%e A317707   (((o))((o)))
%e A317707   ((oo)(oo))
%e A317707   ((o)(o)(o))
%e A317707   (oo(o)(o))
%e A317707   (oooooo)
%p A317707 h:= proc(n, k, t) option remember; `if`(k=0, binomial(n+t, t),
%p A317707       `if`(n=0, 0, add(h(n-1, k-j, t+1), j=2..k)))
%p A317707     end:
%p A317707 b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
%p A317707       add(b(n-i*j, i-1)*h(a(i), j, 0), j=0..n/i)))
%p A317707     end:
%p A317707 a:= proc(n) option remember; `if`(n<2, n, b(n-1$2)+a(n-1)) end:
%p A317707 seq(a(n), n=1..50);  # _Alois P. Heinz_, Aug 31 2018
%t A317707 purt[n_]:=If[n==1,{{}},Join@@Table[Select[Union[Sort/@Tuples[purt/@ptn]],Or[Length[#]==1,Min@@Length/@Split[#]>1]&],{ptn,IntegerPartitions[n-1]}]];
%t A317707 Table[Length[purt[n]],{n,10}]
%t A317707 (* Second program: *)
%t A317707 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}]]];
%t A317707 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}]]];
%t A317707 a[n_] := a[n] = If[n < 2, n, b[n - 1, n - 1] + a[n - 1]];
%t A317707 Array[a, 50] (* _Jean-François Alcover_, May 10 2021, after _Alois P. Heinz_ *)
%Y A317707 Cf. A000081, A001190, A001694, A004111, A301700, A303431, A317102.
%Y A317707 Cf. A317705, A317708, A317709, A317710, A317711, A317712, A317718, A317719.
%K A317707 nonn
%O A317707 1,3
%A A317707 _Gus Wiseman_, Aug 05 2018
%E A317707 a(27)-a(45) from _Alois P. Heinz_, Aug 31 2018