• A Shuttle Puzzle

• Permutations as a Product of Transpositions
• Group multiplication of permutations
• Product of permutations
• Recombining Permutations

The applet below has two purposes. First, it shows an additional way to visualize a permutation (three other possibilities have been described elsewhere.) The members of the set N_n, i.e., numbers from 1 through n, are arranged on a circle sequentially in a natural order. A permutation f: kf(k) is then represented by a set of arrows that join each i with the corresponding f(i), provided of course the two are different.

Second, the applet has been written with a certain solution to the Fifteen Puzzle in mind. Specifically, it helps one grasp an assertion about the representation of permutations as a product of disjoint cycles. A single move in the Fifteen puzzle consists in swapping a blank spot with an adjacent tile. The applet shows what happens when a permutation is multiplied by a transposition, i.e. a permutation that swaps two elements and leaves the rest untouched.

(To perform the feat click on the two elements in sequence.)

The applet demonstrates an intuitively obvious fact that such an operation changes the number of disjoint cycles in the representation of a permutation by 1. More accurately, swapping elements that belong to the same cycle, splits the cycle into two. Swapping elements that belong to different cycles joins their cycles into one. The operation is equivalent to multiplying the initial permutation on the left by a transposition of the two selected elements.

Copyright © 1996-2008 Alexander Bogomolny