Number of permutations of set {1, 2, ..., n} for which insertion sort will perform exactly n permutations

Question

I have had the following problem at my last exam:

For how many permutations of set {1, 2, ..., n} where n > 2 will insertion sort (without guard element) perform exactly n comparisons.

My thinking was: there must be exactly one inversion of succeeding elements so any of the pairs (2, 3) or (3, 4) ... or (n-1, n) has to be swapped in the sorted sequence. So I answered n-2 because there's n-2 such pairs. But the answer was 2(n-1). Why?

Answer 1

Your analysis looks correct to me. The answer should be N-2, not 2(N-1).

It wouldn't be unheard of for graders/teachers to work with an incorrect solution.