Пусть у нас есть набор чисел 1, 2, ..., N
Общеизвестно, что с помощью них можно составить ровно N! перестановок.

Перестановку назовем сильно перемешанной, если для любого числа K (0<K<N) следующее за ним число в ней (если такое есть) отлично от K+1.

Вопрос: Сколько всего сильно перемешанных перестановок? Желательно формулу от N

N = до+X+Y+Я

(1) порвало!

(1) http://img.artlebedev.ru/kovodstvo/idioteka/i/AF65E8A9-5B07-45B4-986E-90F1001DA180.jpg

Пусть
F(N) - искомая функция
Q(N) - количество перестановок, где РОВНО одна пара чисел удовлетворяет условию A[k+1] = A[k] + 1.

Тогда
F(N+1) = N*F(N) + Q(N)
Q(N+1) = F(N) + (N-1)*Q(N)

F(2) = 1
Q(2) = 1

Нерекурсивная формула вряд ли существует.

(4) ну вот я тоже примерно так думал, только формула Q(N+1) = F(N) + (N-1)*Q(N) неверна
в итоге при N=5 получаем F(5) = 51, а на самом деле 53

(4) А если 2 пары или 3 пары?

(53) выведи эти 53 варианта, надо увидеть

Но идея правильная
Пусть F(R,N) - количество перестановок на N элементах, где РОВНО R пар числе удовлетворяют условию: A[k+1] = A[k] + 1
Тогда функции из (4) это:
F(N) = F(0,N)
Q(N) = F(1,N)

рекурсивные формулы:
F(0,N+1) = N*F(0,N) + F(1,N)
F(R,N+1) = F(R-1,N) + (N-R)*F(R,N) + F(R+1,N) при R>0

(7) лови:

5
1 3 2 5 4
1 3 5 2 4
1 3 5 4 2
1 4 2 5 3
1 4 3 2 5
1 4 3 5 2
1 5 2 4 3
1 5 3 2 4
1 5 4 3 2
2 1 3 5 4
2 1 4 3 5
2 1 5 4 3
2 4 1 3 5
2 4 1 5 3
2 4 3 1 5
2 4 3 5 1
2 5 1 4 3
2 5 3 1 4
2 5 4 1 3
2 5 4 3 1
3 1 4 2 5
3 1 5 2 4
3 1 5 4 2
3 2 1 5 4
3 2 4 1 5
3 2 5 1 4
3 2 5 4 1
3 5 1 4 2
3 5 2 1 4
3 5 2 4 1
3 5 4 2 1
4 1 3 2 5
4 1 3 5 2
4 1 5 3 2
4 2 1 3 5
4 2 1 5 3
4 2 5 1 3
4 2 5 3 1
4 3 1 5 2
4 3 2 1 5
4 3 2 5 1
4 3 5 2 1
5 1 3 2 4
5 1 4 3 2
5 2 1 4 3
5 2 4 1 3
5 2 4 3 1
5 3 1 4 2
5 3 2 1 4
5 3 2 4 1
5 4 1 3 2
5 4 2 1 3
5 4 3 2 1
53

+(8) поправка:

рекурсивные формулы:
F(0,N+1) = N*F(0,N) + F(1,N)
F(R,N+1) = F(R-1,N) + (N-R)*F(R,N) + (R+1)*F(R+1,N) при R>0

(10) да, согласен
двух слагаемых недостаточно

интересно, что доля таких перестановок очень слабо убывает и ~0.37
Похоже, что предел F(0,N) равен N!/e

а оказалось все гораздо проще:
F(1,N+1) = N*F(0,N)
Отсюда получаем:
F(0,N+1) = N*F(0,N) + F(1,N) = N*F(0,N) + (N-1)*F(0,N-1)

или если искомую функцию F(0,N) обозначать просто F(N):
F(N+1) = N*F(N) + (N-1)*F(N-1)
правда окончательно от рекурсии, скорее всего, никуда не деться

http://oeis.org/A000255