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

1, 1, 2, 3, 5, 6, 11, 12, 20, 25, 42, 43, 81, 82, 150, 192, 287, 288, 563, 564, 982, 1277, 2182, 2183, 3658, 3785, 7108, 8659, 13101, 13102, 27827, 27828, 47768, 61025, 102355, 105689, 170882, 170883, 329651, 421547, 606283, 606284, 1193038, 1193039, 2158117

Offset: 1

Author

Franklin T. Adams-Watters, Jan 17 2007

Keywords

• nonn

Examples

			The tree shown below left counts, because the subtree shown on the left has 3 nodes and so does the one on the right and a similar condition holds for the subtrees. The tree shown on the right is not counted, because the subtree shown on the left has 3 nodes, while the one on the right 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..1000

Crossrefs

Cf. A000081, A127525.

Programs

Maple

with(numtheory):
a:= proc(n) option remember; `if`(n<2, n,
      add(binomial(a((n-1)/d)+d-1, d), d=divisors(n-1)))
    end:
seq(a(n), n=1..50);  # Alois P. Heinz, May 16 2013

Mathematica

a[1] = 1; a[n_] := a[n] = DivisorSum[n-1, Binomial[a[(n-1)/#]+#-1, #]&]; Table[a[n], {n, 1, 50}] (* Jean-François Alcover, Feb 25 2017 *)

Formula

a(1) = 1; a(n+1) = Sum_{d|n} C(a(n/d) + d-1, d).