wyznaczyć liczbę elementów zbioru

[MikolajB]

Niech \(\displaystyle{ n \in N _{+}}\). Wyznaczyć liczbę elementów zbioru \(\displaystyle{ X=\left\{ \sigma \in S _{n} : \left| \sigma\left( i\right) - i \le 1 \right| \right\}}\)

[brzoskwinka1]

Oznaczmy \(\displaystyle{ X_n =\{\sigma \in S_n : |\sigma (i)-i | \le 1 \text{ dla } i=1,2,...,n\}, A_n =\{\sigma \in X_n : \sigma (n) =n\} , \\B_n =\{\sigma \in X_n : \sigma (n) =n-1\} , C_n =\{\sigma \in X_n : \sigma (n) =n-1 \wedge \sigma (n-1) =n\} .}\)
Dalej niech \(\displaystyle{ x_n =\overline{\overline{X_n }} , a_n =\overline{\overline{A_n }} , b_n =\overline{\overline{B_n }} , c_n =\overline{\overline{C_n }} .}\)
Wówczas łatwo widać, że \(\displaystyle{ x_n =a_n +b_n , a_n =x_{n-1} , b_n =c_n =x_{n-2}}\) skąd otrzymujemy rekursję:
\(\displaystyle{ x_n =x_{n-1} +x_{n-2}}\) z warunkami początkowymi \(\displaystyle{ x_1 =2 , x_2 =3.}\)

[MikolajB]

Nie wiem skąd takie a nie inne równania dla \(\displaystyle{ \sigma}\) dla \(\displaystyle{ A _{n}, B _{n}, C _{n}}\)
skąd się wgl te trzy podzbiory wzięły i skąd takie zależności w nich?