login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
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.
FORMULA
Proven bounds:
A000111(n) <= a(n).
a(n) <= A102038(n-1) for n>1.
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
Sequence in context: A084869 A101900 A005966 * A082282 A005967 A369402
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 03:28 EDT 2024. Contains 371235 sequences. (Running on oeis4.)