login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006894 Number of planted 3-trees of height < n.
(Formerly M1254)
15
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

David Wasserman, Table of n, a(n) for n = 1..14

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

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

CROSSREFS

Row sums of A036602.

Sequence in context: A156434 A007903 A182100 * A193565 A198864 A038093

Adjacent sequences:  A006891 A006892 A006893 * A006895 A006896 A006897

KEYWORD

nonn,easy,core,nice

AUTHOR

Jeffrey Shallit and N. J. A. Sloane

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified November 19 08:51 EST 2017. Contains 294923 sequences.