OFFSET
0,4
COMMENTS
A permutation is heapable if there exists a binary heap with the numbers added to the heap in the order of the permutation, and you may not change already placed numbers.
We provide two programs: The first, given below in the Python section, demonstrates the notion of 'heapable'. It is, however, of big O roughly n!. A second program, given in the Links section, groups heapable sequences into equivalence classes using an extended signature. The big O of this algorithm is roughly 3^n.
We notice that the number of equivalence classes at each step appears to follow A001006, but this has not yet been proven.
LINKS
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.
EXAMPLE
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.
PROG
(Python)
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)])
(Python)
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))
CROSSREFS
KEYWORD
nonn
AUTHOR
EXTENSIONS
a(14) from Seiichi Manyama, Jul 20 2020
a(15)-a(20) from Mario Tutuncu-Macias, Jul 22 2020
Extended beyond a(20) by Mario Tutuncu-Macias, Oct 27 2020
STATUS
approved