A389993 Triangle read by rows: T(n,k) = number of heapable permutations of length n with exactly k consecutive pairs.

1, 0, 1, 0, 1, 1, 0, 3, 1, 1, 2, 4, 8, 2, 1, 7, 22, 22, 17, 2, 1, 38, 100, 119, 70, 28, 3, 1, 225, 588, 665, 443, 159, 42, 3, 1, 1543, 3934, 4464, 2951, 1231, 308, 59, 4, 1, 11954, 29961, 33936, 22788, 9851, 2829, 518, 79, 4, 1

Offset

1,8

Comments

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

A consecutive pair is a pair of adjacent entries (p(i),p(i+1)) such that |p(i)-p(i+1)|=1.

Links

Sean A. Irvine, Table of n, a(n) for n = 1..120 (rows 1..15 flattened)

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

Example

Triangle begins:
  1
  0, 1
  0, 1, 1
  0, 3, 1, 1
  2, 4, 8, 2, 1
  7, 22, 22, 17, 2, 1
  38, 100, 119, 70, 28, 3, 1
  225, 588, 665, 443, 159, 42, 3, 1
  1543, 3934, 4464, 2951, 1231, 308, 59, 4, 1
  11954, 29961, 33936, 22788, 9851, 2829, 518, 79, 4, 1
  ...

Crossrefs

Cf. A336282 (row sums), A386382 (runs), A389792 (ascents), A389991 (descents).

Sequence in context: A306438 A221978 A035254 * A143934 A318442 A086639

Adjacent sequences: A389990 A389991 A389992 * A389994 A389995 A389996

Keyword

nonn,tabl

Author

Manolopoulos Panagiotis, Oct 21 2025

Status

approved