Математикадан облыстық олимпиада, 2014-2015 оқу жылы, 11 сынып

$\left( 1,2,\ldots ,n \right)$ жиынының ${{x}_{i}} < {{x}_{i+2}}$ ($1\le i\le n-2$ үшін) және ${{x}_{i}} < {{x}_{i+3}}$ ($1\le i\le n-3$ үшін) шарттары орындалатындай $\left( {{x}_{1}},{{x}_{2}},\ldots ,{{x}_{n}} \right)$ ауыстырылымдарының санын табыңыз. Бұл жерде $n\ge 4$.

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Ответ. $\dfrac{1}{{\sqrt 5 }}\left( {{{\left( {\dfrac{{1 + \sqrt 5 }}{2}} \right)}^{n+1}} - {{\left( {\dfrac{{1 - \sqrt 5 }}{2}} \right)}^{n+1}}} \right)$ ($(n+1)$-ое число Фибоначчи).
Решение. Обозначим через $f(n)$ число перестановок $(1,2,\ldots ,n)$, удовлетворяющих условию задачи. Тогда нетрудно расширить область определения и посчитать начальные значения $f(1)=1$, $f(2)=2$, $f(3)=3$, $f(4)=5$, $\dots$. Докажем, что $f(k)=f(k-1)+f(k-2)$. Действительно, в перестановках чисел от 1 до $k$, число $k$ может стоять на последнем или предпоследнем местах, так как в противном случае оно окажется меньше числа, стоящего через одну позицию после него.
Если число $k$ стоит на последнем месте, то предыдущие $k-1$ чисел образуют последовательность, удовлетворяющую условию задачи, а таких последовательностей $f(k-1)$.
Если число $k$ стоит на предпоследнем месте, то число $k-1$ может стоять только на последнем месте, так как в противном случае число, стоящее правее от него через одну или две позиции, окажется меньше него. Тогда числа от 1 до $k-2$ образуют последовательность, удовлетворяющую условию задачи, а таких последовательностей $f(k-2)$.
Так как все полученные последовательности различны и образуют все множество возможных перестановок, то их общее количество равно $f(k-1)+f(k-2)$. Заметим, что полученная последовательность образует последовательность Фибоначчи со сдвигом, то есть $f(n)={{f}_{n+1}}= \dfrac{1}{{\sqrt 5 }}\left( {{{\left( {\dfrac{{1 + \sqrt 5 }}{2}} \right)}^{n+1}} - {{\left( {\dfrac{{1 - \sqrt 5 }}{2}} \right)}^{n+1}}} \right)$, так как начальные значения последовательности Фибоначчи сдвинуты $f_1=f_2=1$, а рекуррентное соотношение совпадает.