"Сорок одно число"

[ERoznat]

Вспомнилась одна интересная задача, которую разбирали в школе в конце девяностых. Придумал её наш учитель, которого, увы, уже нет в живых.
Дано 41 число: 1, 2, ..., 41. Числа от 2 до 41 переставили, а число 1 осталось на своём месте. Известно, что в получившейся последовательности чисел разность между любыми двумя соседними числами равна одному или двум. Сколько перестановок удовлетворяют условию задачи?

Очевидно, что на втором месте будет 2 (тогда на третьем 3 или 4) или 3 (на третьем 2, 4 или 5). Но как двигаться дальше? Был бы признателен за помощь.

[user14284]

Если некоторые числа переставились на своё же место, это считается "перестановкой" в вашем смысле?

[ERoznat]

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

[user14284]

Почему

ERoznat в сообщении #1171480 писал(а):

Очевидно, что на втором месте будет 2

UPD. Извиняюсь, я сначала не заметил "или 3" у вас.

[ERoznat]

Я руководствуюсь тем, что на первом месте осталась единица. Так как разность между двумя соседними числами 2 или 1, то на второй позиции будет 2 или 3. Числа от 4 до 41 условию задачи не удовлетворяют.

[user14284]

Можно рекуррентное соотношение выписать (оно линейное). А потом посчитать на компьютере (6585451).

[ERoznat]

Я, увы, обучался в классе с уклоном на физмат, но жизнь связал с экологией.
Можете объяснить на примере, допустим, с аналогичным условием, но для 51 числа, а не для 41, как составляется реккурентное соотношение для таких задач?

[user14284]

Тут всё одинаково для 31, 41 и $n$. Грэхем, Кнут и Поташник написали одну известную книгу, которую вы легко найдете в интернетах, и начинается она с уроков "на пальцах", как составлять рекуррентные соотношения.

[gris]

В изначальной строке без единицы можно выделить произвольное число несоприкасающихся пар и перевернуть их:
$123456789... \to 132457689...$

[DeBill]

ERoznat в сообщении #1171480 писал(а):

что на втором месте будет 2

и мы получили ровно такую же задачу, но с 40 числами.

ERoznat в сообщении #1171480 писал(а):

или 3

Но где же тогда 2?
Она - либо следующая , и тогда далее - 4, и опять получилась такая же задача - но для 38,
либо она - в конце (ибо у нее остался токо один "допустимый сосед"). Но тогда - чтоб не было перескоков больших - все однозначно: в начале возрастая идут нечетные, а затем - убывая - четные.
Вместе это и даст рек. соотношения, о которых грит user14284
К сожалению, явной формулы - не получим: у соответствующего кубического ур-я - плохие корни...

[ERoznat]

Хорошо.
Соответственно, вероятность такого события будет равна, как я понимаю, $6585451/((n-1)!)$ ?

[user14284]

Какого события и при чём тут вероятность?

[ERoznat]

user14284 в сообщении #1171688 писал(а):

Какого события и при чём тут вероятность?

Ну давайте так сформулирую. Дана последовательность из 41 числа, перемешали так же, как и выше, 40 чисел от 2 до 41. Пусть событие К - после перемешивания чисел разность между двумя любыми соседними числами не более двух. Будет ли равно P(K) тому выражению, которое я изложил выше?

[user14284]

Да, если $n=41$.