A389282 Total sum of lengths of the longest decreasing sequences in heapable permutations of length n.

1, 1, 3, 9, 36, 170, 965, 6313, 46987, 392093, 3632933, 37031537, 412058662, 4971801994, 64678909530

Offset

1,3

Comments

A permutation [1...n] is heapable if it can be sequentially inserted into a binary min-heap without violating the heap property.

The longest decreasing subsequence (LDS) of a heapable permutation is a subsequence of the given sequence in which the elements are in strictly decreasing order and the subsequence is as long as possible.

Links

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

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.

Manolopoulos Panagiotis, Python Program

Formula

a(n) = Sum_{k=1..n} k*A390146(n,k).

Example

For n=4 the heapable permutations and their LDS lengths:
  (1,2,3,4): LDS=1 (no decreasing pair).
  (1,3,2,4): LDS=2 (subsequence 3,2).
  (1,2,4,3): LDS=2 (subsequence 4,3).
  (1,4,2,3): LDS=2 (subsequence 4,2).
  (1,3,4,2): LDS=2 (subsequence 4,2).
So the total LDS-sum is 1*1+2*4=9.

Crossrefs

Cf. A336282, A386382, A390146.

Sequence in context: A032314 A144352 A107895 * A343579 A237653 A070960

Adjacent sequences: A389279 A389280 A389281 * A389283 A389284 A389285

Keyword

nonn,more

Author

Manolopoulos Panagiotis, Oct 31 2025

Extensions

a(11)-a(15) from Sean A. Irvine, Nov 03 2025

Status

approved