Fifteen Puzzle Explorer

1. Two-row notation

A permutation of \(\{1,2,\dots,n\}\) is a rearrangement of the numbers \(1,2,\dots,n\). The set of all permutations of \(\{1,2,\dots,n\}\) is denoted \(S_n\).

For the second board above, write

Sigma is the permutation sending 1 to 3, 2 to 1, 3 to 4, 4 to 2, 5 to 5, 6 to 7, and 7 to 6. \[ \sigma= \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 3 & 1 & 4 & 2 & 5 & 7 & 6 \end{bmatrix}. \]

This means \(\sigma(1)=3\), \(\sigma(2)=1\), \(\sigma(3)=4\), \(\sigma(4)=2\), \(\sigma(5)=5\), \(\sigma(6)=7\), and \(\sigma(7)=6\).

1. Draw the 7-puzzle board associated to the two-row permutation with top row 1 through 7 and bottom row 4, 1, 7, 3, 2, 5, 6. \[ \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 1 & 7 & 3 & 2 & 5 & 6 \end{bmatrix} \]
2. Draw the 7-puzzle board associated to the two-row permutation with top row 1 through 7 and bottom row 2, 6, 1, 5, 4, 7, 3. \[ \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 2 & 6 & 1 & 5 & 4 & 7 & 3 \end{bmatrix} \]
3. Write this board in two-row notation. This 7-puzzle board has top row 2, 3, 1, 4 and bottom row 5, 6, 7, blank.
   2314 567

2. One-row notation

In two-row notation, the top row is always the standard list \(1,2,\dots,n\). Because of that, it is often omitted. This gives the shorter one-row notation.

The same permutation can be written in two-row notation or shortened to the one-row list 3, 1, 4, 2, 5, 7, 6. \[ \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 3 & 1 & 4 & 2 & 5 & 7 & 6 \end{bmatrix} \qquad \longleftrightarrow \qquad [3\ 1\ 4\ 2\ 5\ 7\ 6]. \]

The solved board becomes \([1\ 2\ 3\ 4\ 5\ 6\ 7]\).

This board This board has top row 2, 3, 1, 4 and bottom row 5, 6, 7, blank.

becomes \([2\ 3\ 1\ 4\ 5\ 6\ 7]\).

1. Write \([2\ 3\ 1\ 4\ 5\ 6\ 7]\) in two-row notation.
2. Write \(\begin{bmatrix}1 & 2 & 3 & 4 \\ 4 & 1 & 3 & 2\end{bmatrix}\) in one-row notation.
3. Which 7-puzzle board corresponds to \([3\ 1\ 2\ 4\ 5\ 6\ 7]\)?

3. Cycle notation

For \([3\ 1\ 4\ 2\ 5\ 7\ 6]\), start with \(1\): \(1\mapsto3\mapsto4\mapsto2\mapsto1\). This gives \((1\ 3\ 4\ 2)\).

Then start with \(6\): \(6\mapsto7\mapsto6\). This gives \((6\ 7)\). The number \(5\) is fixed, so it is usually omitted. Therefore

The permutation 3, 1, 4, 2, 5, 7, 6 decomposes into the disjoint cycles (1 3 4 2) and (6 7). \[ [3\ 1\ 4\ 2\ 5\ 7\ 6]=(1\ 3\ 4\ 2)(6\ 7). \]

This board This board has top row 2, 3, 1, 4 and bottom row 5, 6, 7, blank.

corresponds to \([2\ 3\ 1\ 4\ 5\ 6\ 7]=(1\ 2\ 3)\).

Convert the following permutations to cycle notation.

1. Convert \([4\ 1\ 3\ 2]\) to cycle notation.
2. Convert \([1\ 5\ 2\ 4\ 3\ 6\ 7]\) to cycle notation.
3. Convert \([3\ 9\ 10\ 4\ 5\ 6\ 1\ 2\ 8\ 7]\in S_{10}\) to cycle notation.
4. Convert \([6\ 5\ 4\ 3\ 2\ 1]\in S_6\) to cycle notation.

Convert the following examples of cycle notation to one-row notation. The ambient set matters here, because fixed points are omitted from the cycle notation.

1. Convert \((1\ 4\ 2)(3\ 5)\in S_5\) to one-row notation.
2. Convert \((2\ 5\ 6\ 8)\in S_8\) to one-row notation.
3. Convert \((2\ 5\ 6\ 8)\in S_{10}\) to one-row notation.
4. Convert \((1\ 2\ 5)(3\ 4\ 6)\in S_6\) to one-row notation.

4. Diagrams

A useful picture places \(1,2,\dots,n\) across the top and again across the bottom, then connects the point labeled \(i\) on top to the point labeled \(\sigma(i)\) on the bottom.

The diagram contains the same information as the list. It is just another way to see the same permutation.

5. Composition of permutations

If \(\sigma\) and \(\tau\) are permutations, then so is their composition. We write \((\sigma\tau)(i)=\sigma(\tau(i))\), so the rightmost permutation acts first.

Let Let tau be the permutation 2, 1, 3, 4, 5 and let sigma be the permutation 1, 3, 2, 4, 5. \[ \tau=[2\ 1\ 3\ 4\ 5], \qquad \sigma=[1\ 3\ 2\ 4\ 5]. \]

Then \((\sigma\tau)(1)=\sigma(\tau(1))=\sigma(2)=3\), \((\sigma\tau)(2)=\sigma(\tau(2))=\sigma(1)=1\), and \((\sigma\tau)(3)=\sigma(\tau(3))=\sigma(3)=2\). Therefore

The composition sigma tau is the permutation 3, 1, 2, 4, 5. \[ \sigma\tau=[3\ 1\ 2\ 4\ 5]. \]

For practice, use the following permutations.

Let sigma a be the permutation 3, 9, 10, 4, 5, 6, 1, 2, 8, 7; sigma b be 7, 8, 1, 4, 5, 6, 10, 9, 2, 3; sigma c be 1, 9, 8, 3, 5, 6, 2, 7, 4, 10; tau a be the cycle 2, 5, 6, 8 in S 10; tau c be the product of cycles 1, 2, 5 and 3, 4, 6 in S 6; and tau d be the product of transpositions 1, 2; 2, 3; 3, 4; 4, 5; 5, 6 in S 6. \[ \sigma_a=[3\ 9\ 10\ 4\ 5\ 6\ 1\ 2\ 8\ 7],\qquad \sigma_b=[7\ 8\ 1\ 4\ 5\ 6\ 10\ 9\ 2\ 3], \] \[ \sigma_c=[1\ 9\ 8\ 3\ 5\ 6\ 2\ 7\ 4\ 10],\qquad \tau_a=(2\ 5\ 6\ 8)\in S_{10}, \] \[ \tau_c=(1\ 2\ 5)(3\ 4\ 6)\in S_6,\qquad \tau_d=(1\ 2)(2\ 3)(3\ 4)(4\ 5)(5\ 6)\in S_6. \]

Composition exercises

1. Compute \(\sigma_a\sigma_b\).
2. Compute \(\sigma_b\sigma_a\).
3. Compute \(\sigma_a\tau_a\).
4. Compute \(\tau_a\sigma_c\).
5. Compute \(\tau_c\tau_d\).
6. Compute \(\tau_d\tau_c\).

Inverses

The identity permutation is \(e=[1\ 2\ \dots\ n]\). The inverse \(\tau^{-1}\) is the permutation that undoes \(\tau\), so \(\tau\tau^{-1}=\tau^{-1}\tau=e\).

1. Find \(\sigma_a^{-1}\).
2. Find \(\sigma_c^{-1}\).
3. Find \(\tau_a^{-1}\).
4. Find \(\tau_c^{-1}\).
5. Find \(\tau_d^{-1}\).

These diagrams will be useful on the next page, where crossings are used to define the length of a permutation.