login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006894 Number of planted 3-trees of height < n.
(Formerly M1254)
16
1, 2, 4, 11, 67, 2279, 2598061, 3374961778892, 5695183504492614029263279, 16217557574922386301420536972254869595782763547561, 131504586847961235687181874578063117114329409897615188504091716162522225834932122128288032336298142 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,2
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.
REFERENCES
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
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.
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
EXAMPLE
x + 2*x^2 + 4*x^3 + 11*x^4 + 67*x^5 + 2279*x^6 + 2598061*x^7 + 3374961778892*x^8 + ...
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 *)
PROG
(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
CROSSREFS
Row sums of A036602.
Sequence in context: A007903 A182100 A327484 * A193565 A198864 A038093
KEYWORD
nonn,easy,core,nice
AUTHOR
STATUS
approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 21 10:39 EDT 2024. Contains 371852 sequences. (Running on oeis4.)