Permutations

[Kennedy]

Christopher,
The seq you seek is A002464. There's quite a bit of information on it in the Encyclopedia, including a simple recursive formula.
I wrote a program to calculate the first few terms; it found the first 10 or 11 in less than one minute.
Regards,
Jack Kennedy

  ----- Original Message ----- 
  From: Christopher Tomaszewski 
  To: SeqFan 
  Sent: Sunday, December 14, 2003 11:09 PM
  Subject: Permutations


  SeqFan members,

      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:

  {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}

  I have already searched the database for the sequence resulting from finding this number for each of n, and it returned nothing. I based the search on the first 5 terms I have derived empirically thus far. I know 6, but I did not include the 6th because, although I checked it aganist all the characteristics I am aware of this sequence possessing, I can not be absolutely sure of its validity. Does anybody know anything about this, or even heard of such a sequence before? Or perhaps somebody is aware of a program that might be able to generate futher terms without manually checking each of the permutations? Manual search can not hope to generate even several more terms when the exponential growth of the factorial function is considered.

  Sincerely,
  Christopher M. Tomaszewski
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20031215/4b7b12b1/attachment-0001.htm>