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

Author

Franklin T. Adams-Watters, Jan 17 2007

Keywords

• nonn

Examples

			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....
		

Links

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

Crossrefs

Cf. A000108, A127524, A007059.

Programs

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 *)

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