A289078 Number of orderless same-trees of weight n.

1, 2, 2, 5, 2, 9, 2, 22, 6, 11, 2, 94, 2, 13, 12, 334, 2, 205, 2, 210, 14, 17, 2, 7218, 8, 19, 68, 443, 2, 1687, 2, 69109, 18, 23, 16, 167873, 2, 25, 20, 89969, 2, 7041, 2, 1548, 644, 29, 2, 36094795, 10, 3078, 24, 2604, 2, 1484102, 20, 1287306, 26, 35, 2

Offset

1,2

Comments

An orderless same-tree t is either: (case 1) a positive integer, or (case 2) a finite multiset of two or more orderless same-trees, all having the same weight. The weight of t in case 1 is the number itself, and in case 2 it is the sum of weights of the branches. For example {{{3,{1,1,1}},{2,{1,1},{1,1}}},{{{1,1,1},{1,1,1}},{{1,1},{1,1},{1,1}}}} is an orderless same-tree of weight 24 with 2 branches.

Links

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

Formula

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

Example

The a(6)=9 orderless same-trees are: 6, (33), (3(111)), (222), (22(11)), (2(11)(11)), ((11)(11)(11)), ((111)(111)), (111111).

Maple

with(numtheory):
a:= proc(n) option remember; 1 + add(
      binomial(a(n/d)+d-1, d), d=divisors(n) minus {1})
    end:
seq(a(n), n=1..60);  # Alois P. Heinz, Jul 05 2017

Mathematica

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

Prog

(PARI) seq(n)={my(v=vector(n)); for(n=1, n, v[n] = 1 + sumdiv(n, d, binomial(v[n/d]+d-1, d))); v} \\ Andrew Howroyd, Aug 20 2018

Crossrefs

Cf. A196545, A273873, A275870, A281145, A281146, A289079.

Sequence in context: A353858 A347466 A266662 * A051612 A083456 A211932

Adjacent sequences: A289075 A289076 A289077 * A289079 A289080 A289081

Keyword

nonn

Author

Gus Wiseman, Jun 23 2017

Status

approved