From: ksbrown@seanet.com (Kevin Brown) Newsgroups: sci.math Subject: Re: Patterns in permutations Date: Fri, 03 Jul 1998 22:50:31 GMT On Fri, 03 Jul 1998 Nick Battle wrote: > After once hearing the "ringing of the changes" at Wells Cathedral > (where the N bells are rung in every N! permutation) I started > thinking about the various orderings of the permutations of N > numbers... Bell ringer friends told me of the various orderings > used to ring the changes, most of them using a simple swap or shift > of bell positions between adjacent peels so that they are simple to > play... Consider the N! permutations of the numbers (1, 2,..., N). > If you take each permutation as the coordinates of a point in N-space, > then all the N! points are equi-distant from the origin... I have > difficulty picturing what the N=4 "shape" made by joining the points > to their nearest neighbours would look like, though trying to project > it into 3-space I think the points form some sort of regular 4 > dimensional polyhedron (with 24 vertices). Yes, I think the shape is what's called a "truncated octahedron", one of the 13 Archimedian solids. It has six square faces and eight hexagonal faces, making a total of 14 faces. The number of edges is 36, as required by Euler's formula F + V - E = 2. For a similar discussion, you could take a look at the notes called "The Shape of Coincidence" and "Meeting Probabilities" at the web page http://www.seanet.com/~ksbrown/. To determine the 3D coordinates of the "4! solid" given in 4D space by the permutations of [1,2,3,4] it might be easiest to subtract 5/2 from each coordinate so as to center the solid at the origin. Then for each of the 4D verticies [W,X,Y,Z] we have W+X+Y+Z=0, which of course is the condition that ensures us we are really dealing with a 3D solid that happens to be rotated into 4D space. We know the 4D coordinates of the verticies are the permutations of V1 = [-3/2, -1/2, +1/2, +3/2] so each vertex is a distance of d = sqrt(5) from the origin. We want to find a rotation that brings all these points into the form [x,y,z,0]. We're free to place the point V1 on the x axis at [d, 0, 0, 0], and we can place the perpindicular point V2 = [+1/2, -3/2, +3/2, -1/2] on the y axis at [0, d, 0, 0]. (Note that V1 and V2 are orthogonal, as can be seen by computing V1 dot V2 = 0.) Then, for lack of any better ideas, let's consider the vertex given by permuting the last two coordinates of V1, i.e., V3 = [-3/2, -1/2, +3/2, +1/2] From the known distances of this vertex to V1, V2, and the origin, we know the 3D coordinates of V3 satisfy the conditions x^2 + y^2 + z^2 = 5 (x-d)^2 + y^2 + z^2 = 2 x^2 + (y-d)^2 + z^2 = 6 which implies that x = 4/d y = 2/d z = +-1 so we can assign it the 3D coordinates [4/d, 2/d, 1, 0]. This is our third independent vector in our 3D space, so we'll need something in 4D to complete the conditions. Let's say the 4D vector V4 = [0, 0, 0, 1] goes to [x,y,z,w] when it is subjected to our rotation. To ensure the determinant of our rotation matrix is 1 we need w=1/2, and then preservation of the distances to V4 leads to the conditions x^2 + y^2 + z^2 = 1 - (1/2)^2 (x-d)^2 + y^2 + z^2 = 3 - (1/2)^2 x^2 + (y-d)^2 + z^2 = 7 - (1/2)^2 which implies x = 3/(2d), y = -1/(2d), and z = +-1/2. Combining all these conditions we can solve for the rotation matrix R using the equation _ _ _ _ | d 0 4/d 3/(2d) || -3/2 1/2 -3/2 0 |-1 R = | 0 d 2/d -1/(2d) || -1/2 -3/2 -1/2 0 | | 0 0 1 1/2 || 1/2 3/2 3/2 0 | |_ 0 0 0 1/2 _||_ 3/2 -1/2 1/2 1 _| _ _ | -3/d -1/d 1/d 3/d | = (1/2)| 1/d -3/d 3/d -1/d | | 1 3 3 1 | |_ 1 1 1 1 _| Applying this transformation to the original 4D "permutation points" (and noting that we need consider only 12 points because they come in opposite pairs), we have the 3D coordinates 2W 2X 2Y 2Z x y z --- --- --- --- ----- ----- ----- -3 -1 +1 +3 d 0 0 -3 -1 +3 +1 4/d 2/d 1 -3 +3 -1 +1 2/d -4/d 1 -3 +3 +1 -1 1/d -2/d 2 -3 +1 -1 +3 4/d -3/d 0 -3 +1 +3 -1 2/d 1/d 2 -1 -3 +1 +3 4/d 2/d -1 -1 -3 +3 +1 3/d 4/d 0 -1 +1 -3 +3 2/d -4/d -1 -1 +1 +3 -3 -1/d 2/d 2 -1 +3 +1 -3 -2/d -1/d 2 -1 +3 -3 +1 0 -d 0 The other 12 points are just the negatives of these (x,y,z) vectors. As mentioned above, these 24 points constitute the verticies of a truncated octahedron. A little Java applet that allows you to examine this solid can be found at the web version of this note at http://www.seanet.com/~ksbrown/kmath482.htm. _________________________________________________________________ | MathPages /*\ http://www.seanet.com/~ksbrown/ | | / \ | |__________/"Angels alone, that soar above, enjoy such liberty." _|