A143897 -id:A143897 - cp's OEIS frontend

A008466 a(n) = 2^n - Fibonacci(n+2).

0, 0, 1, 3, 8, 19, 43, 94, 201, 423, 880, 1815, 3719, 7582, 15397, 31171, 62952, 126891, 255379, 513342, 1030865, 2068495, 4147936, 8313583, 16655823, 33358014, 66791053, 133703499, 267603416, 535524643, 1071563515, 2143959070, 4289264409, 8580707127

Offset: 0

N. J. A. Sloane, I. J. Kennedy, Eric W. Weisstein

Toss a fair coin n times; a(n) is number of possible outcomes having a run of 2 or more heads.
Also the number of binary words of length n with at least two neighboring 1 digits. For example, a(4)=8 because 8 binary words of length 4 have two or more neighboring 1 digits: 0011, 0110, 0111, 1011, 1100, 1101, 1110, 1111 (cf. A143291). - Alois P. Heinz, Jul 18 2008
Equivalently, number of solutions (x_1, ..., x_n) to the equation x_1*x_2 + x_2*x_3 + x_3*x_4 + ... + x_{n-1}*x_n = 1 in base-2 lunar arithmetic. - N. J. A. Sloane, Apr 23 2011
Row sums of triangle A153281 = (1, 3, 8, 19, 43, ...). - Gary W. Adamson, Dec 23 2008
a(n-1) is the number of compositions of n with at least one part >= 3. - Joerg Arndt, Aug 06 2012
One less than the cardinality of the set of possible numbers of (leaf-) nodes of AVL trees with height n (cf. A143897, A217298). a(3) = 4-1, the set of possible numbers of (leaf-) nodes of AVL trees with height 3 is {5,6,7,8}. - Alois P. Heinz, Mar 20 2013
a(n) is the number of binary words of length n such that some prefix contains three more 1's than 0's or two more 0's than 1's. a(4) = 8 because we have: {0,0,0,0}, {0,0,0,1}, {0,0,1,0}, {0,0,1,1}, {0,1,0,0}, {1,0,0,0}, {1,1,1,0}, {1,1,1,1}. - Geoffrey Critzer, Dec 30 2013
With offset 0: antidiagonal sums of P(j,n) array of j-th partial sums of Fibonacci numbers. - Luciano Ancora, Apr 26 2015

			From _Gus Wiseman_, Jun 25 2020: (Start)
The a(2) = 1 through a(5) = 19 compositions of n + 1 with at least one part >= 3 are:
  (3)  (4)    (5)      (6)
       (1,3)  (1,4)    (1,5)
       (3,1)  (2,3)    (2,4)
              (3,2)    (3,3)
              (4,1)    (4,2)
              (1,1,3)  (5,1)
              (1,3,1)  (1,1,4)
              (3,1,1)  (1,2,3)
                       (1,3,2)
                       (1,4,1)
                       (2,1,3)
                       (2,3,1)
                       (3,1,2)
                       (3,2,1)
                       (4,1,1)
                       (1,1,1,3)
                       (1,1,3,1)
                       (1,3,1,1)
                       (3,1,1,1)
(End)

W. Feller, An Introduction to Probability Theory and Its Applications, Vol. 1, 2nd ed. New York: Wiley, p. 300, 1968.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 14, Exercise 1.

Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 301 terms from T. D. Noe)
D. Applegate, M. LeBrun and N. J. A. Sloane, Dismal Arithmetic, arXiv:1107.1130 [math.NT], 2001. [Note: we have now changed the name from "dismal arithmetic" to "lunar arithmetic" - the old name was too depressing]
Simon Cowell, A Formula for the Reliability of a d-dimensional Consecutive-k-out-of-n:F System, arXiv preprint arXiv:1506.03580 [math.CO], 2015.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1020
T. Langley, J. Liese, and J. Remmel, Generating Functions for Wilf Equivalence Under Generalized Factor Order, J. Int. Seq. 14 (2011) # 11.4.2.
B. E. Merkel, Probabilities of Consecutive Events in Coin Flipping, Master's Thesis, Univ. Cincinatti, May 11 2011.
D. J. Persico and H. C. Friedman, Another Coin Tossing Problem, Problem 62-6, SIAM Review, 6 (1964), 313-314.
Eric Weisstein's World of Mathematics, Run.
Index entries for sequences related to dismal (or lunar) arithmetic
Index entries for linear recurrences with constant coefficients, signature (3,-1,-2).

Cf. A050227, A050231, A050232, A050233, A056986.
Cf. A153281, A186244 (ternary words), A335457, A335458, A335516.
The non-contiguous version is A335455.
Row 2 of A340156. Column 3 of A109435.

[2^n-Fibonacci(n+2): n in [0..40]]; // Vincenzo Librandi, Apr 27 2015

a:= n-> (<<3|1|0>, <-1|0|1>, <-2|0|0>>^n)[1, 3]:
seq(a(n), n=0..50); # Alois P. Heinz, Jul 18 2008
# second Maple program:
with(combinat): F:=fibonacci; f:=n->add(2^(n-1-i)*F(i),i=0..n-1); [seq(f(n),n=0..50)]; # N. J. A. Sloane, Mar 31 2014

Table[2^n-Fibonacci[n+2],{n,0,20}] (* Vladimir Joseph Stephan Orlovsky, Jul 22 2008 *)
MMM = 30;
For[ M=2, M <= MMM, M++,
vlist = Array[x, M];
cl[i_] := And[ x[i], x[i+1] ];
cl2 = False; For [ i=1, i <= M-1, i++, cl2 = Or[cl2, cl[i]] ];
R[M] = SatisfiabilityCount[ cl2, vlist ] ]
Table[ R[M], {M,2,MMM}]
(* Find Boolean values of variables that satisfy the formula x1 x2 + x2 x3 + ... + xn-1 xn = 1; N. J. A. Sloane, Apr 23 2011 *)
LinearRecurrence[{3,-1,-2},{0,0,1},40] (* Harvey P. Dale, Aug 09 2013 *)
nn=33; a=1/(1-2x); b=1/(1-2x^2-x^4-x^6/(1-x^2));
CoefficientList[Series[b(a x^3/(1-x^2)+x^2a),{x,0,nn}],x] (* Geoffrey Critzer, Dec 30 2013 *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n+1],Max@@#>2&]],{n,0,10}] (* Gus Wiseman, Jun 25 2020 *)

a(n) = 2^n-fibonacci(n+2) \\ Charles R Greathouse IV, Feb 03 2014

def A008466(n): return 2^n - fibonacci(n+2) # G. C. Greubel, Apr 23 2025

a(1)=0, a(2)=1, a(3)=3, a(n) = 3*a(n-1) - a(n-2) - 2*a(n-3). - Miklos Kristof, Nov 24 2003
G.f.: x^2/((1-2*x)*(1-x-x^2)). - Paul Barry, Feb 16 2004
From Paul Barry, May 19 2004: (Start)
Convolution of Fibonacci(n) and (2^n - 0^n)/2.
a(n) = Sum_{k=0..n} (2^k-0^k)*Fibonacci(n-k)/2.
a(n+1) = Sum_{k=0..n} Fibonacci(k)*2^(n-k).
a(n) = 2^n*Sum_{k=0..n} Fibonacci(k)/2^k. (End)
a(n) = a(n-1) + a(n-2) + 2^(n-2). - Jon Stadler (jstadler(AT)capital.edu), Aug 21 2006
a(n) = 2*a(n-1) + Fibonacci(n-1). - Thomas M. Green, Aug 21 2007
a(n) = term (1,3) in the 3 X 3 matrix [3,1,0; -1,0,1; -2,0,0]^n. - Alois P. Heinz, Jul 18 2008
a(n) = 2*a(n-1) - a(n-3) + 2^(n-3). - Carmine Suriano, Mar 08 2011

A217298 Triangle read by columns: T(n,k) = number of AVL trees of height n with k (leaf-) nodes, k>=1, A029837(k)<=n<A072649(k).

Original entry on oeis.org

1, 1, 2, 1, 4, 6, 4, 1, 16, 32, 44, 60, 70, 56, 128, 28, 448, 8, 864, 1, 1552, 2720, 4288, 6312, 9004, 11992, 4096, 14372, 22528, 15400, 67584, 14630, 159744, 11968, 334080, 8104, 644992, 4376, 1195008, 1820, 2158912, 560, 3811904, 120, 6617184, 16, 11307904

Offset: 1

Alois P. Heinz, Mar 17 2013

			There are 2 AVL trees of height 2 with 3 (leaf-) nodes:
       o       o
      / \     / \
     o   N   N   o
    / \         / \
   N   N       N   N
Triangle begins:
  1
  . 1
  . . 2 1
  . . . . 4 6 4  1
  . . . . . . . 16 32 44 60 70  56  28   8    1
  . . . . . . .  .  .  .  .  . 128 448 864 1552 2720 ...

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 239, Eq 79, A_5.
D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 6.2.3 (7) and (8).

Alois P. Heinz, Columns k = 1..1500, flattened
Ralf Hinze, Functional Pearls: Purely functional 1-2 brother trees, Journal of Functional Programming, 19(6):633-644, 2009, DOI: 10.1017/S0956796809007333.
R. C. Richards, Shape distribution of height-balanced trees, Info. Proc. Lett., 17 (1983), 17-20.
Wikipedia, AVL tree
Index entries for sequences related to rooted trees

Triangle read by rows gives: A143897.
Row sums give: A029758.
Column sums give: A006265.
First elements of rows give: A174677.
First, last elements of columns give: A217299, A217300.
Row lengths give: 1+A008466(n).
Column heights give: A217710(k).
Cf. A029837, A072649.

A006265 Number of shapes of height-balanced AVL trees with n nodes.

Original entry on oeis.org

1, 1, 2, 1, 4, 6, 4, 17, 32, 44, 60, 70, 184, 476, 872, 1553, 2720, 4288, 6312, 9004, 16088, 36900, 82984, 174374, 346048, 653096, 1199384, 2160732, 3812464, 6617304, 11307920, 18978577, 31327104, 51931296, 90400704, 170054336, 341729616, 711634072, 1491256624

Offset: 1

N. J. A. Sloane

nonn

An AVL tree is a complete ordered binary rooted tree where at any node, the height of both subtrees are within 1 of each other.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
This is the limit of A_k as k->inf, see F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 239, Eq 79.

Alois P. Heinz, Table of n, a(n) for n = 1..1000
Ricardo A. Baeza-Yates, Height balance distribution of search trees, Preprint. (Annotated scanned copy)
Ricardo A. Baeza-Yates, Height balance distribution of search trees, Information Processing Letters 39.6 (1991): 317-324.
S. Giraudo, Intervals of balanced binary trees in the Tamari lattice, arXiv preprint arXiv:1107.3472 [math.CO], 2011 and Theor Comput. Sci. 420, 1-27 (2012)
R. C. Richards, Shape distribution of height-balanced trees, Info. Proc. Lett., 17 (1983), 17-20.
Index entries for sequences related to trees
Index entries for sequences related to rooted trees

Cf. A036662, A134306.

Column sums of A143897, A217298. - Alois P. Heinz, Mar 18 2013

a:= proc(n::posint) local B; B:= proc(x,y,d,a,b) if a+b<=d then x+B(x^2+2*x*y, x, d, a+b, a) else x fi end; coeff(B(z,0,n,1,1),z,n) end: seq(a(n), n=1..40);  # Alois P. Heinz, Aug 10 2008

a[n_] := Module[{B}, B[x_, y_, d_, a_, b_] := If[a+b <= d, x+B[x^2+2*x*y, x, d, a+b, a], x]; Coefficient[B[z, 0, n, 1, 1], z, n]]; Table[a[n], {n, 1, 39}] (* Jean-François Alcover, Mar 03 2014, after Alois P. Heinz *)

G.f.: A(x) = B(x,0) where B(x,y) satisfies B(x,y) = x + B(x^2+2xy,x).

More terms, formula and comment from Christian G. Bower, Dec 15 1999

A217710 Cardinality of the set of possible heights of AVL trees with n (leaf-) nodes.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 2, 2, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3

Offset: 1

Alois P. Heinz, Mar 20 2013

nonn

a(n) increases at Fibonacci numbers (A000045) and decreases at powers of 2 plus 1 (A000051) for n>=8.

a(n) is the height (number of nonzero elements) of column n of triangles A143897, A217298.

			a(8) = 2: We have 1 AVL tree with n=8 (leaf-) nodes of height 3 and 16 of height 4 (8 is both Fibonacci number and power of 2):
           o              o
         /   \          /   \
       o       o      o       o
      / \     / )    / \     / \
     o   o   o  N   o   o   o   o
    / ) ( ) ( )    ( ) ( ) ( ) ( )
   o  N N N N N    N N N N N N N N
  ( )
  N N

Alois P. Heinz, Table of n, a(n) for n = 1..50000
Wikipedia, AVL tree
Index entries for sequences related to rooted trees

Cf. A000045, A000051, A000079, A029837, A072649, A143897, A217298.

a:= proc(n) local j, p; for j from ilog[(1+sqrt(5))/2](n)
       while combinat[fibonacci](j+1)<=n do od;
       p:= ilog2(n);
       j-p-`if`(2^p issqr(t+4) or issqr(t-4))(5*n^2), 1, 0)-
     `if`((t-> is(2^ilog2(t)=t))(n-1), 1, 0))
    end:
seq(a(n), n=1..120);  # Alois P. Heinz, Aug 14 2021

a[n_] := Module[{j, p}, For[j = Log[(1+Sqrt[5])/2, n] // Floor, Fibonacci[j+1] <= n, j++]; p = Log[2, n] // Floor; j-p-If[2^p < n, 2, 1]]; Table[a[n], {n, 1, 120}] (* Jean-François Alcover, Dec 30 2013, translated from Maple *)

a(n) = A072649(n) - A029837(n).

A029758 Number of AVL trees of height n.

Original entry on oeis.org

1, 1, 3, 15, 315, 108675, 11878720875, 141106591466142946875, 19911070158545297149037891328865229296875, 396450714858513044552818188364610837019719636049876979456842033610756600341796875

Offset: 0

Don Knuth

			G.f. = 1 + x + 3*x^2 + 15*x^3 + 315*x^4 + 108675*x^5 + 11878720875*x^6 + ...

D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 6.2.3 (7) and (8).

Alois P. Heinz, Table of n, a(n) for n = 0..12
Index entries for sequences related to rooted trees

Cf. A029846.

Row sums of A143897. - Alois P. Heinz, Jun 01 2009

A029758 := proc(n) option remember; if n <= 1 then RETURN(1); else A029758(n-1)^2+2*A029758(n-1)*A029758(n-2); fi; end;

a[0] = a[1] = 1; a[n_] := a[n] = a[n-1]^2 + 2*a[n-1]*a[n-2]; Table[a[n], {n, 0, 9}] (* Jean-François Alcover, Feb 13 2015 *)

{a(n) = if( n<2, n>=0, a(n-1) * (a(n-1) + 2*a(n-2)))}; /* Michael Somos, Feb 07 2004 */

a(n+1) = a(n)^2 + 2*a(n)*a(n-1).

According to Knuth (p. 715), a(n) ~ c^(2^n), where c = 1.4368728483944618758004279843355486292481149448324679771230546290458819902268... - Vaclav Kotesovec, Dec 17 2018

More terms from N. J. A. Sloane.

A217299 Number of height minimal AVL trees with n (leaf-) nodes.

Original entry on oeis.org

1, 1, 2, 1, 4, 6, 4, 1, 32, 44, 60, 70, 56, 28, 8, 1, 2720, 4288, 6312, 9004, 11992, 14372, 15400, 14630, 11968, 8104, 4376, 1820, 560, 120, 16, 1, 31327104, 50882720, 80963520, 125489856, 188637520, 273984664, 383305008, 515461260, 665277632, 822361736

Offset: 1

Alois P. Heinz, Mar 17 2013

Alois P. Heinz, Table of n, a(n) for n = 1..1024
Wikipedia, AVL tree
Index entries for sequences related to rooted trees

Cf. A217300.

a(n) = A143897(A029837(n),n) = A217298(A029837(n),n).

A217300 Number of height maximal AVL trees with n (leaf-) nodes.

Original entry on oeis.org

1, 1, 2, 1, 4, 6, 4, 16, 32, 44, 60, 70, 128, 448, 864, 1552, 2720, 4288, 6312, 9004, 4096, 22528, 67584, 159744, 334080, 644992, 1195008, 2158912, 3811904, 6617184, 11307904, 18978576, 31327104, 1048576, 9437184, 44564480, 153092096, 437649408, 1107951616

Offset: 1

Alois P. Heinz, Mar 17 2013

Alois P. Heinz, Table of n, a(n) for n = 1..1024
Wikipedia, AVL tree
Index entries for sequences related to rooted trees

Cf. A217299.

a(n) = A143897(A072649(n)-1,n) = A217298(A072649(n)-1,n).

A036662 Shapes of height-balanced AVL trees of height at most 5 with n nodes.

Original entry on oeis.org

0, 1, 1, 2, 1, 4, 6, 4, 17, 32, 44, 60, 70, 184, 476, 872, 1553, 2720, 4288, 6312, 9004, 11992, 14372, 15400, 14630, 11968, 8104, 4376, 1820, 560, 120, 16, 1

Offset: 0

N. J. A. Sloane

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 239, Eq 79, A_5.

R. C. Richards, Shape distribution of height-balanced trees, Info. Proc. Lett., 17 (1983), 17-20.
Index entries for sequences related to rooted trees

Cf. A006265, A143897.

a:= proc(n) local B,z; B:= proc(x,y,d) if d>=1 then x+B(x^2+2*x*y, x,d-1) else x fi end; coeff(B(z,0,5), z,n) end: seq(a(n), n=0..32); # Alois P. Heinz, Aug 27 2008

a[n_] := Module[{B, z}, B[x_, y_, d_] := If[d >= 1, x+B[x^2+2*x*y, x, d-1], x];  Coefficient[B[z, 0, 5], z, n]]; Table[a[n], {n, 0, 32}] (* Jean-François Alcover, Feb 24 2015, after Alois P. Heinz *)

a(n) = Sum_{h=0..5} A143897(h,n). - Alois P. Heinz, Mar 17 2013

A134306 Number of shapes of height-balanced AVL trees of height at most 6 with n nodes.

Original entry on oeis.org

0, 1, 1, 2, 1, 4, 6, 4, 17, 32, 44, 60, 70, 184, 476, 872, 1553, 2720, 4288, 6312, 9004, 16088, 36900, 82984, 174374, 346048, 653096, 1199384, 2160732, 3812464, 6617304, 11307920, 18978577, 31327104, 50882720, 80963520, 125489856, 188637520, 273984664

Offset: 0

Alois P. Heinz, Aug 27 2008

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 239, Eq 79, A_5.

Alois P. Heinz, Table of n, a(n) for n = 0..64
R. C. Richards, Shape distribution of height-balanced trees, Info. Proc. Lett., 17 (1983), 17-20.
Wikipedia, AVL tree
Index entries for sequences related to rooted trees

Cf. A006265, A036662.

a:= proc(n) local B,z; B:= proc(x,y,d) if d>=1 then x+B(x^2+2*x*y, x,d-1) else x fi end; coeff(B(z,0,6), z,n) end: seq(a(n), n=0..64);

a[n_] := Module[{B, z}, B[x_, y_, d_] := B[x, y, d] = If[d >= 1, x+B[x^2+2*x*y, x, d-1], x]; Coefficient[B[z, 0, 6], z, n]]; Table[a[n], {n, 0, 64}] (* Jean-François Alcover, Mar 05 2014, after Alois P. Heinz *)

a(n) = Sum_{h=0..6} A143897(h,n).

A174677 a(n) = 2a(n-1)a(n-2) with a(0)=1 and a(1)=1.

Original entry on oeis.org

1, 1, 2, 4, 16, 128, 4096, 1048576, 8589934592, 18014398509481984, 309485009821345068724781056, 11150372599265311570767859136324180752990208

Offset: 0

Giovanni Teofilatto, Mar 26 2010

a(n) is the number of node minimal AVL trees of height n. - Alois P. Heinz, Mar 13 2013

Vincenzo Librandi, Table of n, a(n) for n = 0..17

Cf. A000045, A000301, A143897, A174666, A217298.

[2^(Fibonacci(n+1)-1): n in [0..10]]; // Vincenzo Librandi, Apr 24 2011

2^(Fibonacci[Range[15]] -1) (* Vladimir Joseph Stephan Orlovsky, Apr 19 2011 *)
Join[{1}, RecurrenceTable[{a[1]==1,a[2]==2,a[n]==2a[n-1]a[n-2]},a[n],{n, 12}]] (* Harvey P. Dale, Jul 07 2011 *)

[2^(fibonacci(n+1) -1) for n in range(13)] # G. C. Greubel, Jul 30 2024

a(n) = 2^(Fibonacci(n+1) - 1).

a(n) = 1/2 * A000301(n+1).

Formula index corrected by R. J. Mathar, Mar 30 2010

a(0)=1 prepended and name edited by Alois P. Heinz, Jul 05 2021

cp's OEIS Frontend

A008466 a(n) = 2^n - Fibonacci(n+2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

SageMath

Formula

A217298 Triangle read by columns: T(n,k) = number of AVL trees of height n with k (leaf-) nodes, k>=1, A029837(k)<=n<A072649(k).

Views

Author

Keywords

Examples

References

Links

Crossrefs

A006265 Number of shapes of height-balanced AVL trees with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A217710 Cardinality of the set of possible heights of AVL trees with n (leaf-) nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A029758 Number of AVL trees of height n.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A217299 Number of height minimal AVL trees with n (leaf-) nodes.

Views

Author

Keywords

Links

Crossrefs

Formula

A217300 Number of height maximal AVL trees with n (leaf-) nodes.

Views

Author

Keywords

Links

Crossrefs

Formula

A036662 Shapes of height-balanced AVL trees of height at most 5 with n nodes.

Views

A174677 a(n) = 2a(n-1)a(n-2) with a(0)=1 and a(1)=1.