A001699 -id:A001699 - cp's OEIS frontend

A073345 Table T(n,k), read by ascending antidiagonals, giving the number of rooted plane binary trees of size n and height k.

1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 6, 8, 0, 0, 0, 0, 0, 0, 0, 4, 20, 0, 0, 0, 0, 0, 0, 0, 0, 1, 40, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 68, 56, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 94, 152, 32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 114, 376, 144, 0, 0, 0, 0, 0, 0, 0

Offset: 0

Antti Karttunen, Jul 31 2002

			The top-left corner of this square array is
  1 0 0 0 0 0 0 0 0 ...
  0 1 0 0 0 0 0 0 0 ...
  0 0 2 1 0 0 0 0 0 ...
  0 0 0 4 6 6 4 1 0 ...
  0 0 0 0 8 20 40 68 94 ...
E.g. we have A000108(3) = 5 binary trees built from 3 non-leaf (i.e. branching) nodes:
_______________________________3
___\/__\/____\/__\/____________2
__\/____\/__\/____\/____\/_\/__1
_\/____\/____\/____\/____\./___0
The first four have height 3 and the last one has height 2, thus T(3,3) = 4, T(3,2) = 1 and T(3,any other value of k) = 0.

Luo Jian-Jin, Catalan numbers in the history of mathematics in China, in Combinatorics and Graph Theory, (Yap, Ku, Lloyd, Wang, Editors), World Scientific, River Edge, NJ, 1995.

Alois P. Heinz, Antidiagonals n = 0..200, flattened
Henry Bottomley and Antti Karttunen, Notes concerning diagonals of the square arrays A073345 and A073346.
Andrew Odlyzko, Analytic methods in asymptotic enumeration.

Variant: A073346. Column sums: A000108. Row sums: A001699.
Diagonals: A073345(n, n) = A011782(n), A073345(n+3, n+2) = A014480(n), A073345(n+2, n) = A073773(n), A073345(n+3, n) = A073774(n) - Henry Bottomley and AK, see the attached notes.
A073429 gives the upper triangular region of this array. Cf. also A065329, A001263.

A073345 := n -> A073345bi(A025581(n), A002262(n));
A073345bi := proc(n,k) option remember; local i,j; if(0 = n) then if(0 = k) then RETURN(1); else RETURN(0); fi; fi; if(0 = k) then RETURN(0); fi; 2 * add(A073345bi(n-i-1,k-1) * add(A073345bi(i,j),j=0..(k-1)),i=0..floor((n-1)/2)) + 2 * add(A073345bi(n-i-1,k-1) * add(A073345bi(i,j),j=0..(k-2)),i=(floor((n-1)/2)+1)..(n-1)) - (`mod`(n,2))*(A073345bi(floor((n-1)/2),k-1)^2); end;
A025581 := n -> binomial(1+floor((1/2)+sqrt(2*(1+n))),2) - (n+1);
A002262 := n -> n - binomial(floor((1/2)+sqrt(2*(1+n))),2);

a[0, 0] = 1; a[n_, k_]/;k2^n-1 := 0; a[n_, k_]/;1 <= n <= k <= 2^n-1 := a[n, k] = Sum[a[n-1, k-1-i](2Sum[ a[j, i], {j, 0, n-2}]+a[n-1, i]), {i, 0, k-1}]; Table[a[n, k], {n, 0, 9}, {k, 0, 9}]
(* or *) a[0] = 0; a[1] = 1; a[n_]/;n>=2 := a[n] = Expand[1 + x a[n-1]^2]; gfT[n_] := a[n]-a[n-1]; Map[CoefficientList[ #, x, 8]&, Table[gfT[n], {n, 9}]/.{x^i_/;i>=9 ->0}] (Callan)

(See the Maple code below. Is there a nicer formula?)
This table was known to the Chinese mathematician Ming An-Tu, who gave the following recurrence in the 1730s. a(0, 0) = 1, a(n, k) = Sum[a(n-1, k-1-i)( 2*Sum[ a(j, i), {j, 0, n-2}]+a(n-1, i) ), {i, 0, k-1}]. - David Callan, Aug 17 2004
The generating function for row n, T_n(x):=Sum[T(n, k)x^k, k>=0], is given by T_n = a(n)-a(n-1) where a(n) is defined by the recurrence a(0)=0, a(1)=1, a(n) = 1 + x a(n-1)^2 for n>=2. - David Callan, Oct 08 2005

A056207 Number of binary trees of height <= n.

Original entry on oeis.org

3, 24, 675, 458328, 210066388899, 44127887745906175987800, 1947270476915296449559703445493848930452791203, 3791862310265926082868235028027893277370233152247388584761734150717768254410341175325352024

Offset: 1

Todd K. Moon (Todd.Moon(AT)ece.usu.edu), Aug 02 2000

Todd K. Moon, "Enumerations of binary trees, types of trees and the number of reversible variable length codes," submitted to Discrete Applied Mathematics, 2000.

Index entries for sequences of form a(n+1)=a(n)^2 + ...

Cf. A001699, A002449, A003095.

from itertools import accumulate
def f(anm1, _): return anm1**2 + 4*anm1 + 3
def aupton(terms): return list(accumulate([3]*terms, f))
print(aupton(8)) # Michael S. Branicky, Mar 24 2021

a(n) = d(n) + a(n-1), d(n) = A001699(n) is the number of binary trees of depth exactly n.

a(n) = A003095(n+2) - 2 = A004019(n+1) - 1 = a(n-1)^2 + 4*a(n-1) + 3.

More terms from Henry Bottomley, Jul 09 2001

A213437 Nonlinear recurrence: a(n) = a(n-1) + (a(n-1)+1)*Product_{j=1..n-2} a(j).

Original entry on oeis.org

1, 3, 7, 31, 703, 459007, 210066847231, 44127887746116242376703, 1947270476915296449559747573381594836628779007

Offset: 1

N. J. A. Sloane, Jun 11 2012

nonn

This sequence was going to be included in the Aho-Sloane paper, but was omitted from the published version.

It appears that the sequence becomes periodic mod 10^k for any k, with period 3. The last digits are (1,3,7) repeated. Modulo 10^5 the sequence enters the cycle (56703, 79007, 23231) after the first 10 terms. - M. F. Hasler, Jul 23 2012. See also A214635, A214636.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

A. V. Aho and N. J. A. Sloane, Some doubly exponential sequences, Fibonacci Quarterly, Vol. 11, No. 4 (1973), pp. 429-437. [Includes many similar sequences, although not this one.]
A. V. Aho and N. J. A. Sloane, Some doubly exponential sequences, Fibonacci Quarterly, Vol. 11, No. 4 (1973), pp. 429-437 (original plus references that F.Q. forgot to include - see last page!)

Cf. A076949, A214635, A214636, A003095, A001699.

A213437 := proc(n)
        if n = 1 then 1;
        else procname(n-1)+(1+procname(n-1))*mul(procname(j),j=1..n-2);
        end if;
end proc: # R. J. Mathar, Jul 23 2012

RecurrenceTable[{a[n] == a[n-1]+(a[n-1]+1)*(a[n-1]-a[n-2])*a[n-2]/(a[n-2]+1),a[1]==1,a[2]==3},a,{n,1,10}] (* Vaclav Kotesovec, May 06 2015 *)

a=[1];for(n=1,11,a=concat(a, a[n] + (a[n]+1) * prod(k=1,n-1, a[k] )));a \\ - M. F. Hasler, Jul 23 2012

a(n) = a(n-1)+(a(n-1)+1)*(a(n-1)-a(n-2))*a(n-2)/(a(n-2)+1). - Johan de Ruiter, Jul 23 2012
a(2+3k) = 9007 (mod 10^4) for all k>0. - M. F. Hasler, Jul 23 2012
a(n) ~ c^(2^n), where c = A076949 = 1.2259024435287485386279474959130085213212293209696612823177009... . - Vaclav Kotesovec, May 06 2015
a(n) = A001699(n)/A001699(n-1); a(n+1) - a(n) = A001699(n) + A001699(n-1); a(n) = A003095(n) + A003095(n-1). - Peter Bala, Feb 03 2017

Definition recovered by Johan de Ruiter, Jul 23 2012

A335919 Number T(n,k) of binary search trees of height k having n internal nodes; triangle T(n,k), n>=0, max(0,floor(log_2(n))+1)<=k<=n, read by rows.

Original entry on oeis.org

1, 1, 2, 1, 4, 6, 8, 6, 20, 16, 4, 40, 56, 32, 1, 68, 152, 144, 64, 94, 376, 480, 352, 128, 114, 844, 1440, 1376, 832, 256, 116, 1744, 4056, 4736, 3712, 1920, 512, 94, 3340, 10856, 15248, 14272, 9600, 4352, 1024, 60, 5976, 27672, 47104, 50784, 40576, 24064

Offset: 0

Alois P. Heinz, Jun 29 2020

Empty external nodes are counted in determining the height of a search tree.

T(n,k) is defined for n,k >= 0. The triangle contains only the positive terms. Terms not shown are zero.

			Triangle T(n,k) begins:
  1;
     1;
        2;
        1, 4;
           6,   8;
           6,  20,   16;
           4,  40,   56,   32;
           1,  68,  152,  144,   64;
               94,  376,  480,  352,  128;
              114,  844, 1440, 1376,  832,  256;
              116, 1744, 4056, 4736, 3712, 1920, 512;
  ...

Alois P. Heinz, Rows n = 0..200, flattened
Wikipedia, Binary search tree
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Row sums give A000108.
Column sums give A001699.
Main diagonal gives A011782.
T(n+3,n+2) gives A014480.
T(n,max(0,A000523(n)+1)) = A328349(n).
Cf. A073345, A073429 (another version with 0's), A076615, A195581, A244108, A335920 (the same read by columns), A335921, A335922.

g:= n-> `if`(n=0, 0, ilog2(n)+1):
b:= proc(n, h) option remember; `if`(n=0, 1, `if`(n<2^h,
      add(b(j-1, h-1)*b(n-j, h-1), j=1..n), 0))
    end:
T:= (n, k)-> b(n, k)-`if`(k>0, b(n, k-1), 0):
seq(seq(T(n, k), k=g(n)..n), n=0..12);

g[n_] := If[n == 0, 0, Floor@Log[2, n]+1];
b[n_, h_] := b[n, h] = If[n == 0, 1, If[n < 2^h,
     Sum[b[j - 1, h - 1]*b[n - j, h - 1], {j, 1, n}], 0]];
T[n_, k_] := b[n, k] - If[k > 0, b[n, k - 1], 0];
Table[Table[T[n, k], {k, g[n], n}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Feb 08 2021, after Alois P. Heinz *)

Sum_{k=0..n} k * T(n,k) = A335921(n).

Sum_{n=k..2^k-1} n * T(n,k) = A335922(k).

A335920 Number T(n,k) of binary search trees of height k having n internal nodes; triangle T(n,k), k>=0, k<=n<=2^k-1, read by columns.

Original entry on oeis.org

1, 1, 2, 1, 4, 6, 6, 4, 1, 8, 20, 40, 68, 94, 114, 116, 94, 60, 28, 8, 1, 16, 56, 152, 376, 844, 1744, 3340, 5976, 10040, 15856, 23460, 32398, 41658, 49700, 54746, 55308, 50788, 41944, 30782, 19788, 10948, 5096, 1932, 568, 120, 16, 1, 32, 144, 480, 1440, 4056

Offset: 0

Alois P. Heinz, Jun 29 2020

Empty external nodes are counted in determining the height of a search tree.

T(n,k) is defined for n,k >= 0. The triangle contains only the positive terms. Terms not shown are zero.

			Triangle T(n,k) begins:
  1;
     1;
        2;
        1, 4;
           6,   8;
           6,  20,   16;
           4,  40,   56,   32;
           1,  68,  152,  144,   64;
               94,  376,  480,  352,  128;
              114,  844, 1440, 1376,  832,  256;
              116, 1744, 4056, 4736, 3712, 1920, 512;
  ...

Alois P. Heinz, Columns k = 0..10, flattened
Wikipedia, Binary search tree
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Row sums give A000108.
Column sums give A001699.
Main diagonal gives A011782.
T(n+3,n+2) gives A014480.
T(n,max(0,A000523(n)+1)) = A328349(n).
Cf. A073345, A076615, A195581, A244108, A335919 (the same read by rows), A335921, A335922.

b:= proc(n, h) option remember; `if`(n=0, 1, `if`(n<2^h,
      add(b(j-1, h-1)*b(n-j, h-1), j=1..n), 0))
    end:
T:= (n, k)-> b(n, k)-`if`(k>0, b(n, k-1), 0):
seq(seq(T(n, k), n=k..2^k-1), k=0..6);

b[n_, h_] := b[n, h] = If[n == 0, 1, If[n < 2^h,
     Sum[b[j - 1, h - 1]*b[n - j, h - 1], {j, 1, n}], 0]];
T[n_, k_] := b[n, k] - If[k > 0, b[n, k - 1], 0];
Table[Table[T[n, k], {n, k, 2^k - 1}], {k, 0, 6}] // Flatten (* Jean-François Alcover, Feb 08 2021, after Alois P. Heinz *)

Sum_{k=0..n} k * T(n,k) = A335921(n).

Sum_{n=k..2^k-1} n * T(n,k) = A335922(k).

A001697 a(n+1) = a(n)(a(0) + ... + a(n)).

Original entry on oeis.org

1, 1, 2, 8, 96, 10368, 108615168, 11798392572168192, 139202068568601556987554268864512, 19377215893777651167043206536157390321290709180447278572301746176

Offset: 0

N. J. A. Sloane

Number of binary trees of height n where for each node the left subtree is at least as high as the right subtree. - Franklin T. Adams-Watters, Feb 08 2007
The next term (a(10)) has 129 digits. - Harvey P. Dale, Jan 24 2016
Number of plane trees where the root has exactly n children and the i-th child of any node has at most i-1 children. - David Eppstein, Dec 18 2021

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

John Cerkan, Table of n, a(n) for n = 0..12
A. V. Aho and N. J. A. Sloane, Some doubly exponential sequences, Fibonacci Quarterly, Vol. 11, No. 4 (1973), pp. 429-437.
A. V. Aho and N. J. A. Sloane, Some doubly exponential sequences, Fibonacci Quarterly, Vol. 11, No. 4 (1973), pp. 429-437 (original plus references that F.Q. forgot to include - see last page!)
Daniel Duverney, Takeshi Kurosawa, Iekata Shiokawa, Transformation formulas of finite sums into continued fractions, arXiv:1912.12565 [math.NT], 2019.
Index entries for sequences of form a(n+1)=a(n)^2 + ...
Index to divisibility sequences

a(n) = A039941(2*n+1); first differences of A001696 give this sequence.
Cf. A002658, A001699.
Cf. A064847.

a001697 n = a001697_list !! n
a001697_list = 1 : 1 : f [1,1] where
   f xs@(x:_) = y : f (y : xs) where y = x * sum xs
-- Reinhard Zumkeller, Apr 29 2013

[n le 2 select 1 else Self(n-1)^2*(1+1/Self(n-2)): n in [1..12]]; // Vincenzo Librandi, Nov 25 2015

a[0] = 1; a[1] = 1; a[n_] := a[n] = a[n - 1]^2*(1 + 1/a[n - 2]); Table[a[n], {n, 0, 9}]  (* Jean-François Alcover, Jul 02 2013 *)
nxt[{t_,a_}]:={t+t*a,t*a}; Transpose[NestList[nxt,{1,1},10]][[2]] (* Harvey P. Dale, Jan 24 2016 *)

a(n)=if(n<2,n >= 0,a(n-1)^2*(1+1/a(n-2)))

a(n) ~ c^(2^n), where c = 1.3352454783981919948826893254756974184778316104856161827213437094446034867599... . - Vaclav Kotesovec, May 21 2015

Additional comments from Michael Somos, May 19 2000

A083563 Number of binary rooted trees (every node has out-degree 0 or 2) with n labeled leaves (2n-1 nodes in all) and at most 2 distinct labels. Also the number of expressions in at most two variables constructible with n-1 instances of a single commutative and nonassociative binary operator.

Original entry on oeis.org

0, 2, 3, 6, 18, 54, 183, 636, 2316, 8610, 32763, 126582, 495981, 1964718, 7857939, 31682202, 128644290, 525573252, 2158930398, 8911295286, 36942107373, 153742174722, 642088530453, 2690224616904, 11304554951127, 47630390054802, 201181338802308, 851690762495448

Offset: 0

Doug McIlroy (doug(AT)cs.dartmouth.edu), Jun 12 2003

With a(1)=k, the same recurrence enumerates expressions in at most k variables. In particular, k=1 yields A001190.

			a(3)=6, enumerating the 6 expressions with 2 # operators: x#(x#x), x#(x#y), x#(y#y), y#(x#x), y#(x#y), y#(y#y).
G.f. = 2*x + 3*x^2 + 6*x^3 + 18*x^4 + 54*x^5 + 183*x^6 + 636*x^7 + ...

Andrew Howroyd, Table of n, a(n) for n = 0..500
V. P. Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. Southern Calif., 2012. - From _N. J. A. Sloane_, Dec 22 2012

Column k=2 of A319539.

Cf. A000108, A001190, A001699.

a:= proc(n) option remember; `if`(n<2, 2*n, `if`(n::odd, 0,
      (t-> t*(1-t)/2)(a(n/2)))+add(a(i)*a(n-i), i=1..n/2))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Sep 23 2018

a[n_] := a[n] = If[n < 2, 2*n, If[OddQ[n], 0, #*(1 - #)/2&[a[n/2]]]] + Sum[a[i]*a[n - i], {i, 1, n/2}];
a /@ Range[0, 30] (* Jean-François Alcover, Sep 07 2019, after Alois P. Heinz *)

{a(n) = local(A, m); if( n<0, 0, m=1; A = O(x); while( m<=n, m*=2; A = 1 - sqrt(1 - 4*x - subst(A, x, x^2))); polcoeff(A, n))};

G.f. A(x) = 1 - sqrt(1 - 4*x - A(x^2)) satisfies 0 = A(x)^2 - 2*A(x) + 4*x + A(x^2), A(0)=0. - Michael Somos, Sep 06 2003
G.f.: A(x) = 2x + (1/2)*(A(x)^2 + A(x^2)).
a(0)=0, a(1)=2, a(2*n-1) = a(1)*a(2*n-2) + a(2)*a(2*n-3) + ... + a(n-1)*a(n), a(2*n) = a(1)*a(2*n-1) + a(2)*a(2*n-2) + ... + a(n-1)*a(n+1) + a(n)*(a(n) + 1) / 2.

A065329 Square array read by antidiagonals giving number of binary trees of height n with k points on the n-th level (n,k>0).

Original entry on oeis.org

1, 0, 2, 0, 1, 8, 0, 0, 8, 80, 0, 0, 4, 144, 4160, 0, 0, 1, 168, 13888, 5632640, 0, 0, 0, 138, 31776, 36109952, 5163215782400, 0, 0, 0, 80, 54792, 158572864, 64827181969920, 2169236189050838782284800, 0, 0, 0, 32, 74624, 531441232, 552146121580800

Offset: 1

Henry Bottomley, Oct 29 2001

			Square array starts:
   1,   0,   0,   0,   0,   0,   0,   0,   0,   0, ...
   2,   1,   0,   0,   0,   0,   0,   0,   0,   0, ...
   8,   8,   4,   1,   0,   0,   0,   0,   0,   0, ...
  80, 144, 168, 138,  80,  32,   8,   1,   0,   0, ...
  ...

H. Bottomley, Illustration of initial terms

Row sums are A001699.

Cf. A073345, A073429.

T(n,k) = Sum_{2j >= k} (C(2j,k)*T(n-1,j)) starting with T(1,1) = 1 and T(1,k) = 0 if k>1.

More terms from Sean A. Irvine, Aug 30 2023

cp's OEIS Frontend

A073345 Table T(n,k), read by ascending antidiagonals, giving the number of rooted plane binary trees of size n and height k.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A056207 Number of binary trees of height <= n.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Python

Formula

Extensions

A213437 Nonlinear recurrence: a(n) = a(n-1) + (a(n-1)+1)*Product_{j=1..n-2} a(j).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A335919 Number T(n,k) of binary search trees of height k having n internal nodes; triangle T(n,k), n>=0, max(0,floor(log_2(n))+1)<=k<=n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A335920 Number T(n,k) of binary search trees of height k having n internal nodes; triangle T(n,k), k>=0, k<=n<=2^k-1, read by columns.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A001697 a(n+1) = a(n)(a(0) + ... + a(n)).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

PARI

Formula

Extensions

A083563 Number of binary rooted trees (every node has out-degree 0 or 2) with n labeled leaves (2n-1 nodes in all) and at most 2 distinct labels. Also the number of expressions in at most two variables constructible with n-1 instances of a single commutative and nonassociative binary operator.

Views

Author