cp's OEIS Frontend

A336282 Number of heapable permutations of length n.

%I A336282 #83 Nov 18 2020 10:23:59
%S A336282 1,1,1,2,5,17,71,359,2126,14495,111921,966709,9243208,96991006,
%T A336282 1108710232,13719469288,182771488479,2608852914820,39730632184343,
%U A336282 643142016659417,11029056364607167,199761704824369543,3811075717138755529,76396392619230455931,1605504868758470118493
%N A336282 Number of heapable permutations of length n.
%C A336282 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 A336282 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 A336282 We notice that the number of equivalence classes at each step appears to follow A001006, but this has not yet been proven.
%H A336282 Mario Tutuncu-Macias, <a href="/A336282/b336282.txt">Table of n, a(n) for n = 0..29</a>
%H A336282 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 A336282 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 A336282 Proven bounds:
%F A336282 A000111(n) <= a(n).
%F A336282 a(n) <= A102038(n-1) for n>1.
%e A336282 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 A336282 (Python)
%o A336282 from itertools import permutations
%o A336282 def isHeapable(seq):
%o A336282     sig = [0 for _ in range(len(seq))]
%o A336282     sig[0] = 2
%o A336282     for j in seq[1:]:
%o A336282         sig[j] = 2
%o A336282         while j > -1:
%o A336282             j -= 1
%o A336282             if sig[j] > 0:
%o A336282                 sig[j] -= 1
%o A336282                 break
%o A336282         if j == -1:
%o A336282             return False
%o A336282     return True
%o A336282 def A336282(n):
%o A336282     if n == 0: return 1
%o A336282     x = permutations(range(n))
%o A336282     return sum(1 for h in x if isHeapable(h))
%o A336282 print([A336282(n) for n in range(12)])
%o A336282 (Python)
%o A336282 class EquivalenceClass:
%o A336282     def __init__(self, example, count):
%o A336282         self.example = example
%o A336282         self.count = count
%o A336282 def extendedSig(seq, key, n):
%o A336282     key = eval(key)
%o A336282     top = seq.index(n - 1)
%o A336282     attachement = top - 1
%o A336282     for i in range(attachement, -1, -1):
%o A336282         if key[i] > 0:
%o A336282             key[i] -= 1
%o A336282             key.insert(top, 2)
%o A336282             return key
%o A336282 e_list = [{"[2]": EquivalenceClass([0], 1)}, {}]
%o A336282 def A(n):
%o A336282     if n < 2:
%o A336282         return 1
%o A336282     el_0 = e_list[0]
%o A336282     el = e_list[1]
%o A336282     for key in el_0:
%o A336282         seq = el_0[key].example
%o A336282         for j in range(n - 1, 0, -1):
%o A336282             p = seq[0:j] + [n - 1] + seq[j:]
%o A336282             res = extendedSig(p, key, n)
%o A336282             if not res:
%o A336282                 break
%o A336282             s = str(res)
%o A336282             c = el_0[key].count
%o A336282             if s in el:
%o A336282                 el[s].count += c
%o A336282             else:
%o A336282                 el[s] = EquivalenceClass(p, c)
%o A336282     e_list[0] = el
%o A336282     e_list[1] = {}
%o A336282     return sum(el[key].count for key in el)
%o A336282 def A336282List(size):
%o A336282     return [A(k) for k in range(size)]
%o A336282 print(A336282List(12))
%Y A336282 Cf. A056971, A000111, A102038, A001006.
%K A336282 nonn
%O A336282 0,4
%A A336282 _Benjamin Chen_, _Michael Y. Cho_, _Mario Tutuncu-Macias_, _Tony Tzolov_, Jul 15 2020
%E A336282 a(14) from _Seiichi Manyama_, Jul 20 2020
%E A336282 a(15)-a(20) from _Mario Tutuncu-Macias_, Jul 22 2020
%E A336282 Extended beyond a(20) by _Mario Tutuncu-Macias_, Oct 27 2020