A127525 Number of ordered rooted trees where each subtree from given node has the same number of nodes.

1, 1, 2, 3, 5, 6, 12, 13, 24, 33, 60, 61, 142, 143, 289, 447, 699, 700, 1558, 1559, 3518, 5375, 8977, 8978, 17179, 20305, 40471, 54808, 98182, 98183, 242068, 242069, 477002, 695051, 1183654, 1510612, 2629806, 2629807, 5057173, 7928654, 12366025, 12366026

Offset

1,3

Links

Alois P. Heinz, Table of n, a(n) for n = 1..5590

Formula

a(1) = 1; a(n+1) = Sum_{d|n} a(n/d)^d.

L.g.f.: -log(Product_{n>=1} (1 - a(n)*x^n)^(1/n)) = Sum_{n>=1} a(n+1)*x^n/n. - Ilya Gutkovskiy, Apr 29 2019

Example

The tree shown below left counts, because the left subtree has 3 nodes and so does the right subtree and a similar condition holds for the subtrees. The tree shown on the right is not counted, because the left subtree has 3 nodes, while the right subtree has 4.
O..........O...O...O
|..........|....\./.
O...O...O..O.....O..
.\...\./....\....|..
.O...O......O...O..
..\./........\./...
...O..........O....

Maple

a:= proc(n) option remember; `if`(n<2, n, add(
      a((n-1)/d)^d, d=numtheory[divisors](n-1)))
    end:
seq(a(n), n=1..45);  # Alois P. Heinz, Sep 08 2018

Mathematica

a[1] = 1;
a[n_] := a[n] = Sum[a[(n-1)/d]^d, {d, Divisors[n-1]}];
Array[a, 45] (* Jean-François Alcover, Oct 28 2020 *)

Crossrefs

Cf. A000108, A127524, A007059.

Sequence in context: A359599 A114339 A339308 * A179333 A128958 A007435

Adjacent sequences: A127522 A127523 A127524 * A127526 A127527 A127528

Keyword

nonn

Author

Franklin T. Adams-Watters, Jan 17 2007

Status

approved