Re: Permutations counting problem

From: Rani Sharoni (rani_sharoni_at_hotmail.com)
Date: 10/14/04 

Date: Thu, 14 Oct 2004 11:41:09 +0200

Gerry Myerson wrote:
> 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.

Exactly

> I have no idea how to answer it,

Same here.
It looks like a simple counting problem but I can't even think about
reasonable algorithm that enumerates all paths

> but this looks like a more
> mathematician-friendly way to ask it.

I hope so

> 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.

Good idea.

Thanks,
Rani

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)