login
Number of orderless same-trees of weight n.
27

%I #12 Aug 20 2018 20:51:15

%S 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,

%T 68,443,2,1687,2,69109,18,23,16,167873,2,25,20,89969,2,7041,2,1548,

%U 644,29,2,36094795,10,3078,24,2604,2,1484102,20,1287306,26,35,2

%N Number of orderless same-trees of weight n.

%C 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.

%H Alois P. Heinz, <a href="/A289078/b289078.txt">Table of n, a(n) for n = 1..2500</a>

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

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

%p with(numtheory):

%p a:= proc(n) option remember; 1 + add(

%p binomial(a(n/d)+d-1, d), d=divisors(n) minus {1})

%p end:

%p seq(a(n), n=1..60); # _Alois P. Heinz_, Jul 05 2017

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

%t Array[a,100]

%o (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

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

%K nonn

%O 1,2

%A _Gus Wiseman_, Jun 23 2017