A005588 -id:A005588 - cp's OEIS frontend

A006894 Number of planted 3-trees of height < n.

1, 2, 4, 11, 67, 2279, 2598061, 3374961778892, 5695183504492614029263279, 16217557574922386301420536972254869595782763547561, 131504586847961235687181874578063117114329409897615188504091716162522225834932122128288032336298142

Offset: 1

Jeffrey Shallit and N. J. A. Sloane

Representation requires n triangular numbers with greedy algorithm.
Comment from Marc LeBrun: Maximum possible number of distinct values after applying a commuting operation from 0 to 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 greatest element of the n-th set gives a(n). The sets begin {1}, {2}, {3,4}, {5,6,7,8,9,10,11}, ... - Floor van Lamoen, Jan 16 2002
a(n+1) = (a(n))-th triangular number + 1 = A000217(a(n)) + 1. a(n) = A072638(n-1) + 1. - Jaroslav Krizek, Sep 11 2009
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.

			x + 2*x^2 + 4*x^3 + 11*x^4 + 67*x^5 + 2279*x^6 + 2598061*x^7 + 3374961778892*x^8 + ...

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 = 1..14
Luc Devroye, Michael R. Doboli, Noah A. Rosenberg, and Stephan Wagner, Tree height and the asymptotic mean of the Colijn-Plazzotta rank of unlabeled binary rooted trees, arXiv:2409.18956 [math.CO], 2024. See p. 5.
F. Harary et al., Counting free binary trees admitting a given height, J. Combin. Inform. System Sci. 17 (1992), no. 1-2, 175--181. MR1216977 (94c:05039)
Harary, Frank; Palmer, Edgar M.; Robinson, Robert W., Counting free binary trees admitting a given height, J. Combin. Inform. System Sci. 17 (1992), no. 1-2, 175-181. (Annotated scanned copy)
E. Lemoine, Note sur deux nouvelles décompositions des nombres entiers, Assoc. française pour l'avancement des sciences. Vol. 29, Tome 2, pp. 72-74, 1900.
Sergey Zimnitskiy, Illustration of initial terms of A006894 and A002658
Index entries for "core" sequences
Index entries for sequences related to rooted trees

Row sums of A036602.

A006894 := proc(n) option remember; if n=1 then 1 else A006894(n-1)*(A006894(n-1)+1)/2+1 fi end; [ seq(A006894(i),i=1..11) ];
a[ -1]:=0:a[0]:=1:for n from 1 to 50 do a[n]:=binomial(a[n-1]+2,2) od: seq(a[n]+1, n=-1..9); # Zerinvary Lajos, Jun 08 2007
a[1]:=1:for n from 2 to 10 do a[n]:=a[n-1]*(a[n-1]+1)/2+1 od: seq(a[n],n=1..10); # Miklos Kristof, Dec 11 2007

NestList[(#(#+1))/2+1&,1,12] (* Harvey P. Dale, May 24 2011 *)

v=vector(15);v[1]=1;for(i=2,#v,v[i]=binomial(v[i-1]+1,2)+1);v \\ Charles R Greathouse IV, Feb 11 2011

{a(n) = if( n<1, 0, 1 + binomial( 1 + a(n-1), 2))} /* Michael Somos, Jan 01 2013 */

from functools import lru_cache
@lru_cache(maxsize=None)
def A006894(n): return ((m:=A006894(n-1))*(m+1)>>1)+1 if n else 0 # Chai Wah Wu, Feb 20 2023

Partial sums of A002658; a(n+1) = a(n)(a(n)+1)/2 + 1 (from Marc LeBrun).
Sequence arises from a self-recursive process: a(1)=1, a(n)=a(n-1)*(a(n-1) + 1)/2 + 1. E.g., a(1)=1, a(2) = 1*2/2 + 1 = 2, a(3) = 2*3/2 + 1 = 4, a(4) = 4*5/2 + 1 = 11, a(5) = 11*12/2 + 1 = 67, ... - Miklos Kristof, Dec 11 2007
a(n) ~ 2 * c^(2^n), where c = 1.11625303268733048891316684155278646623772830100986583494311015252450055518... . - Vaclav Kotesovec, May 21 2015

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.

Original entry on oeis.org

1, 1, 2, 7, 56, 2212, 2595782, 3374959180831, 5695183504489239067484387, 16217557574922386301420531277071365103168734284282

Offset: 0

N. J. A. Sloane

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 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
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.
See A067338 for a variant of the integer partitioning construction, starting with {1,2}, {3,4,5}, ... - M. F. Hasler, Jan 21 2015

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
Mayfawny Bergmann, Efficiency of Lossless Compression of a Binary Tree via its Minimal Directed Acyclic Graph Representation. Rose-Hulman Undergraduate Mathematics Journal: Vol. 15 : Iss. 2, Article 1. (2014).
Luc Devroye, Michael R. Doboli, Noah A. Rosenberg, and Stephan Wagner, Tree height and the asymptotic mean of the Colijn-Plazzotta rank of unlabeled binary rooted trees, arXiv:2409.18956 [math.CO], 2024. See p. 5.
A. Erdelyi and I. M. H. Etherington, Some problems of non-associative combinations (II), Edinburgh Math. Notes, 32 (1940), pp. vii-xiv.
I. M. H. Etherington, Non-associate powers and a functional equation, Math. Gaz. 21 (1937), 36-39; addendum 21 (1937), 153.
I. M. H. Etherington, On non-associative combinations, Proc. Royal Soc. Edinburgh, 59 (Part 2, 1938-39), 153-162. [Annotated scanned copy]
I. M. H. Etherington, Some problems of non-associative combinations (I), 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.
F. Harary, et al., Counting free binary trees admitting a given height, J. Combin. Inform. System Sci. 17 (1992), no. 1-2, 175--181. MR1216977 (94c:05039)
Frank Harary, Edgar M. Palmer, and Robert W. Robinson, Counting free binary trees admitting a given height, J. Combin. Inform. System Sci. 17 (1992), no. 1-2, 175-181. (Annotated scanned copy)
Z. A. Melzak, A note on homogeneous dendrites, Canad. Math. Bull., 11 (1968), 85-93.
David E. Narváez, Proof of polynomial recursive equation of order 2, Jun 05 2025.
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

Cf. A006894, A005588. First differences of A072638.

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

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

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

print1(s=a=1);for(i=1,9,print1(","a*=(1-a)/2+s);s+=a) \\ M. F. Hasler, Jan 21 2015

from itertools import islice
def agen():
    yield 1
    an = s = 1
    while True:
        yield an
        an1 = an*s + an*(an+1)//2
        an, s = an1, s+an
print(list(islice(agen(), 10))) # Michael S. Branicky, Nov 14 2022

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()].
a(n) ~ 2 * c^(2^n), where c = 1.2460208329836625089431529441999359284665241772983812581752523573774108242448... . - Vaclav Kotesovec, May 21 2015
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

Corrected by David Wasserman, Nov 20 2006

cp's OEIS Frontend

A173498 Partial sums of A005588.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A006894 Number of planted 3-trees of height < n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Formula

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.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

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.