A298537 Number of unlabeled rooted trees with n nodes such that every branch of the root has the same number of nodes.

1, 1, 2, 3, 6, 10, 25, 49, 127, 291, 766, 1843, 5003, 12487, 34151, 87983, 242088, 634848, 1763749, 4688677, 13085621, 35241441, 98752586, 268282856, 755353825, 2067175933, 5837592853, 16087674276, 45550942142, 126186554309, 358344530763, 997171512999

Offset

1,3

Links

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

Formula

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

Example

The a(5) = 6 trees: ((((o)))), (((oo))), ((o(o))), ((ooo)), ((o)(o)), (oooo).

Mathematica

r[n_]:=r[n]=If[n===1, 1, Sum[Product[Binomial[r[x]+Count[ptn, x]-1, Count[ptn, x]], {x, Union[ptn]}], {ptn, IntegerPartitions[n-1]}]];
Table[If[n===1, 1, Sum[Binomial[r[(n-1)/d]+d-1, d], {d, Divisors[n-1]}]], {n, 40}]

Crossrefs

Cf. A000081, A003238, A004111, A032305, A289078, A289079, A290689, A291443, A297791, A298422, A298533, A298535, A298538, A298539.

Sequence in context: A124345 A123256 A111275 * A272079 A212606 A192440

Adjacent sequences: A298534 A298535 A298536 * A298538 A298539 A298540

Keyword

nonn

Author

Gus Wiseman, Jan 20 2018

Status

approved