%I M0628 #118 Apr 28 2019 20:09:22
%S 1,1,2,3,5,6,10,11,16,19,26,27,40,41,53,61,77,78,104,105,134,147,175,
%T 176,227,233,275,294,350,351,438,439,516,545,624,640,774,775,881,924,
%U 1069,1070,1265,1266,1444,1521,1698,1699
%N Number of rooted trees with n vertices in which vertices at the same level have the same degree.
%C Also, number of sequences of positive integers a_1, a_2, ..., a_k such that 1 + a_1*(1 + a_2*(...(1 + a_k) ... )) = n. If you take mu(a_1)*mu(a_2)*...*mu(a_k) for each sequence you get 1's 0's and -1's. Add them up and you get the terms for A007554. - _Christian G. Bower_, Oct 15 1998
%C Note that this applies also to planar rooted trees and other similar objects (mountain ranges, parenthesizations) encoded by A014486. - _Antti Karttunen_, Sep 07 2000
%C Equals sum of (n-1)-th row terms of triangle A152434. - _Gary W. Adamson_, Dec 04 2008
%C Equals the eigensequence of A051731, the inverse binomial transform. - _Gary W. Adamson_, Dec 26 2008
%C From _Emeric Deutsch_, Aug 18 2012: (Start)
%C The considered rooted trees are called generalized Bethe trees; in the Goldberg-Livshitz reference they are called uniform trees.
%C Also, a(n) = number of partitions of n-1 in which each part is divisible by the next. Example: a(5)=5 because we have 4, 31, 22, 211, and 1111.
%C There is a simple bijection between generalized Bethe trees with n+1 vertices and partitions of n in which each part is divisible by the next (the parts are given by the number of edges at the successive levels). We have the correspondences: number of edges --- sum of parts; root degree --- last part; number of leaves --- first part; height --- number of parts. (End)
%C a(n+1) = a(n) + 1 if and only if n is prime. - _Jon Perry_, Nov 24 2012
%C According to the MathOverflow link, log(a(n)) ~ log(4)*log(n)^2, and a more precise asymptotic expansion is similar to that of A018819 and hence A000123, so the conjecture in the Formula section is partly correct. - _Andrey Zabolotskiy_, Jan 22 2017
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Robert Israel, <a href="/A003238/b003238.txt">Table of n, a(n) for n = 1..10000</a>
%H G. Gati, F. Harary, R. W. Robinson, <a href="/A003238/a003238.pdf">Line colored trees with extendable automorphisms</a>, Acta Mathematica Scientia 2.1 (1982), 105-110. (Annotated scanned copy)
%H M. K. Goldberg and E. M. Livshits, <a href="http://mi.mathnet.ru/eng/mz9458">On minimal universal trees</a>, Mathematical Notes of the Acad. of Sciences of the USSR, 4, 1968, 713-717 (translation from the Russian Mat. Zametki 4 1968 371-379).
%H F. Harary and R. W. Robinson, <a href="http://dx.doi.org/10.1515/crll.1975.278-279.322">The number of achiral trees</a>, J. Reine Angew. Math., 278 (1975), 322-335.
%H F. Harary and R. W. Robinson, <a href="/A002995/a002995_1.pdf">The number of achiral trees</a>, J. Reine Angew. Math., 278 (1975), 322-335. (Annotated scanned copy)
%H B. S. Kochkarev, <a href="http://arxiv.org/abs/1205.0344">Absolutely symmetric trees and complexity of natural number</a>, arXiv:1205.0344 [math.CO], 2012.
%H MathOverflow, <a href="http://mathoverflow.net/questions/159991/are-the-asymptotics-of-a003238-known">Are the asymptotics of A003238 known?</a>
%H O. Rojo, <a href="http://dx.doi.org/10.1016/j.laa.2008.01.026">Spectra of weighted generalized Bethe trees joined at the root</a>, Linear Algebra and its Appl., 428, 2008, 2961-2979.
%H N. J. A. Sloane, <a href="http://neilsloane.com/doc/sg.txt">My favorite integer sequences</a>, in Sequences and their Applications (Proceedings of SETA '98).
%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>
%H Gus Wiseman, <a href="/A003238/a003238.png">Planted achiral trees n=1..10.</a>
%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F Shifts one place left under inverse Moebius transform: a(n+1) = Sum_{k|n} a(k).
%F Conjecture: log(a(n)) is asymptotic to c*log(n)^2 where 0.4 < c < 0.5 - _Benoit Cloitre_, Apr 13 2004
%F For n > 1, a(n) = (1/2) * A068336(n) and Sum_{k = 1..n} a(k) = A003318(n). - _Ralf Stephan_, Mar 27 2004
%F Generating function P(x) for the sequence with offset 2 obeys P(x) = x^2*(1 + Sum_{n >= 1} P(x^n)/x^n). [Harary & Robinson]. - _R. J. Mathar_, Sep 28 2011
%F a(n) = 1 + sum of a(i) such that n == 1 (mod i). - _Jon Perry_, Nov 20 2012
%F From _Ilya Gutkovskiy_, Apr 28 2019: (Start)
%F G.f.: x * (1 + Sum_{n>=1} a(n)*x^n/(1 - x^n)).
%F L.g.f.: -log(Product_{n>=1} (1 - x^n)^(a(n)/n)) = Sum_{n>=1} a(n+1)*x^n/n. (End)
%e a(4) = 3 because we have the path P(4), the tree Y, and the star \|/ . - _Emeric Deutsch_, Aug 18 2012
%e The planted achiral trees with up to 7 nodes are:
%e 1 -
%e 1 (-)
%e 2 (--), ((-))
%e 3 (---), ((--)), (((-)))
%e 5 (----), ((-)(-)), ((---)), (((--))), ((((-))))
%e 6 (-----), ((----)), (((-)(-))), (((---))), ((((--)))), (((((-)))))
%e 10 (------), ((-)(-)(-)), ((--)(--)), (((-))((-))), ((-----)), (((----))), ((((-)(-)))), ((((---)))), (((((--))))), ((((((-)))))). - _Gus Wiseman_, Jan 12 2017
%p with(numtheory): aa := proc (n) if n = 0 then 1 else add(aa(divisors(n)[i]-1), i = 1 .. tau(n)) end if end proc: a := proc (n) options operator, arrow: aa(n-1) end proc: seq(a(n), n = 1 .. 48); # _Emeric Deutsch_, Aug 18 2012
%p A003238:= proc(n) option remember; uses numtheory; add(A003238(m),m=divisors(n-1)) end proc;
%p A003238(1):= 1;
%p [seq(A003238(n),n=1..48)]; # _Robert Israel_, Mar 10 2014
%t (* b = A068336 *) b[1] = 1; b[n_] := b[n] = 1 + Sum[b[k], {k, Divisors[n-1]}]; a[n_] := b[n]/2; a[1] = 1; Table[ a[n], {n, 1, 48}] (* _Jean-François Alcover_, Dec 20 2011, after _Ralf Stephan_ *)
%t achi[n_]:=If[n===1,1,Total[achi/@Divisors[n-1]]];Array[achi,50] (* _Gus Wiseman_, Jan 12 2017 *)
%o (JavaScript)
%o a = new Array();
%o for (i = 1; i < 50; i++) a[i] = 1;
%o for (i = 3; i < 50; i++) for (j = 2; j < i; j++) if (i % j == 1) a[i] += a[j];
%o document.write(a + "<br>"); // _Jon Perry_, Nov 20 2012
%o (Haskell)
%o a003238 n = a003238_list !! (n-1)
%o a003238_list = 1 : f 1 where
%o f x = (sum (map a003238 $ a027750_row x)) : f (x + 1)
%o -- _Reinhard Zumkeller_, Dec 20 2014
%Y Cf. A007439, A007554, A057546, A152434, A051731, A002033, A027750, A281487, A000123.
%Y Row sums of A122934 (offset by 1).
%Y Cf. A004111, A280994.
%K nonn,nice,eigen
%O 1,3
%A _N. J. A. Sloane_
%E Description improved by _Christian G. Bower_, Oct 15 1998