A008466 -id:A008466 - cp's OEIS frontend

A104004 Expansion of (1-x) * (1+x) / ((1-2x)(1-x-x^2)).

1, 3, 7, 16, 35, 75, 158, 329, 679, 1392, 2839, 5767, 11678, 23589, 47555, 95720, 192427, 386451, 775486, 1555153, 3117071, 6245088, 12507887, 25044431, 50135230, 100345485, 200812363, 401821144, 803960099, 1608434427, 3217700894, 6436748057

Offset: 0

Creighton Dement, Feb 24 2005

A floretion-generated sequence relating to Fibonacci numbers and powers of 2. The sequence results from a particular transform of the sequence A000079*(-1)^n (powers of 2).

Floretion Algebra Multiplication Program, FAMP Code: 1jesforseq[ ( 5'i + .5i' + .5'ii' + .5e)*( + .5j' + .5'kk' + .5'ki' + .5e ) ], 1vesforseq = A000079(n+1)*(-1)^(n+1), ForType: 1A. Identity used: jesfor = jesrightfor + jesleftfor

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (3,-1,-2).

Cf. A000045, A000079, A001911, A008466, A016777, A022958, A027934, A042950, A078024, A099036, A221719.

[3*2^n-Fibonacci(n+3): n in [0..40]]; // Vincenzo Librandi, Aug 18 2017

with (combinat):a[0]:=0:a[1]:=1:for n from 2 to 50 do a[n]:=fibonacci(n-1)+2*a[n-1] od: seq(a[n], n=1..26); # Zerinvary Lajos, Mar 17 2008

LinearRecurrence[{3, -1, -2}, {1, 3, 7}, 80] (* Vincenzo Librandi, Aug 18 2017 *)
CoefficientList[Series[(1-x)(1+x)/((2x-1)(x^2+x-1)),{x,0,40}],x] (* Harvey P. Dale, Oct 12 2024 *)
A104004[n_]:= 3*2^n -Fibonacci[n+3]; (* G. C. Greubel, Jun 05 2025 *)

def A104004(n): return 3*2**n - fibonacci(n+3) # G. C. Greubel, Jun 05 2025

4*a(n) = A008466(n+3) + A027973(n) (FAMP result).
Suggestions made by Superseeker: (Start)
a(n+2) - a(n+1) - a(n) = A042950(n+1).
Coefficients of g.f.*(1-x)/(1+x) match A099036.
Coefficients of g.f./(1+x) match A027934.
Coefficients of g.f./(1-x^2) match A008466. (End)
a(n) = A101220(3, 2, n+1) - A101220(3, 2, n). - Ross La Haye, Aug 05 2005
a(n) = 3*2^n - Fibonacci(n+3) = A221719(n) + 1. - Ralf Stephan, May 20 2007, Hugo Pfoertner, Mar 06 2024
a(n) = (3*2^n - (2^(-n)*((1-sqrt(5))^n*(-2+sqrt(5)) + (1+sqrt(5))^n*(2+sqrt(5)))) / sqrt(5)). - Colin Barker, Aug 18 2017
From G. C. Greubel, Jun 05 2025: (Start)
Sum_{k=0..n} A022958(k+1)*a(n-k) = A001911(n+1).
Sum_{k=0..n} (-1)^k*A016777(k)*a(n-k) = A078024(n).
E.g.f.: 3*exp(2*x) - (2/sqrt(5))*exp(x/2)*( 2*sinh(sqrt(5)*x/2) + sqrt(5)*cosh(sqrt(5)*x/2) ). (End)

A353508 Number of integer compositions of n with no ones or runs of length 1.

Original entry on oeis.org

1, 0, 0, 0, 1, 0, 2, 0, 2, 1, 4, 0, 8, 2, 11, 4, 21, 5, 37, 12, 57, 25, 104, 38, 177, 79, 292, 149, 513, 251, 876, 482, 1478, 871, 2562, 1533, 4387, 2815, 7473, 5036, 12908, 8935, 22135, 16085, 37940, 28611, 65422, 50731, 112459, 90408, 193386, 160119, 333513

Offset: 0

Gus Wiseman, May 17 2022

nonn

			The a(0) = 1 through a(14) = 11 compositions (empty columns indicated by dots, 0 is the empty composition):
  0  .  .  .  22  .  33   .  44    333  55     .  66      22333  77
                     222     2222       2233      444     33322  2255
                                        3322      2244           3344
                                        22222     3333           4433
                                                  4422           5522
                                                  22233          22244
                                                  33222          44222
                                                  222222         222233
                                                                 223322
                                                                 332222
                                                                 2222222

Alois P. Heinz, Table of n, a(n) for n = 0..1000

The version for partitions is A339222.
Compositions counted by their run-lengths:
- For run-lengths <= 1 we have A003242, ranked by A333489.
- For run-lengths = 2 we have A003242 aerated.
- For run-lengths > 1 we have A114901, ranked by A353427.
- For run-lengths <= 2 we have A128695 matching A335464.
- For run-lengths > 2 we have A353400, partitions A100405.
- For run-lengths all prime we have A353401.
- For run-lengths and parts > 2 we have A353428.
A008466 counts compositions with some part > 2.
A011782 counts compositions.
A106356 counts compositions by number of adjacent equal parts.
A261983 counts non-anti-run compositions.
A274174 counts compositions with equal parts contiguous.
Cf. A005811, A078012, A238279, A329739, A333755, A351013, A353390.

b:= proc(n,h) option remember; `if`(n=0, 1, add(
     `if`(i<>h, add(b(n-i*j, i), j=2..n/i), 0), i=2..n/2))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..60);  # Alois P. Heinz, May 17 2022

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MemberQ[#,1]&&!MemberQ[Length/@Split[#],1]&]],{n,0,15}]

a(41)-a(52) from Alois P. Heinz, May 17 2022

A050227 Triangle of number of n-tosses having a run of r or more heads for a fair coin with r=1 to n across and n=1, 2, ... down.

Original entry on oeis.org

1, 3, 1, 7, 3, 1, 15, 8, 3, 1, 31, 19, 8, 3, 1, 63, 43, 20, 8, 3, 1, 127, 94, 47, 20, 8, 3, 1, 255, 201, 107, 48, 20, 8, 3, 1, 511, 423, 238, 111, 48, 20, 8, 3, 1, 1023, 880, 520, 251, 112, 48, 20, 8, 3, 1, 2047, 1815, 1121, 558, 255, 112, 48, 20, 8, 3, 1, 4095, 3719

Offset: 1

Eric W. Weisstein

			Triangle begins:
   1;
   3,  1;
   7,  3, 1;
  15,  8, 3, 1;
  31, 19, 8, 3, 1
  ...

W. Feller, An Introduction to Probability Theory and Its Applications, Vol. 1, 2nd ed. New York: Wiley, p. 300, 1968.

T. D. Noe, Rows n=1..100 of triangle, flattened
Eric Weisstein's World of Mathematics, Coin Tossing.
Eric Weisstein's World of Mathematics, Run.

Cf. A008466, A119706 (row sums?).

Cf. A050231, A050232, A050233.

Clear[fib]; fib[n_, n_] = 1; fib[n_, k_] /; k > n = 0; fib[n_, k_] := fib[n, k] = If[k == 1, 1, Sum[fib[m, k], {m, n - k , n - 1}]]; Table[ 2^n - fib[n + k + 1 , k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jan 15 2013 *)

A175660 Eight bishops and one elephant on a 3 X 3 chessboard. a(n) = 2^(n+2) - 3*F(n+2).

Original entry on oeis.org

1, 2, 7, 17, 40, 89, 193, 410, 859, 1781, 3664, 7493, 15253, 30938, 62575, 126281, 254392, 511745, 1028281, 2064314, 4141171, 8302637, 16638112, 33329357, 66744685, 133628474, 267482023, 535328225, 1071245704, 2143444841

Offset: 0

Johannes W. Meijer, Aug 06 2010, Aug 10 2010

The a(n) represent the number of n-move routes of a fairy chess piece starting in a given corner square (m = 1, 3, 7, 9) on a 3 X 3 chessboard. This fairy chess piece behaves like a bishop on the eight side and corner squares but on the central square the bishop turns into a raging elephant, see A175654.

The sequence above corresponds to four A[5] vectors with decimal values 171, 174, 234 and 426. These vectors lead for the side squares to A000079 and for the central square to A175661 (a(n) = 2^(n+2) - 3*F(n+1)).

Harvey P. Dale, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (3, -1, -2).

Cf. A008466 (2^n-F(n+2)), A027934 (2^n-F(n+1)), A027974 (2^(n+3)-F(n+5)-F(n+3)), A074878 (3*2^n-2*F(n+2)), A142585 ((-1)^(n+1)*(2^(n-1)-F(n+1)-F(n-1))), A175661 (2^(n+2)-3*F(n+1)), A179610 (convolution of (-4)^n and F(n+1)).

nmax:=29; m:=1; A[5]:= [0,1,0,1,0,1,0,1,1]: A:=Matrix([[0,0,0,0,1,0,0,0,1], [0,0,0,1,0,1,0,0,0], [0,0,0,0,1,0,1,0,0], [0,1,0,0,0,0,0,1,0], A[5], [0,1,0,0,0,0,0,1,0], [0,0,1,0,1,0,0,0,0], [0,0,0,1,0,1,0,0,0], [1,0,0,0,1,0,0,0,0]]): for n from 0 to nmax do B(n):=A^n: a(n):= add(B(n)[m,k],k=1..9): od: seq(a(n), n=0..nmax);

Table[2^(n+2)-3Fibonacci[n+2],{n,0,30}] (* or *) LinearRecurrence[ {3,-1,-2},{1,2,7},30] (* Harvey P. Dale, Dec 28 2012 *)

G.f.: (1 - x + 2*x^2)/(1 - 3*x + x^2 + 2*x^3).
a(n) = 3*a(n-1) - a(n-2) - 2*a(n-3) with a(0)=1, a(1)=2 and a(2)=7.
a(n) = 2^(n+2) - 3*F(n+2) with F(n)=A000045(n).

A228152 Triangle read by rows: T(n,k) = maximal external path length of AVL trees of height n with k (leaf-) nodes, n>=0, fibonacci(n+2)<=k<=2^n.

Original entry on oeis.org

0, 2, 5, 8, 12, 16, 20, 24, 25, 30, 35, 40, 44, 49, 54, 59, 64, 50, 56, 62, 68, 73, 79, 85, 91, 97, 102, 107, 113, 119, 125, 131, 136, 142, 148, 154, 160, 96, 103, 110, 117, 123, 130, 137, 144, 151, 157, 163, 170, 177, 184, 191, 197, 204, 211, 218, 225, 231

Offset: 0

Herbert Eberle, Aug 13 2013

The external path length of a tree is the sum of the levels of its external nodes (i.e. leaves).

			T(2,3) = 5 because in the (two) AVL trees of height 2 with 3 (leaf-) nodes one has depth 1 and two have depth 2:
       o       o
      / \     / \
     o   1   1   o
    / \         / \
   2   2       2   2
so that the sum of depths is 5 for both trees.
Triangle begins:
  0
  . 2
  . . 5 8
  . . . . 12 16 20 24
  . . . .  .  .  . 25 30 35 40 44 49 54 59 64
  . . . .  .  .  .  .  .  .  .  . 50 56 62 68 73 79 85 91 97 102 ...
  . . . .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 96 103 ...

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

Alois P. Heinz, Rows n = 0..12, flattened
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

Row maxima give: n*2^n = A036289(n).
Row minima give: A067331(n-1) for n>0 or A166106(n+2).
Row lengths give: 1+A008466(n).
Number of AVL trees read by rows gives: A143897.
Triangle read by columns gives: A228153.
The infimum of all external path lengths of binary trees with k (leaf-) nodes is: A003314(k) for k>0.
Column maxima give: A228155(k).
Column heights give: A217710(k).
Number of AVL trees read by columns gives: A217298.

with(combinat): F:=fibonacci:
T:= proc(n, k) option remember; `if`(n<1, 0, max(seq([k+T(n-1,t)+
      T(n-1,k-t), k+T(n-1,t) +T(n-2,k-t)][], t=F(n+1)..k-1)))
    end:
seq(seq(T(n, k), k=F(n+2)..2^n), n=0..7);  # Alois P. Heinz, Aug 14 2013

maxNods = 100; Clear[T, A029837, A072649, A036289, A228155]; T[0, 1] = 0; A029837[1] = 0; A072649[1] = 1; A228155[1] = 0; For[k = 2, k <= maxNods, k++, A029837[k] = maxNods; A072649[k] = 0; A228155u = 0; For[kL = 1, kL <= Floor[k/2], kL++, For[hL = A029837[kL], hL <= A072649[kL] - 1, hL++, For[hR = Max[hL - 1, A029837[k - kL]], hR <= Min[hL + 1, A072649[k - kL] - 1], hR++, maxDepthSum = k + T[hL, kL] + T[hR, k - kL]; A228155u = Max[maxDepthSum, A228155u]; h = Max[hL, hR] + 1; If[ !IntegerQ[T[h, k]], T[h, k] = maxDepthSum, T[h, k] = Max[maxDepthSum, T[h, k]]]; A029837[k] = Min[h, A029837[k]]; If[ !IntegerQ[A036289[h]], A036289[h] = maxDepthSum, A036289[h] = Max[maxDepthSum, A036289[h]]]; A072649[k] = Max[h + 1, A072649[k]]; ]]]; A228155[k] = A228155u]; k =.; Table[T[n, k], {n, 0, maxNods}, {k, 1, maxNods}] // Flatten // Select[#, IntegerQ]& (* Jean-François Alcover, Aug 14 2013, translated and adapted from Herbert Eberle's MuPAD program *)

maxNods:=100: // max number of leaves (= external nodes)
// Triangle T for all AVL trees with <= maxNods leaves:
delete T:
// table T indexed [h, k] (h=height, k=number of leaves):
T[0, 1]:=0:
// A029837 indexed [k], min height of tree with k leaves:
A029837:=array(1..maxNods): A029837[1]:=0:
// A072649 indexed [k], 1+max height of AVL tree with k leaves:
A072649:=array(1..maxNods): A072649[1]:=1:
// A036289 indexed [h], max depthsum of all height h AVL trees:
A036289:=array(1..maxNods):
// A228155 indexed [k], max depthsum of all AVL trees with k leaves:
A228155:=array(1..maxNods): A228155[1]:=0:
for k from 2 to maxNods do:
  A029837[k]:=maxNods: // try infinity for the min height
  A072649[k]:=0:
  A228155u:=0:
  // Put together 2 AVL trees:
  for kL from 1 to floor(k/2) do:
    // kL leaves in the left tree
    for hL from A029837[kL] to A072649[kL]-1 do:
      for hR from max(hL-1, A029837[k-kL])
               to min(hL+1, A072649[k-kL]-1) do:
        // k-kL leaves in the right subtree
        maxDepthSum:=T[hL, kL]+T[hR, k-kL]+k:
        A228155u:=max(maxDepthSum, A228155u):
        h:=max(hL, hR)+1:
        if type(T[h, k]) <> DOM_INT then // T[h, k] uninit
          T[h, k]:=maxDepthSum:
        else
          T[h, k]:=max(maxDepthSum, T[h, k]):
        end_if:
        A029837[k]:=min(h, A029837[k]):
        if type(A036289[h]) <> DOM_INT then
          A036289[h]:=maxDepthSum:
        else
          A036289[h]:=max(maxDepthSum, A036289[h]):
        end_if:
        A072649[k]:=max(h+1, A072649[k]):
      end_for: // hR
    end_for: // hL
  end_for: // kL
  A228155[k]:=A228155u:
end_for: // k

A228153 Triangle read by columns: T(n,k) = maximal external path length of AVL trees of height n with k (leaf-) nodes, k>=1, A029837(k)<=n<A072649(k).

Original entry on oeis.org

0, 2, 5, 8, 12, 16, 20, 24, 25, 30, 35, 40, 44, 49, 50, 54, 56, 59, 62, 64, 68, 73, 79, 85, 91, 97, 96, 102, 103, 107, 110, 113, 117, 119, 123, 125, 130, 131, 137, 136, 144, 142, 151, 148, 157, 154, 163, 160, 170, 177, 184, 180, 191, 188, 197, 196, 204, 204

Offset: 1

Herbert Eberle, Aug 13 2013

The external path length of a tree is the sum of the levels of its external nodes (i.e. leaves).

			In the (two) AVL trees of height 2 the 3 external nodes (leaves) have once depth 1 and twice depth 2:
       o       o
      / \     / \
     o   1   1   o
    / \         / \
   2   2       2   2
so that the sum of depths is 5 for both trees.
Triangle begins:
  0
  . 2
  . . 5 8
  . . . . 12 16 20 24
  . . . .  .  .  . 25 30 35 40 44 49 54 59 64
  . . . .  .  .  .  .  .  .  .  . 50 56 62 68 73 79 85 91 97 102 ...
  . . . .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 96 103 ...

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

Alois P. Heinz, Columns k = 1..3000, flattened
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: A228152.
Row maxima give: n*2^n = A036289(n).
Row minima give: A067331(n-1) for n>0 or A166106(n+2).
Row lengths give: 1+A008466(n).
Number of AVL trees read by rows gives: A143897.
The infimum of all external path lengths of binary trees with k (leaf-) nodes is: A003314(k) for k>0.
Column maxima give: A228155(k).
Column heights give: A217710(k).
Number of AVL trees read by columns gives: A217298.

maxNods = 100; Clear[T, A029837, A072649, A036289, A228155]; T[0, 1] = 0; A029837[1] = 0; A072649[1] = 1; A228155[1] = 0; For[k = 2, k <= maxNods, k++, A029837[k] = maxNods; A072649[k] = 0; A228155u = 0; For[kL = 1, kL <= Floor[k/2], kL++, For[hL = A029837[kL], hL <= A072649[kL] - 1, hL++, For[hR = Max[hL - 1, A029837[k - kL]], hR <= Min[hL + 1, A072649[k - kL] - 1], hR++, maxDepthSum = k + T[hL, kL] + T[hR, k - kL]; A228155u = Max[maxDepthSum, A228155u]; h = Max[hL, hR] + 1; If[ !IntegerQ[T[h, k]], T[h, k] = maxDepthSum, T[h, k] = Max[maxDepthSum, T[h, k]]]; A029837[k] = Min[h, A029837[k]]; If[ !IntegerQ[A036289[h]], A036289[h] = maxDepthSum, A036289[h] = Max[maxDepthSum, A036289[h]]]; A072649[k] = Max[h + 1, A072649[k]]; ]]]; A228155[k] = A228155u]; k =.; Table[ Select[ Table[T[n, k], {n, A029837[k], A072649[k] - 1}], IntegerQ], {k, 1, maxNods}] // Flatten (* Jean-François Alcover, Aug 19 2013, translated and adapted from Herbert Eberle's MuPAD program *)

maxNods:=100: // max number of leaves (= external nodes)
// Triangle T for all AVL trees with <= maxNods leaves:
delete T:
// table T indexed [h, k] (h=height, k=number of leaves):
T[0, 1]:=0:
// A029837 indexed [k], min height of tree with k leaves:
A029837:=array(1..maxNods): A029837[1]:=0:
// A072649 indexed [k], 1+max height of AVL tree with k leaves:
A072649:=array(1..maxNods): A072649[1]:=1:
// A036289 indexed [h], max depthsum of all height h AVL trees:
A036289:=array(1..maxNods):
// A228155 indexed [k], max depthsum of all AVL trees with k leaves:
A228155:=array(1..maxNods): A228155[1]:=0:
for k from 2 to maxNods do:
  A029837[k]:=maxNods: // try infinity for the min height
  A072649[k]:=0:
  A228155u:=0:
  // Put together 2 AVL trees:
  for kL from 1 to floor(k/2) do:
    // kL leaves in the left tree
    for hL from A029837[kL] to A072649[kL]-1 do:
      for hR from max(hL-1, A029837[k-kL])
               to min(hL+1, A072649[k-kL]-1) do:
        // k-kL leaves in the right subtree
        maxDepthSum:=T[hL, kL]+T[hR, k-kL]+k:
        A228155u:=max(maxDepthSum, A228155u):
        h:=max(hL, hR)+1:
        if type(T[h, k]) <> DOM_INT then // T[h, k] uninit
          T[h, k]:=maxDepthSum:
        else
          T[h, k]:=max(maxDepthSum, T[h, k]):
        end_if:
        A029837[k]:=min(h, A029837[k]):
        if type(A036289[h]) <> DOM_INT then
          A036289[h]:=maxDepthSum:
        else
          A036289[h]:=max(maxDepthSum, A036289[h]):
        end_if:
        A072649[k]:=max(h+1, A072649[k]):
      end_for: // hR
    end_for: // hL
  end_for: // kL
  A228155[k]:=A228155u:
end_for: // k

A228155 Maximal external path length of AVL trees with n (leaf-) nodes.

Original entry on oeis.org

0, 2, 5, 8, 12, 16, 20, 25, 30, 35, 40, 44, 50, 56, 62, 68, 73, 79, 85, 91, 97, 103, 110, 117, 123, 130, 137, 144, 151, 157, 163, 170, 177, 184, 191, 197, 204, 211, 219, 227, 235, 243, 250, 257, 265, 273, 281, 289, 296, 304, 312, 320, 328, 335, 342, 349, 356

Offset: 1

Herbert Eberle, Aug 14 2013

nonn

The external path length of a tree is the sum of the levels of its external nodes (i.e. leaves).

			The (two) AVL trees with 3 (leaf-) nodes have one with depth 1 and two with depth 2:
       o       o
      / \     / \
     o   1   1   o
    / \         / \
   2   2       2   2
so a(3) = 5.

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 = 1..5000
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

Column maxima of triangles A228152, A228153.
Row maxima give: n*2^n = A036289(n).
Row minima give: A067331(n-1) for n>0 or A166106(n+2).
Row lengths give: 1+A008466(n).
Column heights give: A217710(k).
Number of AVL trees read by rows gives: A143897.
The infimum of all external path lengths of all binary trees with k (leaf-) nodes is: A003314(k) for k>0.
Number of AVL trees read by columns gives: A217298.

maxNods = 100; Clear[T, A029837, A072649, A036289, A228155]; T[0, 1] = 0; A029837[1] = 0; A072649[1] = 1; A228155[1] = 0; For[k = 2, k <= maxNods, k++, A029837[k] = maxNods; A072649[k] = 0; A228155u = 0; For[kL = 1, kL <= Floor[k/2], kL++, For[hL = A029837[kL], hL <= A072649[kL] - 1, hL++, For[hR = Max[hL - 1, A029837[k - kL]], hR <= Min[hL + 1, A072649[k - kL] - 1], hR++, maxDepthSum = k + T[hL, kL] + T[hR, k - kL]; A228155u = Max[maxDepthSum, A228155u]; h = Max[hL, hR] + 1; If[ !IntegerQ[T[h, k]], T[h, k] = maxDepthSum, T[h, k] = Max[maxDepthSum, T[h, k]]]; A029837[k] = Min[h, A029837[k]]; If[ !IntegerQ[A036289[h]], A036289[h] = maxDepthSum, A036289[h] = Max[maxDepthSum, A036289[h]]]; A072649[k] = Max[h + 1, A072649[k]]; ]]]; A228155[k] = A228155u]; k =.; Table[A228155[k], {k, 1, maxNods}] (* Jean-François Alcover, Aug 19 2013, translated and adapted from Herbert Eberle's MuPAD program *)

maxNods:=100: // max number of leaves (= external nodes)
// Triangle T for all AVL trees with <= maxNods leaves:
delete T:
// table T indexed [h, k] (h=height, k=number of leaves):
T[0, 1]:=0:
// A029837 indexed [k], min height of tree with k leaves:
A029837:=array(1..maxNods): A029837[1]:=0:
// A072649 indexed [k], 1+max height of AVL tree with k leaves:
A072649:=array(1..maxNods): A072649[1]:=1:
// A036289 indexed [h], max depthsum of all height h AVL trees:
A036289:=array(1..maxNods):
// A228155 indexed [k], max depthsum of all AVL trees with k leaves:
A228155:=array(1..maxNods): A228155[1]:=0:
for k from 2 to maxNods do:
  A029837[k]:=maxNods: // try infinity for the min height
  A072649[k]:=0:
  A228155u:=0:
  // Put together 2 AVL trees:
  for kL from 1 to floor(k/2) do:
    // kL leaves in the left tree
    for hL from A029837[kL] to A072649[kL]-1 do:
      for hR from max(hL-1, A029837[k-kL])
               to min(hL+1, A072649[k-kL]-1) do:
        // k-kL leaves in the right subtree
        maxDepthSum:=T[hL, kL]+T[hR, k-kL]+k:
        A228155u:=max(maxDepthSum, A228155u):
        h:=max(hL, hR)+1:
        if type(T[h, k]) <> DOM_INT then // T[h, k] uninit
          T[h, k]:=maxDepthSum:
        else
          T[h, k]:=max(maxDepthSum, T[h, k]):
        end_if:
        A029837[k]:=min(h, A029837[k]):
        if type(A036289[h]) <> DOM_INT then
          A036289[h]:=maxDepthSum:
        else
          A036289[h]:=max(maxDepthSum, A036289[h]):
        end_if:
        A072649[k]:=max(h+1, A072649[k]):
      end_for: // hR
    end_for: // hL
  end_for: // kL
  A228155[k]:=A228155u:
end_for: // k

A351530 The number of quinary strings of length n containing 00.

Original entry on oeis.org

0, 0, 1, 9, 65, 421, 2569, 15085, 86241, 483429, 2669305, 14564061, 78699089, 421880725, 2246459881, 11894065549, 62665617345, 328756309701, 1718275598809, 8951067087165, 46492068009521, 240846026714869, 1244719810538185, 6419100507215341

Offset: 0

R. J. Mathar, Feb 13 2022

Michael De Vlieger, Table of n, a(n) for n = 0..1430
Index entries for linear recurrences with constant coefficients, signature (9,-16,-20).

Cf. A008466 (2-ary), A186244 (3-ary), A351529 (4-ary), A086347 (not containing 00).

CoefficientList[Series[x^2/((5*x - 1)*(4*x^2 + 4*x - 1)), {x, 0, 30}], x] (* Wesley Ivan Hurt, Jun 22 2022 *)
LinearRecurrence[{9,-16,-20},{0,0,1},30] (* Harvey P. Dale, Mar 26 2024 *)

G.f.: x^2 / ( (5*x-1)*(4*x^2+4*x-1) ).
a(n) = 5^n - A086347(n).
a(n) = 9*a(n-1) - 16*a(n-2) - 20*a(n-3). - Wesley Ivan Hurt, Jun 22 2022

A110814 Inverse of a triangle of pyramidal numbers.

Original entry on oeis.org

1, -3, 1, 7, -4, 1, -15, 11, -5, 1, 31, -26, 16, -6, 1, -63, 57, -42, 22, -7, 1, 127, -120, 99, -64, 29, -8, 1, -255, 247, -219, 163, -93, 37, -9, 1, 511, -502, 466, -382, 256, -130, 46, -10, 1, -1023, 1013, -968, 848, -638, 386, -176, 56, -11, 1, 2047, -2036, 1981, -1816, 1486, -1024, 562, -232, 67, -12, 1, -4095, 4083

Offset: 0

Paul Barry, Aug 05 2005

Inverse of A110813. Array factors as (1/(1+2x),x)*(1/(1+x),x/(1+x)). Row sums are (-2)^n. Diagonal sums are (-1)^n*A008466(n+2). Signed version of A104709.

			Rows begin
    1;
   -3,   1;
    7,  -4,   1;
  -15,  11,  -5,   1;
   31, -26,  16,  -6,   1;

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened

A110814_row := proc(n) add((-1)^k*add(binomial(n,n-i)*x^(n-k-1),i=0..k),k=0..n-1); coeffs(sort(%)) end; seq(print(A110814_row(n)),n=1..6); # Peter Luschny, Sep 29 2011

T[n_, k_] := Sum[(-2)^(n - j)*Binomial[j, k]*(-1)^(j - k), {j, 0, n}]; Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* G. C. Greubel, Oct 19 2017 *)

for(n=0,10, for(k=0,n, print1(sum(j=0,n, (-2)^(n-j)*(-1)^(j-k)* binomial(j,k)), ", "))) \\ G. C. Greubel, Oct 19 2017

Number triangle T(n, k) = Sum_{j=0..n} (-2)^(n-j)*binomial(j, k)*(-1)^(j-k).
Riordan array (1/(1+3x+2x^2), x/(1+x)).
T(n,k) = -3*T(n-1,k) + T(n-1,k-1) - 2*T(n-2,k) + 2*T(n-2,k-1), T(0,0)=1, T(n,k)=0 if k < 0 or if k > n. - Philippe Deléham, Nov 30 2013

A341050 Cube array read by upward antidiagonals ignoring zero and empty terms: T(n, k, r) is the number of n-ary strings of length k, containing r consecutive 0's.

Original entry on oeis.org

1, 1, 1, 3, 1, 1, 3, 1, 5, 8, 1, 1, 3, 1, 5, 8, 1, 7, 21, 19, 1, 1, 3, 1, 5, 8, 1, 7, 21, 20, 1, 9, 40, 81, 43, 1, 1, 3, 1, 5, 8, 1, 7, 21, 20, 1, 9, 40, 81, 47, 1, 11, 65, 208, 295, 94, 1, 1, 3, 1, 5, 8, 1, 7, 21, 20, 1, 9, 40, 81, 48, 1, 11, 65, 208, 297, 107, 1, 13, 96, 425, 1024, 1037, 201

Offset: 2

Robert P. P. McKone, Feb 04 2021

			For n = 5, k = 6 and r = 4, there are 65 strings: {000000, 000001, 000002, 000003, 000004, 000010, 000011, 000012, 000013, 000014, 000020, 000021, 000022, 000023, 000024, 000030, 000031, 000032, 000033, 000034, 000040, 000041, 000042, 000043, 000044, 010000, 020000, 030000, 040000, 100000, 100001, 100002, 100003, 100004, 110000, 120000, 130000, 140000, 200000, 200001, 200002, 200003, 200004, 210000, 220000, 230000, 240000, 300000, 300001, 300002, 300003, 300004, 310000, 320000, 330000, 340000, 400000, 400001, 400002, 400003, 400004, 410000, 420000, 430000, 440000}
The first seven slices of the tetrahedron (or pyramid) are:
-----------------Slice 1-----------------
  1
-----------------Slice 2-----------------
    1
  1  3
-----------------Slice 3-----------------
      1
    1  3
  1  5  8
-----------------Slice 4-----------------
        1
      1  3
    1  5   8
  1  7  21  19
-----------------Slice 5-----------------
          1
        1  3
      1  5   8
    1  7  21  20
  1  9  40  81  43
-----------------Slice 6-----------------
              1
           1    3
        1    5     8
      1   7    21    20
    1   9   40    81    47
  1  11  65   208   295   94
-----------------Slice 7-----------------
                 1
              1     3
           1     5     8
         1    7     21    20
      1    9    40     81      48
    1   11   65    208     297     107
  1  13   96   425    1024    1037    201

Robert P. P. McKone, Antidiagonals n = 2..50, flattened

Cf. A340156 (r=2), A340242 (r=3).
Cf. A008466 (n=2, r=2), A186244 (n=3, r=2), A050231 (n=2, r=3), A231430 (n=3, r=3).
Cf. A005408, A003215, A005917, A022521, A022522, A022523, A022524, A022525, A022526, A022527, A022528, A022529, A022530, A022531, A022532, A022533, A022534, A022535, A022536, A022537, A022538, A022539, A022540 (k=x, r=1, where x is the x-th Nexus Number).
Cf. A000567 [(k=4, r=2),(k=5, r=3),(k=6, r=4),...,(k=x, r=x-2)].
Cf. A103532 [(k=6, r=3),(k=7, r=4),(k=8, r=5),...,(k=x, r=x-3)].

m[r_, n_] := Normal[With[{p = 1/n}, SparseArray[{Band[{1, 2}] -> p, {i_, 1} /; i <= r -> 1 - p, {r + 1, r + 1} -> 1}]]]; T[n_, k_, r_] := MatrixPower[m[r, n], k][[1, r + 1]]*n^k; DeleteCases[Transpose[PadLeft[Reverse[Table[T[n, k, r], {k, 2, 8}, {r, 2, k}, {n, 2, r}], 2]], 2 <-> 3], 0, 3] // Flatten

cp's OEIS Frontend

A104004 Expansion of (1-x) * (1+x) / ((1-2*x)*(1-x-x^2)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

A353508 Number of integer compositions of n with no ones or runs of length 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A050227 Triangle of number of n-tosses having a run of r or more heads for a fair coin with r=1 to n across and n=1, 2, ... down.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

A175660 Eight bishops and one elephant on a 3 X 3 chessboard. a(n) = 2^(n+2) - 3*F(n+2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A228152 Triangle read by rows: T(n,k) = maximal external path length of AVL trees of height n with k (leaf-) nodes, n>=0, fibonacci(n+2)<=k<=2^n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

MuPAD

A228153 Triangle read by columns: T(n,k) = maximal external path length of AVL trees of height n with k (leaf-) nodes, k>=1, A029837(k)<=n<A072649(k).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

MuPAD

A228155 Maximal external path length of AVL trees with n (leaf-) nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A104004 Expansion of (1-x) * (1+x) / ((1-2x)(1-x-x^2)).