login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A317707 Number of powerful rooted trees with n nodes. 17
1, 1, 2, 3, 5, 6, 11, 13, 22, 29, 46, 57, 94, 115, 180, 230, 349, 435, 671, 830, 1245, 1572, 2320, 2894, 4287, 5328, 7773, 9752, 14066, 17547, 25328, 31515, 45010, 56289, 79805, 99467, 140778, 175215, 246278, 307273, 429421, 534774, 745776, 927776, 1287038 (list; graph; refs; listen; history; text; internal format)
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

Cf. A000081, A001190, A001694, A004111, A301700, A303431, A317102.

Cf. A317705, A317708, A317709, A317710, A317711, A317712, A317718, A317719.

Sequence in context: A240303 A240218 A347414 * A329159 A104012 A164830

Adjacent sequences:  A317704 A317705 A317706 * A317708 A317709 A317710

KEYWORD

nonn

AUTHOR

Gus Wiseman, Aug 05 2018

EXTENSIONS

a(27)-a(45) from Alois P. Heinz, Aug 31 2018

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 17 16:32 EDT 2021. Contains 347487 sequences. (Running on oeis4.)