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 Nn, i.e., numbers from 1 through n, are arranged on a circle sequentially in a natural order. A permutation f: k → f(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.)


This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.


What if applet does not run?

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.

Permutations

  • Transpositions
  • Groups of Permutations
  • Sliders
  • Puzzles on graphs
  • Equation in Permutations

    |Activities| |Contact| |Front page| |Contents| |Games|

    Copyright © 1996-2018 Alexander Bogomolny

  • 71491464