This site is supported by donations to The OEIS Foundation.



Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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.
(Formerly M1814 N0718)
1, 1, 2, 7, 56, 2212, 2595782, 3374959180831, 5695183504489239067484387, 16217557574922386301420531277071365103168734284282 (list; graph; refs; listen; history; text; internal format)



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.

Also called planted 3-trees or planted unary-binary trees.

The next term (which was incorrectly given) is in fact too large to include. See the b-file.

Comment from Marc LeBrun: Maximum possible number of distinct new values after applying a commuting operation N times to a single initial value.

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 number 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 (fvlamoen(AT)hotmail.com), Jan 16 2002

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

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.


I. M. H. Etherington, On non-associative combinations, Proc. Royal Soc. Edinburgh, 59 (Part 2, 1938-39), 153-162.

F. Harary et al., Counting free binary trees..., J. Combin. Inform. System Sciences, 17 (1992), 175-181.

Z. A. Melzak, A note on homogeneous dendrites, Canad. Math. Bull., 11 (1968), 85-93; http://cms.math.ca/10.4153/CMB-1968-012-1

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


David Wasserman, Table of n, a(n) for n = 0..13

Sergey Zimnitskiy, Illustration of initial terms of A006894 and A002658

Index entries for sequences related to rooted trees

Index entries for sequences related to trees

Index entries for "core" sequences


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()]


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];


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


(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 */


a002658 n = a002658_list !! n

a002658_list = 1 : 1 : f [1, 1] where

   f (x:xs) = y : f (y:x:xs') where y = x * sum xs + x * (x + 1) `div` 2

-- Reinhard Zumkeller, Apr 10 2012


Cf. A006894, A005588. First differences of A072638.

Sequence in context: A227381 A182055 A211209 * A175818 A034939 A048898

Adjacent sequences:  A002655 A002656 A002657 * A002659 A002660 A002661




N. J. A. Sloane.


Corrected by David Wasserman, Nov 20 2006



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified December 22 17:45 EST 2014. Contains 252365 sequences.