Number of permutations of $6 $digit numbers from $\{1,2,3,4,5,6\}$ such that the pattern $12, 23 ,34 ,45, 56$ do not appear is?
I observed that if we take the above permutation as a function in variable $n$ (number of digits given; 6 in above case) then, given $n>2$, $$f(n)=(n-1)f(n-1)+(n-2)f(n-2)$$ for example: $f(3)$=Number of permutations of 3 digit numbers from {1,2,3} such that the pattern 12,23 does not appear I got $f(3)=3$ (tell me if Iam wrong) $f(4)=11$ as from above formula i got $f(5)=53$ which is correct so can anyone tell me the original process for this question please.
Let $f(n)$ denote the number of feasible permutations of the numbers $1...n$ and let $g(n)$ denote the number of permutations of these numbers that contain exactly one disallowed pair (a pattern $(k,k+1)$ for some $k$ with $1\le k\le n-1$).
To build a feasible permutation for the numbers $1...n$, we can either start with a feasible permutation of the numbers $1...(n-1)$ and place the number $n$ somwhere in between/around, except directly after number $n-1$ (there are $n-1$ possible positions), or we start with a permutation of $n-1$ elements that contains exactly one disallowed pair $(k,k+1)$ and place the number $n$ between $k$ and $k+1$ (to "destroy" the disallowed pair). In total, we get $$ f(n)=(n-1)f(n-1)+g(n-1) $$ Now, to construct a permutation of the $n$ numbers that contains exactly one disallowed pair $(k,k+1)$, we can do the following: Choose any $k$ from $1...(n-1)$ and start with a feasible permutation of the $n-1$ numbers $1...(n-1)$. In this permutation, add $1$ to all numbers greater than $k$ and place $k+1$ directly after $k$. This process can be reversed to receive a feasible permutation of $n-1$ elements from any $n$-permutation with exactly one disallowed pair, so $$ g(n)=(n-1)f(n-1) $$ Putting both together, we indeed get $$ f(n)=(n-1)f(n-1)+g(n-1)=(n-1)f(n-1)+(n-2)f(n-2) $$