Permutations

[Eric W. Weisstein]

On Mon, 15 Dec 2003, Christopher Tomaszewski wrote:

>     I am currently attempting to derive a formula giving the total
> number of permutations of n elements such that no two elements which
> were consecutive in the original set are consecutive in any of the
> permutations.
> 
>     In order to easily remember the original positions of elements in
> empirical study, I simply use the set {1,2,3,...,n}.
> 
> Here are all 24 permutations of {1,2,3,4}, with those satisfying my
> criteria in red:

There is no such thing as red in email...

> {1,2,3,4}  {1,2,4,3}  {1,3,2,4}  {1,3,4,2}  {1,4,2,3}  {1,4,3,2}
> {2,1,3,4}  {2,1,4,3}  {2,3,1,4}  {2,3,4,1}  {2,4,1,3}  {2,4,3,1}  {3,1,2,4}  {3,1,4,2}  {3,2,1,4}  {3,2,4,1}  {3,4,1,2}  {3,4,2,1}
> {4,1,2,3}  {4,1,3,2}  {4,2,1,3}  {4,2,3,1}  {4,3,1,2}  {4,3,2,1}

If I understand your statement of the problem correctly:
http://www.research.att.com/projects/OEIS?Anum=A002464

Cheers,
-E