|
|
A167865
|
|
Number of partitions of n into distinct parts greater than 1, with each part divisible by the next.
|
|
95
|
|
|
1, 0, 1, 1, 1, 1, 2, 1, 2, 2, 2, 1, 4, 1, 3, 3, 3, 1, 5, 1, 5, 4, 3, 1, 6, 2, 5, 4, 5, 1, 9, 1, 6, 4, 4, 4, 8, 1, 6, 6, 7, 1, 11, 1, 8, 8, 4, 1, 10, 3, 10, 5, 8, 1, 11, 4, 10, 7, 6, 1, 13, 1, 10, 11, 7, 6, 15, 1, 9, 5, 11, 1, 14, 1, 9, 12, 8, 5, 15, 1, 16, 9, 8, 1, 18, 5, 12, 7, 10, 1, 21, 7, 13, 11, 5
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,7
|
|
COMMENTS
|
Number of lone-child-avoiding achiral rooted trees with n + 1 vertices, where a rooted tree is lone-child-avoiding if all terminal subtrees have at least two branches, and achiral if all branches directly under any given vertex are equal. The Matula-Goebel numbers of these trees are given by A331967. - Gus Wiseman, Feb 07 2020
|
|
LINKS
|
|
|
FORMULA
|
a(0) = 1 and for n>=1, a(n) = Sum_{d|n, d>1} a((n-d)/d).
G.f. A(x) satisfies: A(x) = 1 + x^2*A(x^2) + x^3*A(x^3) + x^4*A(x^4) + ... - Ilya Gutkovskiy, May 09 2019
|
|
EXAMPLE
|
a(12) = 4: [12], [10,2], [9,3], [8,4].
a(14) = 3: [14], [12,2], [8,4,2].
a(18) = 5: [18], [16,2], [15,3], [12,6], [12,4,2].
The a(36) = 8 lone-child-avoiding achiral rooted trees with 37 vertices:
(oooooooooooooooooooooooooooooooooooo)
((oo)(oo)(oo)(oo)(oo)(oo)(oo)(oo)(oo)(oo)(oo)(oo))
((ooo)(ooo)(ooo)(ooo)(ooo)(ooo)(ooo)(ooo)(ooo))
((ooooo)(ooooo)(ooooo)(ooooo)(ooooo)(ooooo))
((oooooooo)(oooooooo)(oooooooo)(oooooooo))
(((ooo)(ooo))((ooo)(ooo))((ooo)(ooo))((ooo)(ooo)))
((ooooooooooo)(ooooooooooo)(ooooooooooo))
((ooooooooooooooooo)(ooooooooooooooooo))
(End)
|
|
MAPLE
|
with(numtheory):
a:= proc(n) option remember;
`if`(n=0, 1, add(a((n-d)/d), d=divisors(n) minus{1}))
end:
|
|
MATHEMATICA
|
a[0] = 1; a[n_] := a[n] = DivisorSum[n, a[(n-#)/#]&, #>1&]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Oct 07 2015 *)
|
|
PROG
|
(PARI) { A167865(n) = if(n==0, return(1)); sumdiv(n, d, if(d>1, A167865((n-d)\d) ) ) }
|
|
CROSSREFS
|
The semi-achiral version is A320268.
Matula-Goebel numbers of these trees are A331967.
The semi-lone-child-avoiding version is A331991.
Achiral rooted trees are counted by A003238.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|