Bubble sort in esattamente 3 passate su 6 elementi

Bubble sort esegue passate complete da sinistra a destra (confronta le coppie adiacenti e scambia se fuori ordine) e termina quando una passata intera non effettua scambi; anche l'ultima passata senza scambi viene contata, così l'array già ordinato richiede 1 passata.

Quante permutazioni di (1, 2, ..., 6) vengono ordinate in esattamente 3 passate?