A056971 -id:A056971 - cp's OEIS frontend

A309049 Number T(n,k) of (binary) max-heaps on n elements from the set {0,1} containing exactly k 0's; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 3, 3, 2, 1, 1, 1, 3, 4, 4, 2, 1, 1, 1, 4, 6, 6, 5, 2, 1, 1, 1, 4, 7, 8, 7, 5, 2, 1, 1, 1, 5, 10, 12, 11, 8, 5, 2, 1, 1, 1, 5, 11, 16, 17, 13, 9, 5, 2, 1, 1, 1, 6, 15, 23, 27, 24, 16, 10, 5, 2, 1, 1, 1, 6, 16, 27, 34, 34, 27, 18, 11, 5, 2, 1, 1

Offset: 0

Alois P. Heinz, Jul 09 2019

Also the number T(n,k) of (binary) min-heaps on n elements from the set {0,1} containing exactly k 1's.

The sequence of column k satisfies a linear recurrence with constant coefficients of order A063915(k).

			T(6,0) = 1: 111111.
T(6,1) = 3: 111011, 111101, 111110.
T(6,2) = 4: 110110, 111001, 111010, 111100.
T(6,3) = 4: 101001, 110010, 110100, 111000.
T(6,4) = 2: 101000, 110000.
T(6,5) = 1: 100000.
T(6,6) = 1: 000000.
T(7,4) = T(7,7-3) = A000108(3) = 5: 1010001, 1010010, 1100100, 1101000, 1110000.
Triangle T(n,k) begins:
  1;
  1, 1;
  1, 1,  1;
  1, 2,  1,  1;
  1, 2,  2,  1,  1;
  1, 3,  3,  2,  1,  1;
  1, 3,  4,  4,  2,  1,  1;
  1, 4,  6,  6,  5,  2,  1,  1;
  1, 4,  7,  8,  7,  5,  2,  1,  1;
  1, 5, 10, 12, 11,  8,  5,  2,  1, 1;
  1, 5, 11, 16, 17, 13,  9,  5,  2, 1, 1;
  1, 6, 15, 23, 27, 24, 16, 10,  5, 2, 1, 1;
  1, 6, 16, 27, 34, 34, 27, 18, 11, 5, 2, 1, 1;
  ...

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

Columns k=0-10 give: A000012, A110654, A114220 (for n>0), A326504, A326505, A326506, A326507, A326508, A326509, A326510, A326511.
Row sums give A091980(n+1).
T(2n,n) gives A309050.
Rows reversed converge to A000108.
Cf. A000225, A000295, A003095, A024358, A056971, A063915, A137560, A168542, A202019, A309051, A309052.

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

b[n_] := b[n] = If[n == 0, 1, Function[g, Function[f, Expand[x^n + b[f]*b[n - 1 - f]]][Min[g - 1, n - g/2]]][2^Floor[Log[2, n]]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, n}]][b[n]];
T /@ Range[0, 14] // Flatten (* Jean-François Alcover, Oct 04 2019, after Alois P. Heinz *)

Sum_{k=0..n}    k  * T(n,k) = A309051(n).
Sum_{k=0..n} (n-k) * T(n,k) = A309052(n).
Sum_{k=0..2^n-1} T(2^n-1,k) = A003095(n+1).
Sum_{k=0..2^n-1} (2^n-1-k) * T(2^n-1,k) = A024358(n).
Sum_{k=0..n} (T(n,k) - T(n-1,k)) = A168542(n).
T(m,m-n) = A000108(n) for m >= 2^n-1 = A000225(n).
T(2^n-1,k) = A202019(n+1,k+1).

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.

Original entry on oeis.org

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)

A306343 Number T(n,k) of defective (binary) heaps on n elements with k defects; triangle T(n,k), n>=0, 0<=k<=max(0,n-1), read by rows.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 2, 3, 9, 9, 3, 8, 28, 48, 28, 8, 20, 90, 250, 250, 90, 20, 80, 360, 1200, 1760, 1200, 360, 80, 210, 1526, 5922, 12502, 12502, 5922, 1526, 210, 896, 7616, 34160, 82880, 111776, 82880, 34160, 7616, 896, 3360, 32460, 185460, 576060, 1017060, 1017060, 576060, 185460, 32460, 3360

Offset: 0

Alois P. Heinz, Feb 08 2019

A defect in a defective heap is a parent-child pair not having the correct order.
T(n,k) is the number of permutations p of [n] having exactly k indices i in {1,...,n} such that p(i) > p(floor(i/2)).
T(n,0) counts perfect (binary) heaps on n elements (A056971).

			T(4,0) = 3: 4231, 4312, 4321.
T(4,1) = 9: 2413, 3124, 3214, 3241, 3412, 3421, 4123, 4132, 4213.
T(4,2) = 9: 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2431, 3142.
T(4,3) = 3: 1234, 1243, 1324.
(The examples use max-heaps.)
Triangle T(n,k) begins:
    1;
    1;
    1,    1;
    2,    2,     2;
    3,    9,     9,     3;
    8,   28,    48,    28,      8;
   20,   90,   250,   250,     90,    20;
   80,  360,  1200,  1760,   1200,   360,    80;
  210, 1526,  5922, 12502,  12502,  5922,  1526,  210;
  896, 7616, 34160, 82880, 111776, 82880, 34160, 7616, 896;
  ...

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

Columns k=0-10 give: A056971, A323957, A323958, A323959, A323960, A323961, A323962, A323963, A323964, A323965, A323966.
Row sums give A000142.
T(n,floor(n/2)) gives A306356.
Cf. A001286, A001710, A008292, A038720, A229039, A230056, A264902, A306393.

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(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(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)*x)
      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 = u + o, g, l},
     If[n == 0, 1, g := 2^Floor@Log[2, n]; l = Min[g-1, n-g/2]; Expand[
     Sum[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[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}]*x]]];
T[n_] := CoefficientList[b[n, 0], x];
T /@ Range[0, 10] // Flatten (* Jean-François Alcover, Feb 17 2021, after Alois P. Heinz *)

T(n,k) = T(n,n-1-k) for n > 0.
Sum_{k>=0} k * T(n,k) = A001286(n).
Sum_{k>=0} (k+1) * T(n,k) = A001710(n-1) for n > 0.
Sum_{k>=0} (k+2) * T(n,k) = A038720(n) for n > 0.
Sum_{k>=0} (k+3) * T(n,k) = A229039(n) for n > 0.
Sum_{k>=0} (k+4) * T(n,k) = A230056(n) for n > 0.

A273693 Number A(n,k) of k-ary heaps on n elements; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 2, 1, 0, 1, 1, 1, 2, 3, 1, 0, 1, 1, 1, 2, 6, 8, 1, 0, 1, 1, 1, 2, 6, 12, 20, 1, 0, 1, 1, 1, 2, 6, 24, 40, 80, 1, 0, 1, 1, 1, 2, 6, 24, 60, 180, 210, 1, 0, 1, 1, 1, 2, 6, 24, 120, 240, 630, 896, 1, 0, 1, 1, 1, 2, 6, 24, 120, 360, 1260, 3360, 3360, 1, 0

Offset: 0

Alois P. Heinz, May 28 2016

			A(4,2) = 3: 1234, 1243, 1324.
A(5,2) = 8: 12345, 12354, 12435, 12453, 12534, 12543, 13245, 13254.
A(5,3) = 12: 12345, 12354, 12435, 12453, 12534, 12543, 13245, 13254, 13425, 13524, 14235, 14325.
A(6,3) = 40: 123456, 123465, 123546, 123564, 123645, 123654, 124356, 124365, 124536, 124563, 124635, 124653, 125346, 125364, 125436, 125463, 125634, 125643, 126345, 126354, 126435, 126453, 126534, 126543, 132456, 132465, 132546, 132564, 132645, 132654, 134256, 134265, 135246, 135264, 136245, 136254, 142356, 142365, 143256, 143265.
(The examples use min-heaps.)
Square array A(n,k) begins:
  1, 1,   1,   1,    1,    1,    1,    1, ...
  1, 1,   1,   1,    1,    1,    1,    1, ...
  0, 1,   1,   1,    1,    1,    1,    1, ...
  0, 1,   2,   2,    2,    2,    2,    2, ...
  0, 1,   3,   6,    6,    6,    6,    6, ...
  0, 1,   8,  12,   24,   24,   24,   24, ...
  0, 1,  20,  40,   60,  120,  120,  120, ...
  0, 1,  80, 180,  240,  360,  720,  720, ...
  0, 1, 210, 630, 1260, 1680, 2520, 5040, ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened
Wikipedia, D-ary heap

Columns k=0-10 give: A019590(n+1), A000012, A056971, A178008, A178009, A178010, A178011, A273694, A273695, A273696, A273697.
Main diagonal gives: A000142(n-1) for n>0.
Cf. A273712.

with(combinat):
A:= proc(n, k) option remember; local h, i, x, y, z;
      if n<2 then 1 elif k<2 then k
    else h:= ilog[k]((k-1)*n+1);
         if k^h=(k-1)*n+1 then A((n-1)/k, k)^k*
            multinomial(n-1, ((n-1)/k)$k)
       else x, y:=(k^h-1)/(k-1), (k^(h-1)-1)/(k-1);
            for i from 0 do z:= (n-1)-(k-1-i)*y-i*x;
              if y<=z and z<=x then A(y, k)^(k-1-i)*
                 multinomial(n-1, y$(k-1-i), x$i, z)*
                 A(x, k)^i*A(z, k); break fi
            od
      fi fi
    end:
seq(seq(A(n, d-n), n=0..d), d=0..14);

multinomial[n_, k_] := n!/Times @@ (k!); A[n_, k_] := A[n, k] = Module[{h, i, x, y, z}, Which[n<2, 1, k<2, k, True, h = Floor @ Log[k, (k-1)*n+1]; If[k^h == (k-1)*n+1, A[(n-1)/k, k]^k*multinomial[n-1, Array[((n-1)/k)&, k]], {x, y} = {(k^h-1)/(k-1), (k^(h-1)-1)/(k-1)}; For[i = 0, True, i++, z = (n-1)-(k-1-i)*y-i*x; If[y<=z && z<=x, A[y, k]^(k-1-i)*multinomial[n-1, Join[Array[y&, k-1-i], Array[x&, i], {z}]]*A[x, k]^i*A[z, k] // Return]] ]]]; Table[A[n, d-n], {d, 0, 14}, {n, 0, d}] // Flatten (* Jean-François Alcover, Mar 13 2017, translated from Maple *)

A373451 Number T(n,k) of (binary) heaps of length n whose element set equals [k]; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 3, 2, 0, 1, 5, 7, 3, 0, 1, 9, 23, 23, 8, 0, 1, 14, 55, 92, 70, 20, 0, 1, 24, 147, 386, 502, 320, 80, 0, 1, 34, 281, 1004, 1861, 1880, 985, 210, 0, 1, 54, 633, 3128, 8113, 12008, 10237, 4690, 896, 0, 1, 79, 1241, 8039, 27456, 54900, 66730, 48650, 19600, 3360

Offset: 0

Alois P. Heinz, Jun 05 2024

These heaps may contain repeated elements. Their element sets are gap-free and contain 1 (if nonempty).

T(n,k) is defined for n,k >= 0. The triangle contains only the terms with k<=n. T(n,k) = 0 for k>n.

			T(4,1) = 1: 1111.
T(4,2) = 5: 2111, 2121, 2211, 2212, 2221.
T(4,3) = 7: 3121, 3211, 3212, 3221, 3231, 3312, 3321.
T(4,4) = 3: 4231, 4312, 4321.
(The examples use max-heaps.)
Triangle T(n,k) begins:
  1;
  0, 1;
  0, 1,  1;
  0, 1,  3,   2;
  0, 1,  5,   7,    3;
  0, 1,  9,  23,   23,    8;
  0, 1, 14,  55,   92,   70,    20;
  0, 1, 24, 147,  386,  502,   320,    80;
  0, 1, 34, 281, 1004, 1861,  1880,   985,  210;
  0, 1, 54, 633, 3128, 8113, 12008, 10237, 4690, 896;
  ...

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

Columns k=0-4 give A000007, A057427, A091980(n+1)-2, A376962, A376963.
Row sums give A373452.
Row maxima give A373608.
Main diagonal gives A056971.
First lower diagonal gives A373496.
T(2n,n) gives A373500.
Antidiagonal sums give A373632.
Antidiagonal maxima give A373897.
Cf. A019590, A373449.

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

b[n_, k_] := b[n, k] = If[n == 0, 1,
   Function[g, Function[f, Sum[b[f, j]*b[n-1-f, j], {j, 1, k}]][
      Min[g-1, n-g/2]]][2^(Length@IntegerDigits[n, 2]-1)]];
T[n_, k_] := Sum[Binomial[k, j]*(-1)^j*b[n, k-j], {j, 0, k}];
Table[Table[T[n, k], {k, 0, n}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Sep 20 2024, after Alois P. Heinz *)

T(n,k) = Sum_{j=0..k} binomial(k,j) * (-1)^j * A373449(n,k-j).

Sum_{k=0..n} (-1)^k * T(n,n-k) = A019590(n+1).

A056972 Number of (binary) heaps on n levels (i.e., of 2^n - 1 elements).

Original entry on oeis.org

1, 1, 2, 80, 21964800, 74836825861835980800000, 2606654998899867556195703676289609067340669424836280320000000000

Offset: 0

Eric W. Weisstein

nonn

A sequence {a_i}{i=1..N} forms a (binary) heap if it satisfies a_i<a{2i} and a_i

a(n) is also the number of knockout tournament seedings that satisfy the increasing competitive intensity property. - Alexander Karpov, Aug 18 2015

a(n) is the number of coalescence sequences, or labeled histories, for a binary, leaf-labeled, rooted tree topology with 2^n leaves (Rosenberg 2006, Theorem 3.3 for a completely symmetric tree with 2^n leaves, dividing by Theorem 3.2 for 2^n leaves). - Noah A Rosenberg, Feb 12 2019

a(n+1) is also the number of random walk labelings of the perfect binary tree of height n, that begin at the root. - Sela Fried, Aug 02 2023

If a bracket of 2^n teams is specified for a single-elimination tournament, a(n) is the number of sequences in which the games of the tournament can be played in a single arena. - Noah A Rosenberg, Jan 01 2025

			There is 1 heap on 2^0-1=0 elements, 1 heap on 2^1-1=1 element and there are 2 heaps on 2^2-1=3 elements and so on.

Alois P. Heinz, Table of n, a(n) for n = 0..9
Emily H. Dickey and Noah A. Rosenberg, Labelled histories with multifurcation and simultaneity, Phil. Trans. R. Soc. B 380 (2025), 20230307.
Sela Fried and Toufik Mansour, Random walk labelings of perfect trees and other graphs, arXiv:2308.00315 [math.CO], 2023.
Alexander Karpov, A theory of knockout tournament seedings, Heidelberg University, AWI Discussion Paper Series, No. 600.
Matthew C. King and Noah A. Rosenberg, A mathematical connection between single-elimination sports tournaments and evolutionary trees, Math. Mag. 96 (2023), 484-497.
Egor Lappo and Noah A. Rosenberg, A lattice structure for ancestral configurations arising from the relationship between gene trees and species trees, Adv. Appl. Math. 343 (2024), 65-81.
Noah A. Rosenberg, The Mean and Variance of the Numbers of r-Pronged Nodes and r-Caterpillars in Yule-Generated Genealogical Trees, Ann. Combinator. 10 (2006), 129-146.
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap

Cf. A000225, A056971, A195581.

Column k=2 of A273712.

a:= n-> (2^n-1)!/mul((2^k-1)^(2^(n-k)), k=1..n):
seq(a(i), i=0..6);  # Alois P. Heinz, Nov 22 2007

s[1] := 1; s[l_] := s[l] := Binomial[2^l-2, 2^(l-1)-1]s[l-1]^2; Table[s[l], {l, 10}]

from math import prod, factorial
def A056972(n): return factorial((1<Chai Wah Wu, May 06 2024

a(n) = A056971(A000225(n)).
a(n) = A195581(2^n-1,n).
a(n) = binomial(2^n-2, 2^(n-1)-1)*a(n-1)^2. - Robert Israel, Aug 18 2015, from the Mathematica program
a(n) = (2^n-1)!/Product_{k=1..n} (2^k-1)^(2^(n-k)). - Robert Israel, Aug 18 2015, from the Maple program

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

A132862 Number of permutations divided by the number of (binary) heaps on n elements.

Original entry on oeis.org

1, 1, 2, 3, 8, 15, 36, 63, 192, 405, 1080, 2079, 6048, 12285, 31752, 59535, 193536, 433755, 1224720, 2488563, 7620480, 16253055, 44008272, 86266215, 274337280, 602791875, 1671742800, 3341878155, 10081895040, 21210236775, 56710659600, 109876902975, 368709304320

Offset: 0

Alois P. Heinz, Nov 18 2007

nonn

a(n) is an integer multiple of n for all n>=1.
a(n) gives the number of complete binary trees on the n numbers from 1 to n (under the same definition of complete used for heaps) with the property that, at each node of the tree, each left descendant is less than each right descendant. For instance, for n=5, there are 15 such trees, determined by a choice of any value at the root and any of the three smallest remaining values as its left child. a(n) can be computed from an unlabeled complete tree on n nodes as the product of the numbers of descendants of each node (including the node itself). - David Eppstein, Mar 18 2016
a(n-1) gives 2 to the power of the minimal value of the s-shape statistic of rooted binary trees with n leaves. - Mareike Fischer, Aug 08 2025

			a(4) = 8 because 8 = 24/3 and there are 24 permutations on 4 elements, 3 of which are heaps, namely (1,2,3,4), (1,2,4,3) and (1,3,2,4). In every (min-) heap, the element at position i has to be larger than an element at position floor(i/2) for all i=2..n.

Alois P. Heinz, Table of n, a(n) for n = 0..2442
Olivier Bodini, Antoine Genitrini, Bernhard Gittenberger, Isabella Larcher, and Mehdi Naima, Compaction for two models of logarithmic-depth trees: Analysis and Experiments, arXiv:2005.12997 [math.CO], 2020.
Sean Cleary, Mareike Fischer, and Katherine St. John, The GFB Tree and Tree Imbalance Indices, arXiv:2502.12854 [q-bio.PE], 2025. See pp. 14, 16.
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap

Cf. A000142, A029837, A053644, A056971, A133385, A386912.

a:= proc(n) option remember; `if`(n=0, 1, (b-> (f->
      a(f)*n*a(n-1-f))(min(b-1, n-b/2)))(2^ilog2(n)))
    end:
seq(a(n), n=0..50);

a[n_] := a[n] = Module[{b, nl}, If[n<2, 1, b = 2^Floor[Log[2, n]]; nl = Min[b-1, n-b/2]; n*a[nl]*a[n-1-nl]]]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Mar 05 2014, after Alois P. Heinz *)

a(n) = n * a(f) * a(n-1-f) with f = min(b-1,n-b/2) and b = 2^floor(log_2(n)) for n>0, a(0) = 1.
a(n) = A000142(n)/A056971(n).
From Mareike Fischer, Aug 08 2025: (Start)
a(n-1) = Product_{i=2..n} (i-1)^q(n,i), with
  q(n,i) = floor(n/i)   if i=2^(k(i)) and ((n mod i)=0 or (n mod i) >= 2^(k(i)-1)),
         = floor(n/i)-1 if i=2^(k(i)) and (0 < (n mod i) < 2^(k(i)-1)),
         = 1 if (i != 2^(k(i)) and ( (n-i) mod 2^(k(i)-1)) = 0 ),
         = 0 if (i != 2^(k(i)) and ( (n-i) mod 2^(k(i)-1)) > 0 ) and
  k(n) = ceiling(log_2(n)) = A029837(n).
Or also, a(n-1) = Product_{i=0..k(n)-1} (2^(k(n)-i)-1)^(2^i) if d(n)=2^(k(n)-1). Else, a(n-1) = (Product_{i=0..k(n)-2} (2^(k(n)-i-1)-1)^(2^i)) * Product_{i=1..k(n)-1} ( ((2^(i+1)-1)/(2^i-1))^floor(d(n)/(2^i)) * ( ( 2^i + (d(n)-2^i*floor(d(n)/(2^i)))-1 ) / (2^i-1) )^(ceiling(d(n)/(2^i))-floor(d(n)/(2^i)))) if d(n) < 2^(k(n)-1), with k(n)=ceiling(log_2(n))= A029837(n) and d(n)=n-2^(k(n)-1). (End)

A178008 Number of permutations of 1..n with no element e[i>=2]

Original entry on oeis.org

1, 1, 1, 2, 6, 12, 40, 180, 630, 3360, 22680, 113400, 831600, 7484400, 38918880, 302702400, 2918916000, 20432412000, 205837632000, 2500927228800, 21598916976000, 263986763040000, 3837961401120000, 33774060329856000, 431557437548160000, 6658314750743040000

Offset: 0

R. H. Hardin, May 17 2010

nonn

a(n) is also the number of labeled histories for the trifurcating labeled topology that possesses the largest number of labeled histories, among all labeled topologies with 2n+1 leaves. - Noah A Rosenberg, Feb 24 2025

Alois P. Heinz, Table of n, a(n) for n = 0..502
E. H. Dickey, N. A. Rosenberg, Labelled histories with multifurcation and simultaneity, Phil. Trans. R. Soc. B 380 (2025), 20230307.
Wikipedia, D-ary heap

Simple 2-way heap A056971.

Column k=3 of A273693.

a(0), a(21)-a(25) from Alois P. Heinz, May 27 2016

Showing 1-10 of 66 results. Next

cp's OEIS Frontend

A309049 Number T(n,k) of (binary) max-heaps on n elements from the set {0,1} containing exactly k 0's; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

A306343 Number T(n,k) of defective (binary) heaps on n elements with k defects; triangle T(n,k), n>=0, 0<=k<=max(0,n-1), read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A273693 Number A(n,k) of k-ary heaps on n elements; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A373451 Number T(n,k) of (binary) heaps of length n whose element set equals [k]; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A056972 Number of (binary) heaps on n levels (i.e., of 2^n - 1 elements).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs