Review worksheet

Review worksheet: permutations

Published

Open PDF The PDF is in Romanian.

Press “Check” next to an exercise. Your answers stay on this device.

Notation

$S_{n}$ – the set of permutations of degree $n$; $e$ – the identity permutation; $m(\sigma)$ – the number of inversions of the permutation $\sigma$; $\varepsilon(\sigma) = ( - 1)^{m(\sigma)}$ – the sign of the permutation $\sigma$; $\sigma\tau = \sigma \circ \tau$, where $(\sigma \circ \tau)(k) = \sigma(\tau(k))$.

Level I – basic problems (problems 1–17)

  1. a) Write all the elements of the set $S_{3}$.

    b) How many elements do the sets $S_{4}$ and $S_{5}$ have?

  2. Consider the functions $f,g:\{ 1,2,3,4\} \rightarrow \{ 1,2,3,4\}$, where $f(x)$ is the remainder of $3x$ divided by 5, and $g(x)$ is the remainder of $x^{2}$ divided by 5. Decide which of them is a permutation and write it as a two-row table.

  3. Let $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 4 & 2 \end{pmatrix} \in S_{4}$. Calculate $\sigma(1) + \sigma(4)$, $\sigma(\sigma(2))$ and $\sigma^{- 1}(4)$.

  4. Find the natural numbers $x$ and $y$ for which $\begin{pmatrix} 1 & 2 & 3 & 4 \\ x + y & 4 & x - y & 2 \end{pmatrix} \in S_{4}$.

  5. Find the real numbers $a$, $b$, $c$ for which $\begin{pmatrix} 1 & 2 & 3 \\ 2a - 1 & b + 1 & c \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix}$.

  6. Let $\sigma = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}$ and $\tau = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix}$. Calculate $\sigma\tau$ and $\tau\sigma$. Is the composition of permutations commutative? Check that $(\sigma\tau)\sigma = \sigma(\tau\sigma)$.

  7. Let $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \end{pmatrix}$. Calculate $\sigma^{2}$, $\sigma^{3}$ and $\sigma^{4}$.

  8. Find the inverse of the permutation $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 1 & 2 & 4 \end{pmatrix}$ and check that $\sigma\sigma^{- 1} = e$.

  9. Find the number of inversions and the sign of the permutation $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 3 & 1 & 4 \end{pmatrix}$.

  10. Decide whether each permutation is even or odd: $e \in S_{5}$, $\alpha = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 1 \end{pmatrix}$ and $\beta = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 4 & 3 & 2 & 5 \end{pmatrix}$.

  11. Let $\tau \in S_{4}$ be the transposition that swaps the numbers 1 and 4. Write $\tau$ as a table, and calculate $\tau^{2}$, $\tau^{- 1}$ and $\varepsilon(\tau)$.

  12. Calculate $m(\sigma)$ and $\varepsilon(\sigma)$ for $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 5 & 4 & 3 & 2 & 1 \end{pmatrix}$.

  13. Let $\sigma = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix}$. Calculate $\sigma^{- 1}$ and $\sigma^{2}$. Show that $\sigma^{2} = \sigma^{- 1}$ and $\sigma^{3} = e$.

  14. Solve in $S_{3}$ the equation $\sigma x = \tau$, where $\sigma = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}$ and $\tau = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix}$.

  15. Solve in $S_{3}$ the equation $x\sigma = \tau$, where $\sigma = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}$ and $\tau = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix}$. Compare the solution with the one of problem 14.

  16. Let $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3 \end{pmatrix}$ and $\tau = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 3 & 4 & 2 \end{pmatrix}$. Calculate $\sigma\tau$ and check the equality $\varepsilon(\sigma\tau) = \varepsilon(\sigma) \cdot \varepsilon(\tau)$.

  17. a) How many permutations $\sigma \in S_{4}$ satisfy $\sigma(1) = 1$?

    b) How many permutations $\sigma \in S_{4}$ satisfy $\sigma(1) = 2$ and $\sigma(2) = 1$?

    c) Write all the transpositions in $S_{4}$.

Level II – intermediate problems (problems 18–35)

  1. Let $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \end{pmatrix}$. Show that $\sigma^{2} = e$ and calculate $\sigma^{2026}$ and $\sigma^{2027}$.

  2. Let $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \end{pmatrix}$. Show that $\sigma^{4} = e$ and calculate $\sigma^{2026}$.

  3. Let $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 1 & 4 & 5 & 3 & 6 \end{pmatrix}$. Find the smallest nonzero natural number $k$ for which $\sigma^{k} = e$, and calculate $\sigma^{100}$.

  4. Solve in $S_{4}$ the equation $axb = c$, where $a = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 3 & 1 & 4 \end{pmatrix}$, $b = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 3 & 4 & 2 \end{pmatrix}$, $c = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 1 \end{pmatrix}$.

  5. Let $n \geq 2$ and $\sigma = \begin{pmatrix} 1 & 2 & 3 & \ldots & n \\ n & n - 1 & n - 2 & \ldots & 1 \end{pmatrix}$. Find $m(\sigma)$ and decide for which values of $n$ the permutation $\sigma$ is even.

  6. Write the permutation $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 4 & 1 & 2 \end{pmatrix}$ as a product of transpositions and deduce its sign. Check the result by counting the inversions.

  7. Show that $\varepsilon(\sigma^{- 1}) = \varepsilon(\sigma)$ for every $\sigma \in S_{n}$. Check it for $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 1 & 5 & 2 & 3 \end{pmatrix}$.

  8. Find all the permutations $x \in S_{3}$ for which $x^{2} = e$.

  9. Find all the permutations $x \in S_{3}$ for which $x^{3} = e$.

  10. Find the permutations $\sigma \in S_{3}$ that satisfy $\sigma\tau = \tau\sigma$, where $\tau = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}$.

  11. a) How many even permutations does $S_{4}$ contain?

    b) How many permutations in $S_{4}$ have exactly two inversions? Write them.

  12. Find $a,b \in \{ 2,5\}$, $a \neq b$, such that the permutation $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & a & 1 & b & 3 \end{pmatrix}$ is even.

  13. Let $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 1 & 5 & 4 \end{pmatrix}$ and $\tau = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 2 & 1 & 4 & 5 \end{pmatrix}$. Calculate $\varepsilon(\sigma^{2026}\tau^{- 1})$.

  14. Solve in $S_{3}$ the equation $x^{2} = \sigma$, where $\sigma = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}$.

  15. Find the number of inversions and the sign of the permutation $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 4 & 6 & 1 & 3 & 5 \end{pmatrix}$.

  16. a) Show that for every transposition $\tau \in S_{n}$ we have $\tau^{2} = e$ and $\tau^{- 1} = \tau$.

    b) Show that $S_{n}$ contains $\frac{n(n - 1)}{2}$ transpositions.

    c) Find $n$ if $S_{n}$ contains 28 transpositions.

  17. Let $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 3 & 1 \end{pmatrix}$ and $\tau = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 1 \end{pmatrix}$. Calculate $\sigma^{3}$ and solve in $S_{4}$ the equation $\sigma^{2}x = \tau$.

  18. Show that the equation $x^{2} = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}$ has no solutions in $S_{3}$.

Level III – advanced problems (problems 36–50)

  1. Let $n \in {\mathbb{N}}^{*}$ and $\sigma = \begin{pmatrix} 1 & 2 & \ldots & n & n + 1 & n + 2 & \ldots & 2n \\ 2 & 4 & \ldots & 2n & 1 & 3 & \ldots & 2n - 1 \end{pmatrix} \in S_{2n}$.

    a) Show that $m(\sigma) = \frac{n(n + 1)}{2}$.

    b) Find the sign of $\sigma$ for $n = 2026$.

  2. Solve in $S_{4}$ the equation $x^{2} = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 4 & 1 & 2 \end{pmatrix}$.

  3. Find the permutations $x \in S_{3}$ for which $x^{2027} = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}$.

  4. Show that $\sigma^{12} = e$ for every $\sigma \in S_{4}$. Is there a natural number $1 \leq k < 12$ such that $\sigma^{k} = e$ for every $\sigma \in S_{4}$?

  5. How many permutations $\sigma \in S_{6}$ satisfy $\sigma(1) < \sigma(2) < \sigma(3)$?

  6. A number $i$ is called a fixed point of the permutation $\sigma$ if $\sigma(i) = i$. How many permutations in $S_{4}$ have no fixed point? What about in $S_{5}$?

  7. Find $n \in {\mathbb{N}}$, $n \geq 2$, if the permutation $\begin{pmatrix} 1 & 2 & \ldots & n - 1 & n \\ n & n - 1 & \ldots & 2 & 1 \end{pmatrix}$ has 45 inversions.

  8. Let $n \geq 2$ and let $\tau \in S_{n}$ be a transposition. Show that the function $f:S_{n} \rightarrow S_{n}$, $f(\sigma) = \tau\sigma$ is bijective and maps even permutations to odd permutations. Deduce that $S_{n}$ contains $\frac{n!}{2}$ even permutations and $\frac{n!}{2}$ odd permutations.

  9. Let $A_{n}$ be the set of even permutations in $S_{n}$. Show that if $\sigma,\tau \in A_{n}$, then $\sigma\tau \in A_{n}$ and $\sigma^{- 1} \in A_{n}$.

  10. Show that for every $\sigma \in S_{n}$ there is $k \in {\mathbb{N}}^{*}$ such that $\sigma^{k} = e$.

  11. Find the permutations $\sigma \in S_{3}$ that satisfy $\sigma x = x\sigma$ for every $x \in S_{3}$.

  12. Show that the equation $x^{2} = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \end{pmatrix}$ has no solutions in $S_{4}$.

  13. Let $\sigma \in S_{n}$ and $\rho = \begin{pmatrix} 1 & 2 & \ldots & n \\ n & n - 1 & \ldots & 1 \end{pmatrix}$. Show that $m(\sigma\rho) = \frac{n(n - 1)}{2} - m(\sigma)$.

  14. Consider the permutation $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 1 & 5 & 4 \end{pmatrix}$.

    a) Find the number of inversions and the sign of $\sigma$.

    b) Show that $\sigma^{6} = e$.

    c) Calculate $\sigma^{2026}$.

    d) Show that the equation $x^{2} = \sigma$ has no solutions in $S_{5}$.

  15. Consider the permutation $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 4 & 2 & 1 \end{pmatrix}$.

    a) Find $\sigma^{- 1}$.

    b) Find the number of permutations $x \in S_{4}$ for which $\varepsilon(x\sigma) = 1$.

    c) Solve in $S_{4}$ the equation $\sigma x\sigma = e$.