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
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;
...
-
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 *)
A323957
Number of defective (binary) heaps on n elements with exactly one defect.
Original entry on oeis.org
0, 1, 2, 9, 28, 90, 360, 1526, 7616, 32460, 190800, 947760, 6382464, 37065600, 296524800, 1812861600, 15283107840, 105015593280, 1017540576000, 7304720544000, 74472335308800, 629300251008000, 7429184791142400, 62417372203929600, 746041213793075200
Offset: 1
a(2) = 1: 12.
a(3) = 2: 213, 231.
a(4) = 9: 2413, 3124, 3214, 3241, 3412, 3421, 4123, 4132, 4213.
a(5) = 28: 25134, 25143, 35124, 35142, 35214, 35241, 42315, 42351, 43125, 43152, 43215, 43251, 43512, 43521, 45123, 45132, 45213, 45231, 45312, 45321, 52314, 52341, 52413, 52431, 53124, 53142, 53214, 53241.
a(6) = 90: 362451, 362541, 436125, 436215, ..., 652314, 652413, 653124, 653214.
(The examples use max-heaps.)
-
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:
a:= n-> coeff(b(n, 0), x, 1):
seq(a(n), n=1..25);
-
b[u_, o_] := b[u, o] = Module[{n = u+o, g, l}, If[n == 0, 1,
g = 2^(Length[IntegerDigits[n, 2]] - 1);
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]]];
a[n_] := Coefficient[b[n, 0], x, 1];
Array[a, 25] (* Jean-François Alcover, Apr 22 2021, after Alois P. Heinz *)
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
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.)
-
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 *)
Showing 1-3 of 3 results.
Comments