Representing Permutations

Often, a mathematical puzzle or problem is interesting because the answer is interesting.  The recent card tricks and other prisoner puzzles discussed lately are of this type.  There is a solution when it seems none exists, or we can succeed with a much higher probability than intuition would suggest.  As Peter Winkler puts it, these are “puzzles you think you must not have heard correctly.”

Other problems, like the one presented last week, are interesting because the method of solution is interesting.  The actual answer may not be terribly surprising, but the process of arriving at the answer involves something surprisingly simple, elegant, and/or useful in other applications.  (Dick Lipton at Gödel’s Lost Letter has an interesting article about historical examples of this in mathematics and computer science, where “the proof is more important than the result.”)

In last week’s problem, we were asked for the probability of successfully unlocking all of n boxes, given that we may initially select and break into k of them.  The answer is rather unsurprising; in fact, it is what you might guess the answer to be without any thought: the probability is k/n.  But I like this problem anyway, because showing that the probability is k/n involves a very simple yet handy idea, that of the canonical cycle representation of a permutation.

First, we can represent the random distribution of keys into boxes by a randomly selected permutation \pi \in S_n, where box i contains the key that unlocks box \pi(i).  There are several different ways to write such a permutation.  For example, we can simply list the image elements \langle\pi(1), \pi(2), ..., \pi(n)\rangle in order.

Another representation that is more convenient for this problem is to decompose the permutation into cycles, where each element is mapped to the element appearing immediately after it in the same cycle (wrapping around if necessary).  Using parentheses to group elements in a cycle, the following notations represent the same permutation:

(2, 4, 5)(1)(6, 3) = \langle 1, 4, 6, 5, 2, 3\rangle

Cycles are important in this prisoner puzzle.  If we assume WLOG that we break open boxes 1 through k, then we can unlock all of the remaining boxes if and only if every cycle in \pi contains an element in {1, 2, ..., k}.  We can find the desired probability by counting the number of permutations that have this property.

There are two disadvantages of cycle representations of a permutation.  First, we need the parentheses to indicate which elements belong to the same cycle.  Thinking like a computer scientist, if we want to store a permutation as a simple linear array of n elements, then the cycle representation requires storing additional information about where the parentheses go.

The second disadvantage is that cycle representations are not unique.  It does not matter in what order we write the cycles; nor does it matter which element we write first in any particular cycle.  For example, all of the following represent the same permutation:

(2, 4, 5)(1)(6, 3) = (1)(2, 4, 5)(3, 6) = (3, 6)(2, 4, 5)(1)

The canonical cycle representation simply fixes a particular ordering of cycles and elements within each cycle, by writing each cycle with its least element first, and ordering the cycles from left to right in decreasing order of first element.  For example, the last of the three representations above is the “canonical” one.  (It is worth pointing out that an equally workable “canonical” representation would be to write each cycle with its largest element first, and order the cycles from left to right in increasing order of first element.)

This representation solves both of our problems: it is unique… and it does not require the parentheses!  That is, each of the n! possible lists of elements corresponds to a unique permutation whose canonical cycle representation has that same ordering of elements.

Coming back to the puzzle again, we can now restate the desired property of a permutation very simply in terms of its canonical cycle representation.  We can unlock all of the remaining boxes if and only if the first element in the canonical cycle representation of the corresponding permutation is at most k.  The number of permutations with this property is k(n-1)!, and so the probability is k/n.

 

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s