A324068
Number of defective (binary) heaps on n elements where seven ancestor-successor pairs do not have the correct order.
Original entry on oeis.org
0, 0, 0, 0, 0, 0, 60, 640, 5040, 39424, 315840, 2572800, 22730400, 207820800, 1979577600, 20119756800, 180756576000, 1740900761600, 17732095180800, 197872975872000, 2123068147200000, 24858537099264000, 303091124244480000, 4076808466857984000
Offset: 0
A324069
Number of defective (binary) heaps on n elements where eight ancestor-successor pairs do not have the correct order.
Original entry on oeis.org
0, 0, 0, 0, 0, 0, 20, 480, 4830, 40320, 346080, 3014400, 28036800, 271180800, 2723635200, 28751923200, 273405132000, 2754444492800, 29222409216000, 335670386688000, 3786723502848000, 45941770321920000, 580488335032320000, 8000481890598912000
Offset: 0
A324070
Number of defective (binary) heaps on n elements where nine ancestor-successor pairs do not have the correct order.
Original entry on oeis.org
0, 0, 0, 0, 0, 0, 0, 240, 4200, 39424, 359520, 3340800, 32630400, 331499520, 3503385600, 38504294400, 386486100000, 4064835174400, 44847772569600, 530121646080000, 6258102529536000, 78618109870080000, 1027628834918400000, 14504975258222592000
Offset: 0
A324071
Number of defective (binary) heaps on n elements where ten ancestor-successor pairs do not have the correct order.
Original entry on oeis.org
0, 0, 0, 0, 0, 0, 0, 80, 3150, 36736, 359520, 3532800, 36115200, 383708160, 4247443200, 48673996800, 515675160000, 5654852403200, 64785924403200, 788119068672000, 9695238119424000, 125961866477568000, 1700829800017920000, 24580421999198208000
Offset: 0
A373496
Number of (binary) heaps with element set [n] and length n+1.
Original entry on oeis.org
0, 1, 3, 7, 23, 70, 320, 985, 4690, 19600, 121920, 549600, 3775200, 21964800, 186700800, 983954400, 7898290400, 53301248000, 523712716800, 3600440064000, 37065077913600, 315001589760000, 3848127528960000, 30288467049984000, 357688760600371200, 3481899302289408000
Offset: 0
a(1) = 1: 11.
a(2) = 3: 211, 212, 221.
a(3) = 7: 3121, 3211, 3212, 3221, 3231, 3312, 3321.
a(4) = 23: 42311, 42312, 42321, 43112, 43121, 43122, 43123, 43132, 43211, 43212, 43213, 43221, 43231, 43312, 43321, 43412, 43421, 44123, 44132, 44213, 44231, 44312, 44321.
(The examples use max-heaps.)
Cf.
A056971 (without repeated elements).
-
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:
a:= n-> add(binomial(n, j)*(-1)^j*b(n+1, n-j), j=0..n):
seq(a(n), n=0..29);
A373500
Number of (binary) heaps of length 2n whose element set equals [n].
Original entry on oeis.org
1, 1, 5, 55, 1004, 27456, 1077657, 59699950, 3944644671, 319905929418, 32390662046661, 4181039787994506, 602128996908467070, 102537208988632300118, 20497804459093071390108, 4978144718604701947160364, 1232227300264551117529973052, 335016989869301170468736520008
Offset: 0
a(0) = 1: the empty heap.
a(1) = 1: 11.
a(2) = 5: 2111, 2121, 2211, 2212, 2221.
a(3) = 55: 312111, 312112, 313112, 321111, ..., 333221, 333231, 333312, 333321.
a(4) = 1004: 41311121, 41311211, 41311221, 41311231, ... 44444213, 44444231, 44444312, 44444321.
(The examples use max-heaps.)
-
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:
a:= n-> add(binomial(n, j)*(-1)^j*b(2*n, n-j), j=0..n):
seq(a(n), n=0..17);
A246829
The number of binary heaps on n elements whose breadth-first search reading word avoids 321.
Original entry on oeis.org
1, 1, 2, 3, 7, 16, 45, 111, 318, 881, 2686, 8033, 25470, 80480, 263977, 862865, 2891344, 9706757, 33178076, 113784968, 395303480, 1379160685, 4859274472, 17195407935, 61310096228, 219520467207, 790749207801, 2859542098634, 10391610220375, 37897965144166
Offset: 1
A heap on 4 elements is pictured in the 2nd link, and has breadth first reading word abcd. Then for n = 4 the a(4) = 3 heaps have reading words 1234, 1243, and 1324.
- D. Levin, L. Pudwell, M. Riehl, A. Sandberg, Pattern Avoidance on k-ary Heaps, Slides of Talk, 2014. [broken link]
- Manda Riehl (joint work with Derek Levin, Lara Pudwell, and Adam Sandberg), Page 92 of the Permutation Patterns 2014 Abstract Book
- Eric Weisstein's World of Mathematics, Heap
A273754
Number of binary heaps on [n] that give a heap when the first element is removed.
Original entry on oeis.org
1, 1, 1, 2, 3, 8, 18, 70, 180, 770, 2610, 14570, 54720, 330960, 1562814, 11946080, 57126780, 429542960, 2465050968, 22517159760
Offset: 1
There are 3 (min) heaps for n=4: 1234, 1243, 1324. When the first element is removed only 2 heaps remain: 234, 243. Thus a(4) = 2.
a(5) = 3: 12345, 12354, 12435.
a(6) = 8: 123456, 123465, 123546, 123564, 123645, 123654, 124356, 124365.
A336282
Number of heapable permutations of length n.
Original entry on oeis.org
1, 1, 1, 2, 5, 17, 71, 359, 2126, 14495, 111921, 966709, 9243208, 96991006, 1108710232, 13719469288, 182771488479, 2608852914820, 39730632184343, 643142016659417, 11029056364607167, 199761704824369543, 3811075717138755529, 76396392619230455931, 1605504868758470118493
Offset: 0
For n=4, the 5 heapable sequences are (1,2,3,4), (1,2,4,3), (1,3,2,4), (1,3,4,2), (1,4,2,3). Notice that (1,4,3,2) is missing.
- Mario Tutuncu-Macias, Table of n, a(n) for n = 0..29
- John Byers, Brent Heeringa, Michael Mitzenmacher, and Georgios Zervas, Heapable Sequences and Subsequences, arXiv:1007.2365 [cs.DS], 2010.
- G. Istrate and C. Bonchis, Partition into heapable sequences, heap tableaux and a multiset extension of Hammersley’s process, arXiv:1502.02045 [math.CO], 2015.
-
from itertools import permutations
def isHeapable(seq):
sig = [0 for _ in range(len(seq))]
sig[0] = 2
for j in seq[1:]:
sig[j] = 2
while j > -1:
j -= 1
if sig[j] > 0:
sig[j] -= 1
break
if j == -1:
return False
return True
def A336282(n):
if n == 0: return 1
x = permutations(range(n))
return sum(1 for h in x if isHeapable(h))
print([A336282(n) for n in range(12)])
-
class EquivalenceClass:
def _init_(self, example, count):
self.example = example
self.count = count
def extendedSig(seq, key, n):
key = eval(key)
top = seq.index(n - 1)
attachement = top - 1
for i in range(attachement, -1, -1):
if key[i] > 0:
key[i] -= 1
key.insert(top, 2)
return key
e_list = [{"[2]": EquivalenceClass([0], 1)}, {}]
def A(n):
if n < 2:
return 1
el_0 = e_list[0]
el = e_list[1]
for key in el_0:
seq = el_0[key].example
for j in range(n - 1, 0, -1):
p = seq[0:j] + [n - 1] + seq[j:]
res = extendedSig(p, key, n)
if not res:
break
s = str(res)
c = el_0[key].count
if s in el:
el[s].count += c
else:
el[s] = EquivalenceClass(p, c)
e_list[0] = el
e_list[1] = {}
return sum(el[key].count for key in el)
def A336282List(size):
return [A(k) for k in range(size)]
print(A336282List(12))
A178012
Number of permutations of 2 copies of 1..n with no element e[i>=2]
Original entry on oeis.org
1, 2, 7, 44, 394, 5160, 95772, 2070282, 54033576, 1768770384, 74057667588, 3481862274120
Offset: 1
Comments