A370484 -id:A370484 - cp's OEIS frontend

A091980 Recursive sequence; one more than maximum of products of pairs of previous terms with indices summing to current index.

1, 2, 3, 5, 7, 11, 16, 26, 36, 56, 81, 131, 183, 287, 417, 677, 937, 1457, 2107, 3407, 4759, 7463, 10843, 17603, 24373, 37913, 54838, 88688, 123892, 194300, 282310, 458330, 634350, 986390, 1426440, 2306540, 3221844, 5052452, 7340712, 11917232, 16500522

Offset: 1

Franklin T. Adams-Watters, Mar 15 2004

The maximum is always obtained by taking i as the power of 2 nearest to n/2. - Anna de Mier, Mar 12 2012

a(n) is the number of (binary) max-heaps on n-1 elements from the set {0,1}. a(7) = 16: 000000, 100000, 101000, 101001, 110000, 110010, 110100, 110110, 111000, 111001, 111010, 111011, 111100, 111101, 111110, 111111. - Alois P. Heinz, Jul 09 2019

A. de Mier and M. Noy, On the maximum number of cycles in outerplanar and series-parallel graphs, Graphs Combin., 28 (2012), 265-275.

Alois P. Heinz, Table of n, a(n) for n = 1..5652
F. Disanto and N. A. Rosenberg, Enumeration of ancestral configurations for matching gene trees and species trees, J. Comput. Biol. 24 (2017), 831-850. See Section 4.2.
A. de Mier and M. Noy, On the maximum number of cycles in outerplanar and series-parallel graphs, Elect. Notes Discr. Math 34 (2009) 489-493
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap

Cf. A003095, A056971, A309049.
Partial differences give A168542.
a(n) = A355108(n)+1.
Column k=0 of A370484 and of A372640.

b:= proc(n) option remember; `if`(n=0, 1, (g-> (f->
      1+b(f)*b(n-1-f))(min(g-1, n-g/2)))(2^ilog2(n)))
    end:
a:= n-> b(n-1):
seq(a(n), n=1..50);  # Alois P. Heinz, Jul 09 2019

a[n_] := a[n] = 1 + Max[Table[a[i] a[n-i], {i, n-1}]]; a[1] = 1;
Array[a, 50] (* Jean-François Alcover, Apr 30 2020 *)

a(n) = 1 + max_{i=1..n-1} a(i)*a(n-i) for n > 1, a(1) = 1.
From Alois P. Heinz, Jul 09 2019: (Start)
a(n) = Sum_{k=0..n-1} A309049(n-1,k).
a(2^(n-1)) = A003095(n). (End)

A372640 Number T(n,k) of defective (binary) heaps on n elements from the set {0,1} where k ancestor-successor pairs do not have the correct order; triangle T(n,k), n>=0, read by rows.

Original entry on oeis.org

1, 2, 3, 1, 5, 2, 1, 7, 4, 3, 2, 11, 6, 7, 5, 2, 1, 16, 13, 12, 8, 10, 3, 2, 26, 22, 23, 14, 21, 10, 9, 2, 1, 36, 36, 39, 33, 33, 28, 26, 13, 9, 2, 1, 56, 54, 67, 61, 60, 59, 56, 37, 34, 11, 13, 2, 2, 81, 99, 111, 96, 117, 112, 107, 96, 76, 53, 36, 20, 14, 4, 2

Offset: 0

Alois P. Heinz, May 08 2024

T(n,k) is the number of bit vectors v of length n having exactly k pairs (i,j) in {1,...,n} X {1,...,floor(log_2(i))} such that v[i] > v[floor(i/2^j)].
T(n,0) counts perfect (binary) heaps on n elements from the set {0,1}.
T(n,k) is defined for all n>=0 and k>=0. The triangle displays only positive terms. All other terms are zero.

			T(4,0) = 7: 0000, 1000, 1010, 1100, 1101, 1110, 1111.
T(4,1) = 4: 0010, 0100, 1001, 1011.
T(4,2) = 3: 0001, 0101, 0110.
T(4,3) = 2: 0011, 0111.
(The examples use max-heaps.)
Triangle T(n,k) begins:
   1;
   2;
   3,  1;
   5,  2,   1;
   7,  4,   3,  2;
  11,  6,   7,  5,   2,   1;
  16, 13,  12,  8,  10,   3,   2;
  26, 22,  23, 14,  21,  10,   9,  2,  1;
  36, 36,  39, 33,  33,  28,  26, 13,  9,  2,  1;
  56, 54,  67, 61,  60,  59,  56, 37, 34, 11, 13,  2,  2;
  81, 99, 111, 96, 117, 112, 107, 96, 76, 53, 36, 20, 14, 4, 2;
  ...

Alois P. Heinz, Rows n = 0..112, flattened
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap

Columns k=0-1 give: A091980(n+1), A372643.
Row sums give A000079.
Main diagonal gives A372641.
T(2,n) gives A372642.
Cf. A306393, A370484.

b:= proc(n, t) option remember; `if`(n=0, 1, (g-> (f->
      expand(b(f, t)*b(n-1-f, t)*x^t+b(f, t+1)*b(n-1-f, t+1)
          ))(min(g-1, n-g/2)))(2^ilog2(n)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):
seq(T(n), n=0..14);

b[n_, t_] := b[n, t] = If[n == 0, 1, Function[g, Function [f,
   Expand[b[f, t]*b[n-1-f, t]*x^t + b[f, t+1]*b[n-1 - f, t+1]]][
   Min[g-1, n-g/2]]][2^(Length@IntegerDigits[n, 2]-1)]];
T[n_] := CoefficientList[b[n, 0], x];
Table[T[n], {n, 0, 14}] // Flatten (* Jean-François Alcover, May 09 2024, after Alois P. Heinz *)

A372628 Number of defective (binary) heaps on n elements from the set {0,1} with exactly one defect.

Original entry on oeis.org

0, 0, 1, 2, 6, 11, 20, 32, 60, 100, 162, 255, 427, 692, 1093, 1738, 2800, 4507, 6951, 11032, 17224, 27553, 42276, 67639, 103989, 165856, 251312, 401236, 608112, 968380, 1465934, 2354752, 3525880, 5585826, 8370796, 13394396, 19937564, 31632664, 47478092

Offset: 0

Alois P. Heinz, May 07 2024

nonn

A defect in a defective heap is a parent-child pair not having the correct order.

a(n) is the number of bit vectors v of length n having exactly one index i in [n] with v[i] > v[floor(i/2)].

			a(2) = 1: 01.
a(3) = 2: 001, 010.
a(4) = 6: 0001, 0010, 0100, 0101, 1001, 1011.
a(5) = 11: 00001, 00010, 00100, 01000, 01001, 01010, 01011, 10001, 10010, 10101, 10110.
(The examples use max-heaps.)

Alois P. Heinz, Table of n, a(n) for n = 0..5634
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap

Column k=1 of A370484.

Cf. A323957, A372643.

b:= proc(n, t) option remember; convert(series(`if`(n=0, 1, (g->
      (f-> expand(b(f, 1)*b(n-1-f, 1)*t+b(f, x)*b(n-1-f, x)))(
           min(g-1, n-g/2)))(2^ilog2(n))), x, 2), polynom)
    end:
a:= n-> coeff(b(n, 1), x, 1):
seq(a(n), n=0..38);

b[n_, t_] := b[n, t] = If[n == 0, 1, Function[g, Function[f,
   Expand[b[f, 1]*b[n - 1 - f, 1]*t + b[f, x]*b[n - 1 - f, x]]][
   Min[g - 1, n - g/2]]][2^(Length[IntegerDigits[n, 2]] - 1)]];
a[n_] := Coefficient[b[n, 1], x, 1];
Table[a[n], {n, 0, 38}] (* Jean-François Alcover, May 11 2024, after Alois P. Heinz *)

A372489 Number of defective (binary) heaps on 2n elements from the set {0,1} with exactly n defects.

Original entry on oeis.org

1, 1, 3, 4, 8, 18, 41, 104, 253, 579, 1370, 3184, 7331, 16720, 38720, 91720, 218038, 518268, 1259464, 3141644, 7687556, 18460394, 45409204, 115174672, 283748621, 680088840, 1665189408, 4207220068, 10403856572, 25304979704, 62881939100, 161253396400, 396959041273

Offset: 0

Alois P. Heinz, May 06 2024

nonn

A defect in a defective heap is a parent-child pair not having the correct order.

a(n) is the number of bit vectors v of length 2n having exactly n indices i in [2n] such that v[i] > v[floor(i/2)].

			a(0) = 1: the empty heap.
a(1) = 1: 01.
a(2) = 3: 0011, 0110, 0111.
a(3) = 4: 000111, 001110, 001111, 100111.
a(4) = 8: 00001111, 00011110, 00011111, 01000111, 01001111, 10001111, 10011110, 10011111.
a(5) = 18: 0000011111, 0000111110, 0000111111, 0100001111, 0100010111, 0100011011, 0100011101, 0100011110, 0100111110, 0100111111, 0110000111, 0110001111, 0110010111, 0110011111, 1000011111, 1000111110, 1000111111, 1100011111.
(The examples use max-heaps.)

Alois P. Heinz, Table of n, a(n) for n = 0..2528
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap

Cf. A091980 (no defects), A370484.

b:= proc(n, t) option remember; `if`(n=0, 1, (g-> (f->
      expand(b(f, 1)*b(n-1-f, 1)*t+b(f, x)*b(n-1-f, x)))(
      min(g-1, n-g/2)))(2^ilog2(n)))
    end:
a:= n-> coeff(b(2*n, 1), x, n):
seq(a(n), n=0..32);

a(n) = A370484(2n,n).

cp's OEIS Frontend

A091980 Recursive sequence; one more than maximum of products of pairs of previous terms with indices summing to current index.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A372640 Number T(n,k) of defective (binary) heaps on n elements from the set {0,1} where k ancestor-successor pairs do not have the correct order; triangle T(n,k), n>=0, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A372628 Number of defective (binary) heaps on n elements from the set {0,1} with exactly one defect.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A372489 Number of defective (binary) heaps on 2n elements from the set {0,1} with exactly n defects.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula