A336282 - OEIS

%I #83 Nov 18 2020 10:23:59

%S 1,1,1,2,5,17,71,359,2126,14495,111921,966709,9243208,96991006,

%T 1108710232,13719469288,182771488479,2608852914820,39730632184343,

%U 643142016659417,11029056364607167,199761704824369543,3811075717138755529,76396392619230455931,1605504868758470118493

%N Number of heapable permutations of length n.

%C 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.

%C 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.

%C We notice that the number of equivalence classes at each step appears to follow A001006, but this has not yet been proven.

%H Mario Tutuncu-Macias, <a href="/A336282/b336282.txt">Table of n, a(n) for n = 0..29</a>

%H John Byers, Brent Heeringa, Michael Mitzenmacher, and Georgios Zervas, <a href="https://arxiv.org/abs/1007.2365">Heapable Sequences and Subsequences</a>, arXiv:1007.2365 [cs.DS], 2010.

%H G. Istrate and C. Bonchis, <a href="https://arxiv.org/abs/1502.02045">Partition into heapable sequences, heap tableaux and a multiset extension of Hammersley’s process</a>, arXiv:1502.02045 [math.CO], 2015.

%F Proven bounds:

%F A000111(n) <= a(n).

%F a(n) <= A102038(n-1) for n>1.

%e 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.

%o (Python)

%o from itertools import permutations

%o def isHeapable(seq):

%o     sig = [0 for _ in range(len(seq))]

%o     sig[0] = 2

%o     for j in seq[1:]:

%o         sig[j] = 2

%o         while j > -1:

%o             j -= 1

%o             if sig[j] > 0:

%o                 sig[j] -= 1

%o                 break

%o         if j == -1:

%o             return False

%o     return True

%o def A336282(n):

%o     if n == 0: return 1

%o     x = permutations(range(n))

%o     return sum(1 for h in x if isHeapable(h))

%o print([A336282(n) for n in range(12)])

%o (Python)

%o class EquivalenceClass:

%o     def __init__(self, example, count):

%o         self.example = example

%o         self.count = count

%o def extendedSig(seq, key, n):

%o     key = eval(key)

%o     top = seq.index(n - 1)

%o     attachement = top - 1

%o     for i in range(attachement, -1, -1):

%o         if key[i] > 0:

%o             key[i] -= 1

%o             key.insert(top, 2)

%o             return key

%o e_list = [{"[2]": EquivalenceClass([0], 1)}, {}]

%o def A(n):

%o     if n < 2:

%o         return 1

%o     el_0 = e_list[0]

%o     el = e_list[1]

%o     for key in el_0:

%o         seq = el_0[key].example

%o         for j in range(n - 1, 0, -1):

%o             p = seq[0:j] + [n - 1] + seq[j:]

%o             res = extendedSig(p, key, n)

%o             if not res:

%o                 break

%o             s = str(res)

%o             c = el_0[key].count

%o             if s in el:

%o                 el[s].count += c

%o             else:

%o                 el[s] = EquivalenceClass(p, c)

%o     e_list[0] = el

%o     e_list[1] = {}

%o     return sum(el[key].count for key in el)

%o def A336282List(size):

%o     return [A(k) for k in range(size)]

%o print(A336282List(12))

%Y Cf. A056971, A000111, A102038, A001006.

%K nonn

%O 0,4

%A _Benjamin Chen_, _Michael Y. Cho_, _Mario Tutuncu-Macias_, _Tony Tzolov_, Jul 15 2020

%E a(14) from _Seiichi Manyama_, Jul 20 2020

%E a(15)-a(20) from _Mario Tutuncu-Macias_, Jul 22 2020

%E Extended beyond a(20) by _Mario Tutuncu-Macias_, Oct 27 2020