login
A127524
Number of unordered rooted trees where each subtree from given node has the same number of nodes.
14
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
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
Sequence in context: A318689 A365311 A083710 * A117086 A344551 A081026
KEYWORD
nonn
AUTHOR
STATUS
approved