A091980 -id:A091980 - cp's OEIS frontend

A373449 Number A(n,k) of (binary) heaps of length n whose element set is a subset of [k]; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 3, 1, 0, 1, 4, 6, 5, 1, 0, 1, 5, 10, 14, 7, 1, 0, 1, 6, 15, 30, 25, 11, 1, 0, 1, 7, 21, 55, 65, 53, 16, 1, 0, 1, 8, 28, 91, 140, 173, 100, 26, 1, 0, 1, 9, 36, 140, 266, 448, 400, 222, 36, 1, 0, 1, 10, 45, 204, 462, 994, 1225, 1122, 386, 56, 1, 0

Offset: 0

Alois P. Heinz, Jun 05 2024

These heaps may contain repeated elements.

			A(3,1) = 1: 111.
A(3,2) = 5: 111, 211, 212, 221, 222.
A(3,3) = 14: 111, 211, 212, 221, 222, 311, 312, 313, 321, 322, 323, 331, 332, 333.
(The examples use max-heaps.)
Square array A(n,k) begins:
  1, 1,  1,   1,    1,     1,     1,     1,      1, ...
  0, 1,  2,   3,    4,     5,     6,     7,      8, ...
  0, 1,  3,   6,   10,    15,    21,    28,     36, ...
  0, 1,  5,  14,   30,    55,    91,   140,    204, ...
  0, 1,  7,  25,   65,   140,   266,   462,    750, ...
  0, 1, 11,  53,  173,   448,   994,  1974,   3606, ...
  0, 1, 16, 100,  400,  1225,  3136,  7056,  14400, ...
  0, 1, 26, 222, 1122,  4147, 12428, 32028,  73644, ...
  0, 1, 36, 386, 2336, 10036, 34242, 98922, 251922, ...

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

Columns k=0-2 give: A000007, A000012, A091980(n+1).
Rows n=0-6 give: A000012, A001477, A000217, A000330, A001296, A207361, A001249(k-1).
Main diagonal gives A373450.
Cf. A373451.

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

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

A(n,k) = Sum_{j=0..k} binomial(k,j) * A373451(n,k-j).

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

A336631 a(n) = 1 + Max_{0<=i<=j<=k; i+j+k=n-1} a(i)a(j)a(k) for n>0, with a(0) = 1.

Original entry on oeis.org

1, 2, 3, 5, 9, 13, 21, 37, 55, 91, 163, 244, 406, 730, 1054, 1702, 2998, 4456, 7372, 13204, 19765, 32887, 59131, 85411, 137971, 243091, 361351, 597871, 1070911, 1603081, 2667421, 4796101, 6927701, 11190901, 19717301, 29309501, 48493901, 86862701, 130027601

Offset: 0

Justin Dallant, Jul 28 2020

a(n) is the maximum number of antichains (including the empty antichain) among all posets of size n with a Hasse diagram corresponding to a ternary tree (each node has up to three children). Equivalently, a(n)-1 is the maximum number of subtrees containing the root among all ternary trees of size n.

a(n)^(1/n) converges, and the decimal expansion of the limit seems to start with 1.6296636...

			For n = 1 we have a(1) = 1 + a(0)*a(0)*a(0) = 1 + 1*1*1 = 2.
For n = 6 we have a(6) = 1 + a(1)*a(1)*a(3) = 1 + 2*2*5 = 21.
For n = 24 we have a(24) = 1 + a(4)*a(6)*a(13) = 1+9*21*730 = 137971.

Ternary version of A091980.

a(n) = 1 + Max_{0<=i<=j<=k; i+j+k=n-1} a(i)*a(j)*a(k) for n>0, a(0) = 1.

A379272 Number of binary min-heaps on n elements from the set {0,1} that give a max-heap when reversed.

Original entry on oeis.org

1, 2, 3, 4, 6, 8, 10, 14, 18, 22, 33, 40, 54, 74, 93, 116, 172, 204, 268, 378, 482, 584, 905, 1036, 1378, 1858, 2520, 3002, 4700, 5298, 7089, 9456, 12420, 15452, 24160, 26542, 36646, 47634, 64183, 75568, 126118, 135226, 188098, 244172, 329098, 383142, 626452, 689466, 980284, 1229296, 1691506

Offset: 0

Alois P. Heinz, Feb 18 2025

nonn

If n is odd then a(n) is even.

			a(5) = 8: 00000, 00001, 00011, 00101, 00111, 01011, 01111, 11111.
a(6) = 10: 000000, 000001, 000011, 000101, 000111, 001011, 001111, 010111, 011111, 111111. Min-heaps on 6 elements from the set {0,1} that do not give a max-heap when reversed are: 000010, 000100, 000110, 001001, 001101, 010110.
a(7) = 14: 0000000, 0000001, 0000011, 0000101, 0000111, 0001011, 0001111, 0010011, 0010111, 0011011, 0011111, 0101111, 0111111, 1111111.

Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap

Cf. A056971, A091980, A273755.

cp's OEIS Frontend

A373449 Number A(n,k) of (binary) heaps of length n whose element set is a subset of [k]; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

A336631 a(n) = 1 + Max_{0<=i<=j<=k; i+j+k=n-1} a(i)a(j)a(k) for n>0, with a(0) = 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A379272 Number of binary min-heaps on n elements from the set {0,1} that give a max-heap when reversed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

cp's OEIS Frontend

A373449 Number A(n,k) of (binary) heaps of length n whose element set is a subset of [k]; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

A336631 a(n) = 1 + Max_{0<=i<=j<=k; i+j+k=n-1} a(i)*a(j)*a(k) for n>0, with a(0) = 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A379272 Number of binary min-heaps on n elements from the set {0,1} that give a max-heap when reversed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A336631 a(n) = 1 + Max_{0<=i<=j<=k; i+j+k=n-1} a(i)a(j)a(k) for n>0, with a(0) = 1.