A300650 Number of orderless same-trees of weight 2n + 1 in which all outdegrees are odd and all leaves greater than 1.

1, 1, 1, 1, 2, 1, 1, 3, 1, 1, 3, 1, 2, 6, 1, 1, 3, 3, 1, 3, 1, 1, 19, 1, 2, 3, 1, 3, 3, 1, 1, 21, 3, 1, 3, 1, 1, 28, 3, 1, 68, 1, 3, 3, 1, 3, 3, 3, 1, 25, 1, 1, 71, 1, 1, 3, 1, 3, 27, 3, 2, 3, 8, 1, 3, 1, 3, 1656, 1, 1, 3, 3, 3, 43, 1, 1, 31, 3, 1, 3, 3, 1

Offset

0,5

Comments

An orderless same-tree of weight n > 0 is either a single node of weight n, or a finite multiset of two or more orderless same-trees whose weights are all equal and sum to n.

Links

Table of n, a(n) for n=0..81.

Formula

a(1) = 1; a(n > 1) = Sum_d binomial(a(n/d) + d - 1, d) where the sum is over odd divisors of n greater than 1.

Example

The a(13) = 6 orderless same-trees: 27, (999), (99(333)), (9(333)(333)), ((333)(333)(333)), (333333333).

Mathematica

a[n_]:=If[n===1, 1, Sum[Binomial[a[n/d]+d-1, d], {d, Select[Rest[Divisors[n]], OddQ]}]];
Table[a[n], {n, 1, 100, 2}]

Prog

(PARI) f(n) = if (n==1, 1, sumdiv(n, d, if ((d > 1) && (d % 2), binomial(f(n/d)+d-1, d))));
a(n) = f(2*n+1); \\ Michel Marcus, Mar 10 2018

Crossrefs

Cf. A003238, A006241, A063834, A069283, A273873, A281145, A289078, A289079, A289501, A298118, A300436, A300439, A300574, A300647, A300648, A300649.

Sequence in context: A232529 A095374 A352063 * A363528 A300649 A086599

Adjacent sequences: A300647 A300648 A300649 * A300651 A300652 A300653

Keyword

nonn

Author

Gus Wiseman, Mar 10 2018

Status

approved