cp's OEIS Frontend

A002658 a(0) = a(1) = 1; for n > 0, a(n+1) = a(n)*(a(0) + ... + a(n-1)) + a(n)*(a(n) + 1)/2.

%I A002658 M1814 N0718 #119 Jun 10 2025 01:10:51
%S A002658 1,1,2,7,56,2212,2595782,3374959180831,5695183504489239067484387,
%T A002658 16217557574922386301420531277071365103168734284282
%N A002658 a(0) = a(1) = 1; for n > 0, a(n+1) = a(n)*(a(0) + ... + a(n-1)) + a(n)*(a(n) + 1)/2.
%C A002658 Number of planted trees in which every node has degree <= 3 and of height n; or products of height n when multiplication is commutative but non-associative.
%C A002658 Also called planted 3-trees or planted unary-binary trees.
%C A002658 The next term (which was incorrectly given) is in fact too large to include. See the b-file.
%C A002658 Comment from _Marc LeBrun_: Maximum possible number of distinct new values after applying a commuting operation N times to a single initial value.
%C A002658 Divide the natural numbers in sets of consecutive numbers, starting with {1}, each set with number of elements equal to the sum of elements of the preceding set. The sum of elements in the n-th (n>0) set gives a(n). The sets begin {1}, {2}, {3,4}, {5,6,7,8,9,10,11}, ... - _Floor van Lamoen_, Jan 16 2002
%C A002658 Consider the free algebraic system with one binary commutative (x+y) operator and one generator A. The number of elements of height n is a(n) where the height of A is zero and the height of (x+y) is one more than the maximum height of x and y. - _Michael Somos_, Mar 06 2012
%C A002658 Sergey Zimnitskiy, May 08 2013, provided an illustration for A006894 and A002658 in terms of packing circles inside circles. The following description of the figure was supplied by _Allan Wilks_. Label a blank page "1" and draw a black circle labeled "2". Subsequent circles are labeled "3", "4", ... . In the black circle put two red circles (numbered "3" and "4"); two because the label of the black circle is "2". Then in each of the red circles put blue circles in number equal to the labels of the red circles. So these get labeled "5", ..., "11". Then in each of the blue circles, starting with circle "5", place a set of green (say) circles, equal in number to the label of the enclosing blue circle. When all of the green circles have been drawn, they will be labeled "12", ..., "67". If you take the maximum circle label at each colored level, you get 1,2,4,11,67,2279,..., which is A006894, which itself is the partial sums of A002658. The picture is a visualization of _Floor van Lamoen_'s comment above.
%C A002658 See A067338 for a variant of the integer partitioning construction, starting with {1,2}, {3,4,5}, ... - _M. F. Hasler_, Jan 21 2015
%D A002658 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A002658 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A002658 David Wasserman, <a href="/A002658/b002658.txt">Table of n, a(n) for n = 0..13</a>
%H A002658 Mayfawny Bergmann, <a href="http://scholar.rose-hulman.edu/rhumj/vol15/iss2/1/">Efficiency of Lossless Compression of a Binary Tree via its Minimal Directed Acyclic Graph Representation</a>. Rose-Hulman Undergraduate Mathematics Journal: Vol. 15 : Iss. 2, Article 1. (2014).
%H A002658 Luc Devroye, Michael R. Doboli, Noah A. Rosenberg, and Stephan Wagner, <a href="https://arxiv.org/abs/2409.18956">Tree height and the asymptotic mean of the Colijn-Plazzotta rank of unlabeled binary rooted trees</a>, arXiv:2409.18956 [math.CO], 2024. See p. 5.
%H A002658 A. Erdelyi and I. M. H. Etherington, <a href="http://dx.doi.org/10.1017/S0950184300002640">Some problems of non-associative combinations (II)</a>, Edinburgh Math. Notes, 32 (1940), pp. vii-xiv.
%H A002658 I. M. H. Etherington, <a href="http://www.jstor.org/stable/3605743">Non-associate powers and a functional equation</a>, Math. Gaz. 21 (1937), 36-39; addendum 21 (1937), 153.
%H A002658 I. M. H. Etherington, <a href="/A000108/a000108_13.pdf">On non-associative combinations</a>, Proc. Royal Soc. Edinburgh, 59 (Part 2, 1938-39), 153-162. [Annotated scanned copy]
%H A002658 I. M. H. Etherington, <a href="http://dx.doi.org/10.1017/S0950184300002639">Some problems of non-associative combinations (I)</a>, Edinburgh Math. Notes, 32 (1940), pp. i-vi. Part II is by A. Erdelyi and I. M. H. Etherington, and is on pages vii-xiv of the same issue.
%H A002658 F. Harary, et al., <a href="http://cobweb.cs.uga.edu/~rwr/publications/binary.pdf">Counting free binary trees admitting a given height</a>, J. Combin. Inform. System Sci. 17 (1992), no. 1-2, 175--181. MR1216977 (94c:05039)
%H A002658 Frank Harary, Edgar M. Palmer, and Robert W. Robinson, <a href="/A005588/a005588.pdf">Counting free binary trees admitting a given height</a>, J. Combin. Inform. System Sci. 17 (1992), no. 1-2, 175-181. (Annotated scanned copy)
%H A002658 Z. A. Melzak, <a href="http://dx.doi.org/10.4153/CMB-1968-012-1">A note on homogeneous dendrites</a>, Canad. Math. Bull., 11 (1968), 85-93.
%H A002658 David E. Narváez, <a href="/A002658/a002658.pdf">Proof of polynomial recursive equation of order 2</a>, Jun 05 2025.
%H A002658 Sergey Zimnitskiy, <a href="/A006894/a006894.jpg">Illustration of initial terms of A006894 and A002658</a>
%H A002658 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%H A002658 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%H A002658 <a href="/index/Cor#core">Index entries for "core" sequences</a>
%F A002658 a(n + 1) = a(n) * (a(n) / a(n-1) + (a(n) + a(n-1)) / 2) [equation (5) on page 87 of Melzak 1968 with a() instead of his f()].
%F A002658 a(n) ~ 2 * c^(2^n), where c = 1.2460208329836625089431529441999359284665241772983812581752523573774108242448... . - _Vaclav Kotesovec_, May 21 2015
%F A002658 a(n) = (-1/4)*(a(n-2)^3 - 2*a(n-1)^2 - 6*a(n-1)*a(n-2) - 4*a(n-2)^2 - 8*a(n-1) + 11*a(n-2)) (see Narváez link for proof). - _Boštjan Gec_, Dec 03 2024
%p A002658 s := proc(n) local i,j,ans; ans := [ 1 ]; for i to n do ans := [ op(ans),ans[ i ]*(add(j,j=ans)-ans[ i ])+ans[ i ]*(ans[ i ]+1)/2 ] od; RETURN(ans); end; t1 := s(10); A002658 := n->t1[n];
%t A002658 Clear[a, b]; a[0] = a[1] = 1; b[0] = b[1] = 1; b[n_] := b[n] = b[n-1] + a[n-1]; a[n_] := a[n] = (a[n-1]+1)*a[n-1]/2 + a[n-1]*b[n-1]; Table[a[n], {n, 0, 9}] (* _Jean-François Alcover_, Jan 31 2013, after Frank Harary *)
%t A002658 RecurrenceTable[{a[n] == a[n-1]*(a[n-1]/a[n-2]+(a[n-1]+a[n-2])/2), a[0]==1, a[1]==1},a,{n,0,10}] (* _Vaclav Kotesovec_, May 21 2015 *)
%o A002658 (PARI) {a(n) = local(a1, a2); if( n<2, n>=0, a2 = a(n-1); a1 = a(n-2); a2 * (a2 / a1 + (a1 + a2) / 2))} /* _Michael Somos_, Mar 06 2012 */
%o A002658 (PARI) print1(s=a=1);for(i=1,9,print1(","a*=(1-a)/2+s);s+=a) \\ _M. F. Hasler_, Jan 21 2015
%o A002658 (Haskell)
%o A002658 a002658 n = a002658_list !! n
%o A002658 a002658_list = 1 : 1 : f [1,1] where
%o A002658    f (x:xs) = y : f (y:x:xs') where y = x * sum xs + x * (x + 1) `div` 2
%o A002658 -- _Reinhard Zumkeller_, Apr 10 2012
%o A002658 (Python)
%o A002658 from itertools import islice
%o A002658 def agen():
%o A002658     yield 1
%o A002658     an = s = 1
%o A002658     while True:
%o A002658         yield an
%o A002658         an1 = an*s + an*(an+1)//2
%o A002658         an, s = an1, s+an
%o A002658 print(list(islice(agen(), 10))) # _Michael S. Branicky_, Nov 14 2022
%Y A002658 Cf. A006894, A005588. First differences of A072638.
%K A002658 nonn,easy,core,nice
%O A002658 0,3
%A A002658 _N. J. A. Sloane_
%E A002658 Corrected by _David Wasserman_, Nov 20 2006