0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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\}$ ? $\endgroup$ – darij grinberg Mar 1 at 20:53
  • $\begingroup$ 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. $\endgroup$ – lulu Mar 1 at 21:41
  • $\begingroup$ The following MSE link might be relevant. $\endgroup$ – Marko Riedel Mar 2 at 14:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.