|
%I M1254 #63 Feb 20 2023 11:45:34
%S 1,2,4,11,67,2279,2598061,3374961778892,5695183504492614029263279,
%T 16217557574922386301420536972254869595782763547561,
%U 131504586847961235687181874578063117114329409897615188504091716162522225834932122128288032336298142
%N Number of planted 3-trees of height < n.
%C Representation requires n triangular numbers with greedy algorithm.
%C 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.
%C 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
%C a(n+1) = (a(n))-th triangular number + 1 = A000217(a(n)) + 1. a(n) = A072638(n-1) + 1. - _Jaroslav Krizek_, Sep 11 2009
%C 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.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H David Wasserman, <a href="/A006894/b006894.txt">Table of n, a(n) for n = 1..14</a>
%H F. Harary et al., <a href="http://cobweb.cs.uga.edu/~rwr/publications/binary.pdf">Counting free binary trees admitting a given height</a>, J. Combin. Inform. System Sci. 17 (1992), no. 1-2, 175--181. MR1216977 (94c:05039)
%H Harary, Frank; Palmer, Edgar M.; Robinson, Robert W., <a href="/A005588/a005588.pdf">Counting free binary trees admitting a given height</a>, J. Combin. Inform. System Sci. 17 (1992), no. 1-2, 175-181. (Annotated scanned copy)
%H E. Lemoine, <a href="http://gallica.bnf.fr/ark:/12148/bpt6k2011936/f75.image">Note sur deux nouvelles décompositions des nombres entiers</a>, Assoc. française pour l'avancement des sciences. Vol. 29, Tome 2, pp. 72-74, 1900.
%H Sergey Zimnitskiy, <a href="/A006894/a006894.jpg">Illustration of initial terms of A006894 and A002658</a>
%H <a href="/index/Cor#core">Index entries for "core" sequences</a>
%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F Partial sums of A002658; a(n+1) = a(n)(a(n)+1)/2 + 1 (from Marc LeBrun).
%F 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
%F a(n) ~ 2 * c^(2^n), where c = 1.11625303268733048891316684155278646623772830100986583494311015252450055518... . - _Vaclav Kotesovec_, May 21 2015
%e x + 2*x^2 + 4*x^3 + 11*x^4 + 67*x^5 + 2279*x^6 + 2598061*x^7 + 3374961778892*x^8 + ...
%p 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) ];
%p 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
%p 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
%t NestList[(#(#+1))/2+1&,1,12] (* _Harvey P. Dale_, May 24 2011 *)
%o (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
%o (PARI) {a(n) = if( n<1, 0, 1 + binomial( 1 + a(n-1), 2))} /* _Michael Somos_, Jan 01 2013 */
%o (Python)
%o from functools import lru_cache
%o @lru_cache(maxsize=None)
%o def A006894(n): return ((m:=A006894(n-1))*(m+1)>>1)+1 if n else 0 # _Chai Wah Wu_, Feb 20 2023
%Y Row sums of A036602.
%K nonn,easy,core,nice
%O 1,2
%A _Jeffrey Shallit_ and _N. J. A. Sloane_
|
