I'm confused. Shouldn't there be 4 \choose 2 = 6 permutations at distance one? 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.)
Dan
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Thane Plambeck thane@best.com http://www.plambeck.org