A388139 Total number of fixed points in all heapable permutations of length n.

1, 2, 4, 10, 35, 150, 763, 4538, 31099, 240998, 2086861, 19995764, 210178054, 2405810764, 29802767812, 397387258762

Offset

1,2

Comments

A permutation is heapable if it can be inserted into a binary min-heap by the usual insertion process without violating the heap property.

A fixed point of a permutation p is an index i such that p(i) = i.

Links

Table of n, a(n) for n=1..16.

Benjamin Chen, Michael Cho, Mario Tutuncu-Macias, and Tony Tzolov, Efficient methods of calculating the number of heapable permutations, Discrete Applied Mathematics Volume 331, 31 May 2023, 126-137.

Manolopoulos Panagiotis, Python program

Wikipedia, Binary heap

Example

For n=4, the heapable permutations are (1,2,3,4), (1,2,4,3), (1,3,2,4), (1,3,4,2), (1,4,2,3).
Their fixed points are:
  (1,2,3,4): {1,2,3,4}, 4 fixed points;
  (1,2,4,3): {1,2}, 2 fixed points;
  (1,3,2,4): {1,4}, 2 fixed points;
  (1,3,4,2): {1}, 1 fixed point;
  (1,4,2,3): {1}, 1 fixed point.
a(4) = 10 since the total number of fixed points is 4 + 2 + 2 + 1 + 1 = 10.

Crossrefs

Cf. A336282 (number of heapable permutations), A000142 (total number of fixed points in all permutations), A388136, A386382.

Sequence in context: A189591 A189598 A156800 * A210772 A125859 A103854

Adjacent sequences: A388136 A388137 A388138 * A388140 A388141 A388142

Keyword

nonn,more

Author

Manolopoulos Panagiotis, Sep 15 2025

Extensions

a(12)-a(15) from Sean A. Irvine, Sep 26 2025

a(16) from Sean A. Irvine, Oct 14 2025

Status

approved