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,3

Links

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

Formula

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

Example

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

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

Crossrefs

Cf. A000081, A127525.

Sequence in context: A318689 A365311 A083710 * A117086 A344551 A081026

Adjacent sequences: A127521 A127522 A127523 * A127525 A127526 A127527

Keyword

nonn

Author

Franklin T. Adams-Watters, Jan 17 2007

Status

approved