# Permutation - Find occurrences where pair of 2 adjacent values does not belong to original sequence

Given an original sequence of numbers (of length n with all unique values), we have to first identify all its permutations. Next we will remove such permutations, where any pair of 2 adjacent values are present as it is in the provided original sequence.

Example,

Case 1: For n = 2, Original sequence = {1,2}

Possible per = {1,2} and {2,1}

Relevant per = Only 1 out of 2 i.e. {2,1}.

Bcoz (1,2) in {1,2} seq is present in original sequence.

Case 2: For n = 3, Original sequence = {1,2,3}

Possible per = {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2} and {3,2,1}

Relevant per = Only 3 out of 6 i.e. {1,3,2}, {2,1,3} and {3,2,1}.

Bcoz {1,2,3} contains pair (1,2) and pair (2,3) which is present in original, {2,3,1} contains pair (2,3) which is present in original, {3,1,2} contains pair (1,2) which is present in original.

Question,

Is there a generalisation of the solution?

Thank you.

• Are you asking for the number of permutations $\sigma$ of $\left\{1,2,\ldots,n\right\}$ such that $\sigma\left(i+1\right) \neq \sigma\left(i\right) + 1$ for each $i \in \left\{1,2,\ldots,n-1\right\}$ ? – darij grinberg Mar 1 at 20:53
• Perhaps a recursion works. After all, if you have a "good" permutation on $n-1$ letters then you can insert the $n$ anywhere except to the right of $n-1$. The problem is that if you have a permutation on $n-1$ letters which only has a single bad pair in it then you can insert the $n$ between those two to make a new good permutation on $n$ letters, so you'll also need to count those permutations with exactly one bad pair. Not sure this is tractable. – lulu Mar 1 at 21:41
• The following MSE link might be relevant. – Marko Riedel Mar 2 at 14:01