cp's OEIS Frontend

A003238 Number of rooted trees with n vertices in which vertices at the same level have the same degree.

%I A003238 M0628 #127 Jun 08 2025 17:33:06
%S A003238 1,1,2,3,5,6,10,11,16,19,26,27,40,41,53,61,77,78,104,105,134,147,175,
%T A003238 176,227,233,275,294,350,351,438,439,516,545,624,640,774,775,881,924,
%U A003238 1069,1070,1265,1266,1444,1521,1698,1699
%N A003238 Number of rooted trees with n vertices in which vertices at the same level have the same degree.
%C A003238 Also, number of sequences of positive integers b_1, b_2, ..., b_k such that 1 + b_1*(1 + b_2*(...(1 + b_k) ... )) = n. If you take mu(b_1)*mu(b_2)*...*mu(b_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 A003238 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 A003238 Equals sum of (n-1)-th row terms of triangle A152434. - _Gary W. Adamson_, Dec 04 2008
%C A003238 Equals the eigensequence of A051731, the inverse binomial transform. - _Gary W. Adamson_, Dec 26 2008
%C A003238 From _Emeric Deutsch_, Aug 18 2012: (Start)
%C A003238 The considered rooted trees are called generalized Bethe trees; in the Goldberg-Livshitz reference they are called uniform trees.
%C A003238 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 A003238 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 A003238 a(n+1) = a(n) + 1 if and only if n is prime. - _Jon Perry_, Nov 24 2012
%C A003238 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 A003238 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A003238 Robert Israel, <a href="/A003238/b003238.txt">Table of n, a(n) for n = 1..10000</a>
%H A003238 G. Gati, F. Harary, and 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 A003238 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 A003238 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 A003238 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 A003238 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 A003238 MathOverflow, <a href="http://mathoverflow.net/questions/159991/are-the-asymptotics-of-a003238-known">Are the asymptotics of A003238 known?</a>
%H A003238 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 A003238 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 A003238 N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>
%H A003238 Gus Wiseman, <a href="/A003238/a003238.png">Planted achiral trees n=1..10.</a>
%H A003238 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%H A003238 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F A003238 Shifts one place left under inverse Moebius transform: a(n+1) = Sum_{k|n} a(k).
%F A003238 Conjecture: log(a(n)) is asymptotic to c*log(n)^2 where 0.4 < c < 0.5 - _Benoit Cloitre_, Apr 13 2004
%F A003238 For n > 1, a(n) = (1/2) * A068336(n) and Sum_{k = 1..n} a(k) = A003318(n). - _Ralf Stephan_, Mar 27 2004
%F A003238 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 A003238 a(n) = 1 + sum of a(i) such that n == 1 (mod i). - _Jon Perry_, Nov 20 2012
%F A003238 From _Ilya Gutkovskiy_, Apr 28 2019: (Start)
%F A003238 G.f.: x * (1 + Sum_{n>=1} a(n)*x^n/(1 - x^n)).
%F A003238 L.g.f.: -log(Product_{n>=1} (1 - x^n)^(a(n)/n)) = Sum_{n>=1} a(n+1)*x^n/n. (End)
%e A003238 a(4) = 3 because we have the path P(4), the tree Y, and the star \|/ . - _Emeric Deutsch_, Aug 18 2012
%e A003238 The planted achiral trees with up to 7 nodes are:
%e A003238  1  -
%e A003238  1  (-)
%e A003238  2  (--),     ((-))
%e A003238  3  (---),    ((--)),      (((-)))
%e A003238  5  (----),   ((-)(-)),    ((---)),    (((--))),     ((((-))))
%e A003238  6  (-----),  ((----)),    (((-)(-))), (((---))),    ((((--)))), (((((-)))))
%e A003238 10 (------), ((-)(-)(-)), ((--)(--)), (((-))((-))), ((-----)),  (((----))), ((((-)(-)))), ((((---)))), (((((--))))), ((((((-)))))). - _Gus Wiseman_, Jan 12 2017
%p A003238 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 A003238:= proc(n) option remember; uses numtheory; add(A003238(m),m=divisors(n-1)) end proc;
%p A003238 A003238(1):= 1;
%p A003238 [seq(A003238(n),n=1..48)]; # _Robert Israel_, Mar 10 2014
%t A003238 (* 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 A003238 achi[n_]:=If[n===1,1,Total[achi/@Divisors[n-1]]];Array[achi,50] (* _Gus Wiseman_, Jan 12 2017 *)
%o A003238 (JavaScript)
%o A003238 a = new Array();
%o A003238 for (i = 1; i < 50; i++) a[i] = 1;
%o A003238 for (i = 3; i < 50; i++) for (j = 2; j < i; j++) if (i % j == 1) a[i] += a[j];
%o A003238 document.write(a + "<br>"); // _Jon Perry_, Nov 20 2012
%o A003238 (Haskell)
%o A003238 a003238 n = a003238_list !! (n-1)
%o A003238 a003238_list = 1 : f 1 where
%o A003238    f x = (sum (map a003238 $ a027750_row x)) : f (x + 1)
%o A003238 -- _Reinhard Zumkeller_, Dec 20 2014
%o A003238 (PARI) seq(n) = {my(v=vector(n)); v[1]=1; for(i=2, n, v[i]=sumdiv(i-1, d, v[d])); v} \\ _Andrew Howroyd_, Jun 08 2025
%Y A003238 Cf. A007439, A007554, A057546, A152434, A051731, A002033, A027750, A281487, A000123.
%Y A003238 Row sums of A122934 (offset by 1).
%Y A003238 Cf. A004111, A280994.
%K A003238 nonn,nice,eigen
%O A003238 1,3
%A A003238 _N. J. A. Sloane_
%E A003238 Description improved by _Christian G. Bower_, Oct 15 1998