A390450 Sum of indices of the positions of 2 in all heapable permutations of length n (positions starting from 0).

0, 1, 3, 9, 35, 162, 891, 5664, 41061, 334675, 3034176, 30311763, 331074965, 3926884061, 50284845273, 691632150641

Offset

1,3

Comments

A permutation is heapable if its elements can be inserted into a binary min-heap in breadth-first order without violating the heap property.

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

Manolopoulos Panagiotis, Python file

Example

For n=4: There are 5 heapable permutations: (1,2,3,4), (1,2,4,3), (1,3,2,4), (1,3,4,2), (1,4,2,3). Positions of element 2 (0-based): 1,1,2,3,2. Their sum = 9.

Crossrefs

Cf. A336282 (number of heapable permutations), A390377 (triangle of positions of 2), A390368 (removals from start to become heapable), A390146 (triangle of longest decreasing runs).

Sequence in context: A370341 A101880 A222398 * A107894 A155858 A000834

Adjacent sequences: A390447 A390448 A390449 * A390451 A390452 A390453

Keyword

nonn,more

Author

Manolopoulos Panagiotis, Nov 06 2025

Extensions

a(12)-a(16) from Sean A. Irvine, Nov 12 2025

Status

approved