Permutazioni al minimo di scambi nell'heapsort (n=9)

Il seguente heapsort ordina in senso crescente un array $A$, prima costruendo uno max-heap e poi estraendo ripetutamente il massimo:

# sift_down(A, start, end): fa scendere A[start] scambiandolo col figlio
# maggiore finché non è più piccolo di un figlio; ogni scambio A[i] con A[j]
# conta come UNO scambio

for start from n//2 - 1 down to 0:
    sift_down(A, start, n-1)          # costruzione dello heap iniziale

for end from n-1 down to 1:
    swap(A[0], A[end])                # sposta il massimo in fondo: 1 scambio
    sift_down(A, 0, end-1)

Considera tutti i possibili array $A$ di $9$ elementi distinti. Per quanti di essi il numero totale di scambi (costruzione dello heap più fase di estrazione) raggiunge il valore minimo possibile su tutta l'esecuzione?