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

Author

Gus Wiseman, Jun 23 2017

Keywords

• nonn

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.

Examples

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

Links

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

Crossrefs

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

Programs

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]

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

Formula

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