|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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:
|
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|