A389232 Total number of decreasing runs in all heapable permutations of length n.

1, 2, 5, 16, 64, 309, 1762, 11612, 87053, 732514, 6843547, 70340402, 789273399, 9604401877, 126021340536, 1774093497373

Offset

1,2

Comments

A permutation of [1..n] is heapable if it can be inserted, one element at a time, into a binary min-heap without violating the heap property.

A decreasing run in a permutation is a maximal contiguous subsequence that is strictly decreasing. For example, in the permutation (3,1,4,2) the decreasing runs are (3,1) and (4,2).

Links

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

Manolopoulos Panagiotis, Python program.

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, Pages 126-137.

Example

For n=4, the heapable permutations are:
  (1,2,3,4): runs (1),(2),(3),(4) => 4 decreasing runs.
  (1,3,2,4): runs (1), (3,2), (4) => 3 decreasing runs.
  (1,2,4,3): runs (1),(2), (4,3) => 3 decreasing runs.
  (1,4,2,3): runs (1), (4,2), (3) => 3 decreasing runs.
  (1,3,4,2): runs (1),(3),(4,2) => 3 decreasing run.
So among the 5 heapable permutations of length 4:
  1 permutations have 4 decreasing run,
  4 permutations have 3 decreasing runs,
  for a total of 16 decreasing runs.

Crossrefs

Cf. A336282 (number of heapable permutations), A386382 (for runs), A389256 (for increasing runs), A389255.

Sequence in context: A185998 A127083 A131178 * A003149 A027046 A369775

Adjacent sequences: A389229 A389230 A389231 * A389233 A389234 A389235

Keyword

nonn,more

Author

Manolopoulos Panagiotis, Sep 26 2025

Extensions

a(11)-a(15) from Sean A. Irvine, Oct 06 2025

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

Status

approved