Michael Y. Cho - cp's OEIS frontend

User: Michael Y. Cho

Michael Y. Cho has authored 1 sequences.

A336282 Number of heapable permutations of length n.

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

Benjamin Chen, Michael Y. Cho, Mario Tutuncu-Macias, Tony Tzolov, Jul 15 2020

nonn

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.

			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.

Cf. A056971, A000111, A102038, A001006.

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))

Proven bounds:
A000111(n) <= a(n).
a(n) <= A102038(n-1) for n>1.

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

cp's OEIS Frontend

User: Michael Y. Cho

A336282 Number of heapable permutations of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Python

Formula

Extensions