MAS1003 Discrete Mathematics: Problem sheet 4 Please hand in solutions to your tutor no later than Monday 6th December 1. [2] Consider the following elements in S_{8}:

σ : \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ \\ 3 & 7 & 4 & 2 & 1 & 8 & 6 & 5 \end{matrix} , τ : \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ \\ 2 & 4 & 5 & 3 & 8 & 6 & 7 & 1 \end{matrix} ,

and ρ : \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ & ↓ \\ 2 & 3 & 6 & 1 & 4 & 5 & 8 & 7 \end{matrix} .

Compute σ^{2}, τ^{2}, ρ^{2}, σ^{−1}, τ^{−1}, ρ^{−1}, στ, τσ, τ^{−1}ρ and στρ, expressing your answers in “two-row” notation. Write all of these permutations in cycle notation.

2. [2] In each case, given permutations σ, τ ∈ S_{n}, find σ^{2}, σ^{3}, σ^{−1}, τ^{2}, τ^{3}, τ^{−1}, στ, τσ, στσ^{−1} and τστ^{−1}. Express your answers in cycle notation.

(i) n = 6, σ = (1 4 5 6 2 3), τ = (1 3 5)(2 6); (ii) n = 8, σ = (1 3 5 2 8 7)(4 6), τ = (1 8)(2 7)(3 6)(4 5); (iii) n = 10, σ = (1 2 3 4 5 6 7 8 9 10), τ = (2 4 7 3 8 10)(5 9 6).

In general note that στ ≠ τσ. Can you see any relation between στ and τσ? [If so can you prove it?]

3. [2] In the lectures it was shown that S_{3} = {id, σ_{1}, σ_{2}, τ_{1}, τ_{2}, τ_{3}} where σ_{1} = (1 2 3), σ_{2} = (1 3 2), τ_{1} = (1 2), τ_{2} = (1 3) and τ_{3} = (2 3). Using this notation write down a complete multiplication table for S_{3}.

4. [2] List all 24 permutations in S_{4} in cycle notation, and give the order and sign of each.

5. [2] Recall the description in lectures of the perfect riffle shuffle. Write down, in cycle notation, the permutation corresponding to the riffle shuffle on a pack of n cards where (i) n = 12; (ii) n = 32; and (iii) n = 52. In each case determine the order of the permutation.

6. [3] Suppose that the permutation σ corresponds to the perfect riffle shuffle on a pack of n = 2m cards. Show that. for each j ∈ {1, 2, …, n} we have

σ(j) ≡ 2j (mod n + 1).

7. [2] Find the order and sign of the following permutations, and express each as a product of transpositions.

(i) (1 4 3)(2 6) ∈ S_{6}; (ii) (1 7 4)(2 6 3 8 5) ∈ S_{8}; (iii) (1 8 7 10 2 3 5)(4 9) ∈ S_{10}; (iv) (1 4 3 11 9)(2 7 10)(5 12 8 6) ∈ S_{12};

(v) (1 9 15 12 4 3 13)(2 6)(5 10 7 8) ∈ S_{15}.

8. [3] For each possible cycle structure for permutations in S_{6}, find the number of elements with that cycle structure. (That is, count the permutations with one cycle of length 6, then those with cycles of lengths 5 and 1, etc.) At the end check to see you have accounted for exactly 6! permutations in all.

9. [3] How many permutations σ are there with σ^{2} = id in (i) S_{3}; (ii) S_{4}; (iii) S_{5}; (iv) S_{6}?

10. [2] Let ρ and σ be permutations. Show that σ^{−1}ρ^{−1} is the inverse of ρσ.

11. [3] Which numbers are orders of permutations in (a) S_{5}; (b) S_{6}; (c) S_{7}? In each case, which numbers are orders of odd permutations, and which numbers are orders of even permutations?

12. [3] Let σ ∈ S_{n}, and suppose that the order of σ is an odd number. Show that σ is an even permutation.

13. [3] In each case calculate στ, and state how many cycles στ has (including 1-cycles):

(i) σ = (1 4 6 2 8)(3 5 7), τ = (1 2); (ii) σ = (1 4 7 6)(2 5)(3 8), τ = (1 2); (iii) σ = (1 3 8 5 6)(2)(4 7), τ = (2 5); (iv) σ = (1 3 8 5 6)(2)(4 7), τ = (1 3);

(v) σ = (1 3 8 5 6)(2)(4 7), τ = (1 5).

Given an arbitrary permutation σ ∈ S_{n} with r cycles (including 1-cycles) and a transposition τ ∈ S_{n}, what can you say about the number of cycles in στ? (You may like to collect more evidence yourself.) Can you prove that your observation always holds?

14. [4] The 15-puzzle consists of 15 numbered square tiles mounted in a 4 by 4 square frame as shown below.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15  1 2 3 4 5 6 7 8 9 10 11 12 13 15 14

One can move a tile by sliding it into the empty space. The object is to restore the tiles into numerical order as shown in the example on the left. If we label the blank square as 16, show that each move corresponds to a transposition in S_{16}. Hence show that the puzzle cannot be solved starting from the position on the right.

RJC 16/11/1999