On Thu, 29 Jul 2004, Daniel Asimov wrote:
Let the (usual) distance on the symmetric group S_n be given by d(p,q) = the least # of transpositions that will change p into q.
Just did some little calculations with the symmetric group S_4 and found the # of perms at distance = d from 1234 to be these:
dist: 0 1 2 3 4 5 6 #: 1 3 5 6 5 3 1
a) I'm wondering if there's a simple formula that will give this table for any S_n, including which perms are at what distance. I can do this by hand, but wonder if there's a faster algorithm than winging it -- and of course would want to use a computer for large n (even pretty small n are large in this question).
b) Even better, is there a simple formula to determine the distance between any two permutations p, q in S_n ? (I guess it boils down to the distance from p(q^-1) to the identity, which would come from the answer to a). But still it would be nice to quickly calculate all n!*(n!-1)/2 distances for tractable n.)
As you say the problem boils down to determining the distance from the identity to a permutation p. This is the minimum number of transpositions that it takes to write p. As I recall this minimum is obtained by computing the disjoint cycle decomposition and then decomposing each of the cycles into transpositions in the standard way so that a k-cycle is ap product of k-1 cycles. I think there was an article a few years ago in the Monthly proving this. I just looked this up in a little book I have by Persi Diaconis, Group Representations in Probablity and Statistics. He describes several metrics on S_n. The 5th one on page 112 is the one you describe. He attributes this to Cayley and mentions that Cayley proved that the distance from permutation f to permutation g in S_n is given by n - # cycles in the disjoint cycle decomposition of fg^(-1). The proof is essentially what I mentioned above, but Diaconis is skimpy on the details. Anyhow this should make it easy to find the formulas you seek. --Edwin PS This graph is clearly a "Cayley graph" and perhaps is the source of the term.