Задача на подсчет перестановок

[SiberianSemion]

Найти кол-во перестановок $a_1a_2\ldots a_n \in S_n,$ таких, что $|a_i-i|=0$ или $1.$

[eugensk]

(удалено, перепутал с ПРР)

[Pphantom]

Тема перемещена из форума «Олимпиадные задачи (М)» в форум «Карантин»
по следующим причинам:

- отсутствуют собственные содержательные попытки решения задачи (если Вы знаете, как решается задача, и хотите предложить ее для решения остальным участникам - пришлите решение модератору в ЛС).

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Pphantom]

Тема перемещена из форума «Карантин» в форум «Олимпиадные задачи (М)»
Причина переноса: поступило решение в ЛС.

[maxal]

Похожая задача у меня была в AMM под номером 11281 (в выпуске 114:3 за 2007 год). Только там $a_i-i$ принимает ровно два различных значения. И ответ, кстати, не зависит от самих этих значений.

[eugensk]

Раз я влез, не разобравшись, то должен был попытаться решить сам.

(мой ответ)

$ M(n) = M(n-1) + M(n-2), M(1) = 1, M(2) = 2$

[wrest]

SiberianSemion
Спасибо!

(Ответ)

Это ж... Лео П.

[SiberianSemion]

eugensk, совершенно верно!

(Оффтоп)

По-другому это числа Фибоначчи $F_{n+1}.$

Непосредственное развитие этой задачи:
Найти число перестановок $a_1a_2\ldots a_n \in S_n,$ таких, что $a_i-i \equiv 0,\pm 1 $ (mod $n$).

Это уже потруднее будет.

[Someone]

Я, конечно, могу ошибаться, но, по-моему, здесь моментально получаются числа Фибоначчи со сдвигом нумерации: число перестановок требуемого вида из $n$ элементов равно $F_{n+1}$. Например, для $n=4$ полeчаем $F_5=5$ перестановок: $1234$, $1243$, $1324$, $2134$, $2143$.

-- Пн апр 01, 2019 17:30:22 --

Ой, пока писал да внучке сказку читал, уже написали.

[wrest]

SiberianSemion в сообщении #1385321 писал(а):

Найти число перестановок $a_1a_2\ldots a_n \in S_n,$ таких, что $a_i-i \equiv 0,\pm 1 $ (mod $n$).

Можно пояснить, тут имеется в виду, что $a_i-i \equiv -1 (\mod n)$ это то же что и $a_i-i \equiv n-1 (\mod n)$?

[Someone]

SiberianSemion в сообщении #1385321 писал(а):

Найти число перестановок $a_1a_2\ldots a_n \in S_n,$ таких, что $a_i-i \equiv 0,\pm 1 $ (mod $n$).

Оказывается, тут новый вариант задачи появился.

wrest в сообщении #1385323 писал(а):

Можно пояснить, тут имеется в виду, что $a_i-i \equiv -1 (\mod n)$ это то же что и $a_i-i \equiv n-1 (\mod n)$?

Ну да, $n-1\equiv-1\pmod{n}$. В первой задаче была цепочка, теперь она замыкается в кольцо.

SiberianSemion в сообщении #1385321 писал(а):

Это уже потруднее будет.

Да нет, имея решение предыдущей задачи (почти очевидное), эта уже решается легко. Получается $F_{n-1}+F_{n+1}+2$ перестановки. Если не проврался, конечно.

[wrest]

Someone в сообщении #1385347 писал(а):

Получается $F_{n-1}+F_{n+1}+2$ перестановки. Если не проврался, конечно.

Да, у меня тоже так.

[Someone]

Поскольку тут возникли обиды на то, что задачу назвали простой, сопровождаемые требованием строго покарать обидчика, я изложу своё решение. Тем более, что после публикации ответа прошло уже больше трёх суток, и никто не захотел опубликовать решение.
Числа Фибоначчи я буду обозначать $F_n$, причём, $F_0=0$, $F_1=1$, $F_n=F_{n-1}+F_{n-2}$ при $n>1$ (это все знают, но могу же я позанудствовать; также из занудства я разжую всё настолько подробно, насколько у самого хватит терпения). Рассматриваются перестановки (упорядоченного) множества $I_n=(1,2,\ldots,n)$.

Первая задача.

Требуется подсчитать число перестановок $P\colon I_n\to I_n$, удовлетворяющих условию $\forall k\in I_n(\lvert Pk-k\rvert\leqslant 1)$.
Будем формулировать это условие в наглядных выражениях: каждый элемент сдвигается (вправо или влево) не более чем на $1$ шаг.
Число указанных перестановок множества $I_n$ будем обозначать, например, $S^I_n$. Естественно считать, что $S^I_0=S^I_1=1$, поэтому далее предполагаем, что $n>1$.

Посмотрим, могут ли два соседних элемента сдвинуться в одну сторону. При $n=2$ это, очевидно, невозможно, так как для этого просто нет места. При $n>2$ в результате сдвига на один шаг двух или более соседних элементов в одну сторону освобождается место, которое можно заполнить только встречным движением элемента, перепрыгивающего все указанные элементы, и этот элемент должен прыгнуть не менее чем на два шага, что противоречит условию. Поэтому перестановка должна выглядеть так: в множестве $I_n$ выбираются попарно не пересекающиеся пары элементов (от $0$ до $\left[\frac n2\right]$ штук), и в каждой паре элементы меняются местами.

Рассмотрим некоторую допустимую перестановку множества $I_n$, $n\geqslant 2$. В ней элемент $n$ либо остаётся на месте, либо меняется местами с элементом $n-1$.
В первом случае удалим элемент $n$ и получим допустимую перестановку множества $I_{n-1}$, по которой исходная перестановка множества $I_n$ восстанавливается однозначно. Следовательно, таких перестановок имеется $S^I_{n-1}$ штук.
Во вором случае удалим оба элемента $n$ и $n-1$ и получим допустимую перестановку множества $I_{n-2}$, по которой исходная перестановка множества $I_n$ восстанавливается однозначно. Следовательно, таких перестановок имеется $S^I_{n-2}$ штук.
Таким образом, получаем соотношение $S^I_n=S^I_{n-1}+S^I_{n-2}$, которое совпадает с рекуррентным соотношением для чисел Фибоначчи. Поскольку, как мы видели, $S^I_0=1=F_1$ и $S^I_1=1=F_2$, то $S^I_n=F_{n+1}$.

Ответ: $S^I_n=F_{n+1}$ при $n\geqslant 0$.

Вторая задача.

Рассматриваются перестановки того же множества $I_n$, но множество возможных сдвигов $P_k-k$ расширяется: теперь должно выполняться условие $\lvert Pk-k\rvert\in\{0,1,n-1\}$.
Наглядно это можно представлять себе так: множество $I_n$ замкнуто в кольцо, в связи с чем будем обозначать его $C_n$, подразумевая структуру кольца, и допустимы те и только те перестановки, в которых каждый элемент кольца сдвигается по кольцу не более, чем на один шаг.
Число таких перестановок будем обозначать $S^C_n$. Очевидно, что $S^C_0=S^I_0=F_1=1$, $S^C_1=S^I_1=F_2=1$, $S^C_2=S^I_2=F_3=2$.

Далее предполагаем, что $n\geqslant 3$.
Рассмотрим некоторую допустимую перестановку на кольце $C_n$.
Заметим, что если два каких-нибудь соседних элемента сдвигаются по кольцу на один шаг в одну сторону, то и все элементы сдвигаются на один шаг в ту же сторону (объяснение то же, что в первой задаче: элемент, перемещающийся по кольцу им навстречу, должен перепрыгнуть через все встречные элементы). Это даёт две перестановки, которые сдвигают все элементы кольца в одну сторону.
Если же в перестановке нет двух соседних элементов, сдвигающихся в одну сторону, то мы приходим к такой же структуре перестановки, как в первой задаче: на кольце выбрано некоторое количество попарно не пересекающихся пар соседних элементов (от $0$ до $\left[\frac n2\right]$), и в каждой паре элементы меняются местами.
Рассмотрим некоторую перестановку такого вида. В ней элемент $n$ либо остаётся на месте, либо меняется местами с элементом $n-1$, либо меняется местами с элементом $1$.
В первом случае удалим элемент $n$ и получим допустимую (в смысле первой задачи) перестановку множества $I_{n-1}$, по которой исходная перестановка множества $C_n$ восстанавливается однозначно. Следовательно, число перестановок такого вида равно $S^I_{n-1}=F_n$.
Во втором случае удалим элементы $n$ и $n-1$ и получим допустимую перестановку множества $I_{n-2}$, по которой исходная перестановка множества $C_n$ восстанавливается однозначно. Следовательно, число перестановок такого вида равно $S^I_{n-2}=F_{n-1}$.
В третьем случае удалим элементы $n$ и $1$, а значения всех оставшихся элементов уменьшим на $1$ (это я занудствую), что опять даст нам перестановку множества $I_{n-2}$, по которой исходная перестановка множества $C_n$ восстанавливается однозначно. Следовательно, число перестановок такого вида тоже равно $S^I_{n-2}=F_Хn-1}$.
Таким образом, получаем $S^C_n=2+F_n+F_{n-1}+F_{n-1}=F_{n+1}+F_{n-1}+2$.
Ответ: $S^C_n=\begin{cases}1\text{ при }n=0\text{ и при }n=1,\\ 2\text{ при }n=2,\\ F_{n+1}+F_{n-1}+2\text{ при }n\geqslant 3.\end{cases}$

Замечание. Как всегда, более или менее аккуратное изложение решения занимает гораздо больше времени, чем требуется для придумывания этого решения.