Thinking...

The problem is meaningful only for n >= 4.

For n = 4, there are 6 possible permutations: (1, 2, 3, 4), (1, 3, 2, 4), (1, 3, 4, 2), (3, 4, 1, 2), (3, 1, 4, 2) and (3, 1, 2, 4).

For n = 5, '5' can go into any of the five 'gaps'. There are 5*6 = 30 possible permutations.

The numbers greater than 4 will have to placed into some or all of the five 'gaps'.