Thane wrote:

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

nmbr: 1 3 5 6 5 3 1

Maybe I didn't express the definition of distance clearly, and/or maybe I'm using confusing notation.

But there are only 3 transpositions one can apply to 1234: (12),(23), or (34). The 3 perms. at distance = 1 from 1234

[Note: 1234 doesn't mean the cycle (1234); it's the identity perm., the result of applying the identity to the initial position of 4 things, which I'm calling 1234]

are the following: 2134, 1324, or 1243.

(By the same token, *any* element of S_4

should also have exactly 3 perms. at distance = 1

from it.)

Hope this clarifies things.

--Dan