Областная олимпиада по математике, 2015 год, 11 класс

Найдите количество перестановок $(x_1,x_2,\dots,x_n)$ набора $(1,2,\dots,n)$, удовлетворяющих условиям $x_i< x_{i+2}$ при $1 \leq i \leq n-2$, $x_i< x_{i+3}$ при $1 \leq i \leq n-3$. Здесь $n \geq 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$, а рекуррентное соотношение совпадает.