Re: Permutations counting problem

From: Gerry Myerson (gerry_at_maths.mq.edi.ai.i2u4email)
Date: 10/14/04 

Date: Thu, 14 Oct 2004 11:22:55 +1000

In article <df893da6.0410130102.523af172@posting.google.com>,
 rani_sharoni@hotmail.com (Rani Sharoni) wrote:

> What is the number of enumerations, starting from identity, of all
> n-length permutations, without repetitions, where each step is a
> transposition (i.e. changing exactly two elements)?
>
> Let's call such enumeration a "low const path".
>
> Examples of two low cost paths for 3-length permutation:
> 123 ; identity 123 ; identity
> 132 ; (2,3) 321 ; (1,3)
> 231 ; (1,3) 231 ; (1,2)
> 213 ; (2,3) 213 ; (2,3)
> 312 ; (1,3) 312 ; (1,3)
> 321 ; (2,3) 132 ; (1,2)
>
> I counted 3*2*2=12 paths for 3-length.

Let me see if I understand the problem.

You have a graph. There is one vertex for each permutation on n
symbols, and there is an edge between vertices if you can get
from the one permutation to the other by a single transposition.
You want the number of hamiltonian paths in this graph.

I have no idea how to answer it, but this looks like a more
mathematician-friendly way to ask it.

If you can calculate it for a few small values of n, you can
try looking up the terms in Sloane's online encyclopedia of
integer sequences. 

-- 
Gerry Myerson (gerry@maths.mq.edi.ai) (i -> u for email)

Relevant Pages

  • Re: Maximum over an n-cycle
    ... and a permutation s in S_n, ... What I actually proved is that no _transposition_ of the ... A version of my question was indeed one of the easier Putnam problems ... I already knew that the sum S can be increased by transposing ...
    (sci.math)
  • Re: was heisst Produkt von Transposition?
    ... wie kann man fuer Permutation Klammern in newsgroup machen? ... Zykelschreibweise zu verwenden, wie Du es in der ersten Zeile bereits ... Eine Transposition ist eine Permutation, ...
    (de.sci.mathematik)
  • Re: Odd and even transpositions of permutations
    ... (Arturo Magidin) ... but is not a transposition! ... A transposition is a permutation that lets every element fixed ... thing as a "transposition of permutation", let alone "odd ...
    (sci.math)
  • Re: Maximum over an n-cycle
    ... quasi wrote: ... Then a specification for an optimal sequence ... cyclic permutation, except in reverse order. ... What I actually proved is that no _transposition_ of the ...
    (sci.math)
  • Re: Info about a particular permutation distance
    ... > permutation distance definitions, and didn't find ... > transposition: in fact, a transposition involves two ... proved that the distance from permutation f to permutation g in S_n is ... W. Edwin Clark, Math Dept, University of South Florida ...
    (sci.math)
Quantcast