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

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

Offset: 1

Author

Jeffrey Shallit and N. J. A. Sloane

Keywords

• nonn
• easy
• core
• nice

Comments

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.

Examples

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

References

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

Links

• 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

Crossrefs

Row sums of A036602.

Programs

Maple

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

Mathematica

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

PARI

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

PARI

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

Python

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

Formula

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