Спасибо за ответы. Конечно я пробовала вычислить распределение для разных значений числа

. Но не удается понять закономерность для

в середине распределения. Как отметил
gris,

и такое значение

будет принимать два раза, в случае, когда числа в перестановке расположены по убыванию или возрастанию. Далее, если за исходную перестановку взять

, то путем перестановки первых двух чисел или последних двух, получим

, что можно сделать и с обратной перестановкой

. Таким образом, число случаев, когда

. А вот с максимальным значением не все так просто. Для

последовательность случаев, когда S принимает максимальное значение, такова:

.
Здесь
http://dl.dropbox.com/u/17459017/9.xlsx расчитанные распределения для N от 3 до 9.
Спасибо большое за упоминание OEIS. Действительно максимальные значения выводятся по формуле

.