|
|
A289078
|
|
Number of orderless same-trees of weight n.
|
|
27
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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:
|
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|