At 11:51 PM 7/29/2004, Thane Plambeck wrote:
I'm confused. Shouldn't there be 4 \choose 2 = 6 permutations at distance one?
Perhaps Dan means to limit the transpositions to transpositions of adjacent elements; at any rate, that definition results in the same numbers for S_4. In that case there is a simple way of computing the table which is exemplified by the fact that 1356531 = 1*11*111*1111, and is easily established by induction (tacking n+1 onto a permutation of 1...n yields n+1 possibilities with 0,1,... or n more transpositions needed to put n in the desired place). This distance between two permutations is also given by the number of pairs of elements which appear in one order in the first permutation and in the opposite order in the second.
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.)
-- Fred W. Helenius <fredh@ix.netcom.com>