A372640 -id:A372640 - cp's OEIS frontend

A306393 Number T(n,k) of defective (binary) heaps on n elements where k ancestor-successor pairs do not have the correct order; triangle T(n,k), n >= 0, 0 <= k <= A061168(n), read by rows.

1, 1, 1, 1, 2, 2, 2, 3, 6, 6, 6, 3, 8, 16, 24, 24, 24, 16, 8, 20, 60, 100, 120, 120, 120, 100, 60, 20, 80, 240, 480, 640, 720, 720, 720, 640, 480, 240, 80, 210, 840, 1890, 3150, 4200, 4830, 5040, 5040, 4830, 4200, 3150, 1890, 840, 210

Offset: 0

Alois P. Heinz, Feb 12 2019

T(n,k) is the number of permutations p of [n] having exactly k pairs (i,j) in {1,...,n} X {1,...,floor(log_2(i))} such that p(i) > p(floor(i/2^j)).

T(n,0) counts perfect (binary) heaps on n elements (A056971).

			T(4,0) = 3: 4231, 4312, 4321.
T(4,1) = 6: 3241, 3412, 3421, 4123, 4132, 4213.
T(4,2) = 6: 2341, 2413, 2431, 3124, 3142, 3214.
T(4,3) = 6: 1342, 1423, 1432, 2134, 2143, 2314.
T(4,4) = 3: 1234, 1243, 1324.
T(5,1) = 16: 43512, 43521, 45123, 45132, 45213, 45231, 45312, 45321, 52314, 52341, 52413, 52431, 53124, 53142, 53214, 53241.
(The examples use max-heaps.)
Triangle T(n,k) begins:
   1;
   1;
   1,   1;
   2,   2,   2;
   3,   6,   6,   6,   3;
   8,  16,  24,  24,  24,  16,   8;
  20,  60, 100, 120, 120, 120, 100,  60,  20;
  80, 240, 480, 640, 720, 720, 720, 640, 480, 240, 80;
  ...

Alois P. Heinz, Rows n = 0..100, flattened
Marko Riedel, math.stackexchange.com, Average number of inversions in a random binary heap on 2^n-1 elements.
Marko Riedel, Average number of inversions in a random binary heap on 2^n-1 elements (PDF).
Eric Weisstein's World of Mathematics, Heap,
Wikipedia, Binary heap.
Wikipedia, Permutation.

Columns k=0-10 give: A056971, A324062, A324063, A324064, A324065, A324066, A324067, A324068, A324069, A324070, A324071.
Row sums give A000142.
Central terms (also maxima) of rows give A324075.
Cf. A000523, A008302, A061168, A120385, A306343, A324074, A372640.
Average number of inversions of a full binary heap on 2^n-1 elements is A000337.

b:= proc(u, o) option remember; local n, g, l; n:= u+o;
      if n=0 then 1
    else g:= 2^ilog2(n); l:= min(g-1, n-g/2); expand(
         add(x^(n-j)*add(binomial(j-1, i)*binomial(n-j, l-i)*
         b(i, l-i)*b(j-1-i, n-l-j+i), i=0..min(j-1, l)), j=1..u)+
         add(x^(j-1)*add(binomial(j-1, i)*binomial(n-j, l-i)*
         b(l-i, i)*b(n-l-j+i, j-1-i), i=0..min(j-1, l)), j=1..o))
      fi
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):
seq(T(n), n=0..10);

b[u_, o_] := b[u, o] = Module[{n, g, l}, n = u + o;
     If[n == 0, 1, g = 2^Floor@Log[2, n]; l = Min[g - 1, n - g/2]; Expand[
     Sum[x^(n-j)*Sum[Binomial[j - 1, i]*Binomial[n - j, l - i]*
     b[i, l-i]*b[j-1-i, n-l-j+i], {i, 0, Min[j - 1, l]}], {j, 1, u}] +
     Sum[x^(j-1)*Sum[Binomial[j - 1, i]*Binomial[n - j, l - i]*
     b[l-i, i]*b[n-l-j+i, j-1-i], {i, 0, Min[j-1, l]}], {j, 1, o}]]]];
T[n_] := CoefficientList[b[n, 0], x];
T /@ Range[0, 10] // Flatten (* Jean-François Alcover, Feb 15 2021, after Alois P. Heinz *)

T(n,k) = T(n,A061168(n)-k) for n > 0.

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

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

Original entry on oeis.org

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)

A370484 Number T(n,k) of defective (binary) heaps on n elements from the set {0,1} with k defects; triangle T(n,k), n>=0, read by rows.

Original entry on oeis.org

1, 2, 3, 1, 5, 2, 1, 7, 6, 3, 11, 11, 9, 1, 16, 20, 24, 4, 26, 32, 52, 16, 2, 36, 60, 100, 52, 8, 56, 100, 192, 120, 40, 4, 81, 162, 351, 300, 111, 18, 1, 131, 255, 631, 627, 313, 77, 13, 1, 183, 427, 1067, 1311, 821, 241, 41, 5, 287, 692, 1856, 2484, 1894, 764, 184, 28, 3

Offset: 0

Alois P. Heinz, May 06 2024

A defect in a defective heap is a parent-child pair not having the correct order.
T(n,k) is the number of bit vectors v of length n having exactly k indices i in [n] such that v[i] > v[floor(i/2)].
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) = 6: 0001, 0010, 0100, 0101, 1001, 1011.
T(4,2) = 3: 0011, 0110, 0111.
(The examples use max-heaps.)
Triangle T(n,k) begins:
    1;
    2;
    3,   1;
    5,   2,    1;
    7,   6,    3;
   11,  11,    9,    1;
   16,  20,   24,    4;
   26,  32,   52,   16,   2;
   36,  60,  100,   52,   8;
   56, 100,  192,  120,  40,   4;
   81, 162,  351,  300, 111,  18,  1;
  131, 255,  631,  627, 313,  77, 13, 1;
  183, 427, 1067, 1311, 821, 241, 41, 5;
  ...

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

Columns k=0-1 give: A091980(n+1), A372628.
Row sums give A000079.
T(2n,n) gives A372489.
Cf. A045623, A056971, A139756, A306343, A372640.

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:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 1)):
seq(T(n), n=0..15);

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)]];
T[n_] := CoefficientList[b[n, 1], x];
Table[T[n], {n, 0, 15}] // Flatten (* Jean-François Alcover, May 09 2024, after Alois P. Heinz *)

Sum_{k>=0} k * T(n,k) = A139756(n) = ceiling((n-1)*2^n/4).

Sum_{k>=0} (k+1) * T(n,k) = A045623(n) = ceiling((n+3)*2^n/4).

A372643 Number of defective (binary) heaps on n elements from the set {0,1} where exactly one ancestor-successor pair does not have the correct order.

Original entry on oeis.org

0, 0, 1, 2, 4, 6, 13, 22, 36, 54, 99, 164, 260, 400, 692, 1146, 1730, 2638, 4358, 7148, 10788, 16716, 27168, 44692, 65630, 100736, 159851, 261156, 385740, 599704, 946368, 1551686, 2245014, 3455650, 5364990, 8743620, 12757292, 19869332, 30818816, 50429524

Offset: 0

Alois P. Heinz, May 08 2024

nonn

			a(2) = 1: 01.
a(3) = 2: 001, 010.
a(4) = 4: 0010, 0100, 1001, 1011.
a(5) = 6: 00100, 01000, 10001, 10010, 10101, 10110.
a(6) = 13: 001000, 010000, 100001, 100010, 100100, 101010, 101011, 101100, 101101, 110001, 110011, 110101, 110111.
(The examples use max-heaps.)

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

Column k=1 of A372640.

Cf. A323957, A372628.

b:= proc(n, t) option remember; convert(series(`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))),x,2), polynom)
    end:
a:= n-> coeff(b(n, 0),x,1):
seq(a(n), n=0..39);

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)]];
a[n_] := Coefficient[b[n, 0], x, 1];
Table[a[n], {n, 0, 39}] (* Jean-François Alcover, May 09 2024, after Alois P. Heinz *)

a(n) = A372640(n,1).

A372641 Number of defective (binary) heaps on n elements from the set {0,1} where exactly n ancestor-successor pairs do not have the correct order.

Original entry on oeis.org

1, 0, 0, 0, 0, 1, 2, 2, 9, 11, 36, 71, 151, 306, 591, 1228, 2469, 4966, 10025, 19591, 38946, 75977, 148585, 291027, 579981, 1152385, 2280696, 4470814, 8817933, 17244969, 33819425, 65976444, 129933731, 254791662, 499516984, 977417823, 1914394157, 3745482924

Offset: 0

Alois P. Heinz, May 08 2024

nonn

			a(5) = 1: 00111.
a(6) = 2: 000111, 001111.
a(7) = 2: 0011111, 0101111.
a(8) = 9: 00010111, 00011011, 00011101, 00011110, 00101111, 00111011, 00111101, 01001111, 01011111.
a(9) = 11: 000011101, 000011110, 001001111, 001010011, 001101111, 001110011, 001111101, 001111110, 010001111, 010111111, 011011111.
(The examples use max-heaps.)

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

Main diagonal of A372640.

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:
a:= n-> coeff(b(n, 0),x,n):
seq(a(n), n=0..37);

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)]];
a[n_] := Coefficient[b[n, 0], x, n];
Table[a[n], {n, 0, 37}] (* Jean-François Alcover, May 09 2024, after Alois P. Heinz *)

a(n) = A372640(n,n).

A372642 Number of defective (binary) heaps on 2n elements from the set {0,1} where exactly n ancestor-successor pairs do not have the correct order.

Original entry on oeis.org

1, 1, 3, 8, 33, 112, 370, 1186, 4338, 14999, 52175, 179159, 649132, 2415766, 8994203, 33305573, 120968991, 431067336, 1538631892, 5509192918, 19859364136, 72330631743, 265219210010, 977508697125, 3619996788047, 13376125657317, 49294003078858, 181671504803323

Offset: 0

Alois P. Heinz, May 08 2024

nonn

			a(0) = 1: the empty heap.
a(1) = 1: 01.
a(2) = 3: 0001, 0101, 0110.
a(3) = 8: 001010, 001100, 010001, 010110, 011001, 011010, 011100, 100111.
(The examples use max-heaps.)

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

Cf. A372640.

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:
a:= n-> coeff(b(2*n, 0), x, n):
seq(a(n), n=0..27);

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)]];
a[n_] := Coefficient[b[2 n, 0], x, n];
Table[a[n], {n, 0, 27}] (* Jean-François Alcover, May 09 2024, after Alois P. Heinz *)

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

cp's OEIS Frontend

A306393 Number T(n,k) of defective (binary) heaps on n elements where k ancestor-successor pairs do not have the correct order; triangle T(n,k), n >= 0, 0 <= k <= A061168(n), read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

A370484 Number T(n,k) of defective (binary) heaps on n elements from the set {0,1} with k defects; triangle T(n,k), n>=0, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A372643 Number of defective (binary) heaps on n elements from the set {0,1} where exactly one ancestor-successor pair does not have the correct order.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A372641 Number of defective (binary) heaps on n elements from the set {0,1} where exactly n ancestor-successor pairs do not have the correct order.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A372642 Number of defective (binary) heaps on 2n elements from the set {0,1} where exactly n ancestor-successor pairs do not have the correct order.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula