A167865 - OEIS

%I #28 Feb 08 2020 08:15:21

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

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

%U 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

%N Number of partitions of n into distinct parts greater than 1, with each part divisible by the next.

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

%H Alois P. Heinz, <a href="/A167865/b167865.txt">Table of n, a(n) for n = 0..10000</a>

%H Gus Wiseman, <a href="https://docs.google.com/document/d/e/2PACX-1vS1zCO9fgAIe5rGiAhTtlrOTuqsmuPos2zkeFPYB80gNzLb44ufqIqksTB4uM9SIpwlvo-oOHhepywy/pub">Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.</a>

%F a(0) = 1 and for n>=1, a(n) = Sum_{d|n, d>1} a((n-d)/d).

%F 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

%e a(12) = 4: [12], [10,2], [9,3], [8,4].

%e a(14) = 3: [14], [12,2], [8,4,2].

%e a(18) = 5: [18], [16,2], [15,3], [12,6], [12,4,2].

%e From _Gus Wiseman_, Jul 13 2018: (Start)

%e The a(36) = 8 lone-child-avoiding achiral rooted trees with 37 vertices:

%e   (oooooooooooooooooooooooooooooooooooo)

%e   ((oo)(oo)(oo)(oo)(oo)(oo)(oo)(oo)(oo)(oo)(oo)(oo))

%e   ((ooo)(ooo)(ooo)(ooo)(ooo)(ooo)(ooo)(ooo)(ooo))

%e   ((ooooo)(ooooo)(ooooo)(ooooo)(ooooo)(ooooo))

%e   ((oooooooo)(oooooooo)(oooooooo)(oooooooo))

%e   (((ooo)(ooo))((ooo)(ooo))((ooo)(ooo))((ooo)(ooo)))

%e   ((ooooooooooo)(ooooooooooo)(ooooooooooo))

%e   ((ooooooooooooooooo)(ooooooooooooooooo))

%e (End)

%p with(numtheory):

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

%p       `if`(n=0, 1, add(a((n-d)/d), d=divisors(n) minus{1}))

%p     end:

%p seq(a(n), n=0..200);  # _Alois P. Heinz_, Mar 28 2011

%t 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 *)

%o (PARI) { A167865(n) = if(n==0,return(1)); sumdiv(n,d, if(d>1, A167865((n-d)\d) ) ) }

%Y Cf. A001678, A067824, A122651, A167439, A167865, A167866, A184998, A316782.

%Y The semi-achiral version is A320268.

%Y Matula-Goebel numbers of these trees are A331967.

%Y The semi-lone-child-avoiding version is A331991.

%Y Achiral rooted trees are counted by A003238.

%Y Cf. A000081, A000669, A289079, A320222, A331912, A331933, A331936, A331992.

%K nonn,look

%O 0,7

%A _Max Alekseyev_, Nov 13 2009