|
|
A336282
|
|
Number of heapable permutations of length n.
|
|
1
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
FORMULA
|
Proven bounds:
|
|
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
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
|
|
|
STATUS
|
approved
|
|
|
|