Math Problems Vault

Problem 1.7.1

Fifteen schoolchildren sit on fifteen numbered chairs. Every minute a kind teacher reseats them according to the following scheme:

\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ 3 & 5 & 10 & 8 & 11 & 14 & 15 & 6 & 13 & 1 & 4 & 9 & 7 & 2 & 12 \end{pmatrix}.

After how many minutes will all the schoolchildren be back in their original seats for the first time?

?

Remark.

?

A permutation of a set is a listing of the elements of this set in an arbitrary order. More rigorously, a permutation of a set is a one-to-one mapping of this set onto itself (i.e., a bijection). It is convenient to depict a permutation $f$ as a directed graph whose vertices are the elements of the set and whose edges go from the vertex $a_k$ to the vertex $f(a_k)$ . The permutation of the set $\{ a_1, a_2, \ldots , a_n\}$ that takes $a_k$ to $f(a_k)$ is written in the form

\begin{pmatrix} a_1 & a_2 & \ldots & a_n \\ f(a_1) & f(a_2) & \ldots & f(a_n) \end{pmatrix};

usually $a_k = k$ for all $k \in \mathscr {R}_n$ . The inverse permutation of $f$ is the permutation $f^{-1}$ written in the form

\begin{pmatrix} f(a_1) & f(a_2) & \ldots & f(a_n) \\ a_1 & a_2 & \ldots & a_n \end{pmatrix}.

A cycle (of length $n$ ) is a permutation of the form

\begin{pmatrix} a_1 & a_2 & \ldots & a_{n-1} & a_n \\ a_2 & a_3 & \ldots & a_n & a_1 \end{pmatrix}.

This permutation is briefly denoted by $(a_1a_2\ldots a_n)$ .

The composition of permutations $f$ and $g$ is the permutation $f\circ g$ defined by the formula $(f\circ g)(x) := f(g(x))$ .

Problem 1.7.2

Find the compositions of permutations of the set of digits

?

(1)

$(12)\circ (13)$ ;

(2)

$(12)\circ (23)$ ;

(3)

$(23)\circ (12)$ ;

(4)

$(123)\circ (132)$ ;

(5)

$(12)\circ (13)\circ (12)$ ;

(6)

$(12345)\circ (12)$ ;

(7)

$(12345)\circ (56789)$ .

Give the answer as a composition of disjoint cycles. For example, $(123)\circ (234) = (12)\circ (34)$ .

From now on, the composition sign is omitted.

Problem 1.7.3

For every permutation $f$ there exists $k>0$ for which $f^k = \mathrm{id}$ (i.e., for which, after the $k$ -fold application of the permutation $f$ , every element is mapped to itself).

The order of a permutation $f$ is the least $k>0$ for which $f^k = \mathrm{id}$ .

?

Problem 1.7.4

Do there exist permutations of a 9-element set of orders $7, 10, 12, 11$ ?

?

Problem 1.7.5

What is the order of a composition of disjoint cycles of $n_1, \ldots , n_k$ elements, respectively?

The permutations of an $(n_1+\ldots +n_k)$ -element set from Problem 1.7.5 are called permutations of type $\langle n_1, \ldots , n_k \rangle$ . For example, the permutations $(14)(253)$ , $(15)(432)$ are of type $\langle 2,3 \rangle$ , while the permutation $(1)(3)(245)$ is of a different type, $\langle 1,1,3 \rangle$ .

?

Problem 1.7.6

(1)(2)(3)

Find the number of permutations of type

?

(1)

$\langle 2,3 \rangle$ ;

(2)

$\langle 3,3 \rangle$ ;

(3)

$\langle 1,2,3,4 \rangle$ .

Problem 1.7.7

(1)(2)(3)

Every permutation can be represented as a composition of

?

(1)

disjoint cycles;

(2)

transpositions, i.e., permutations each of which swaps some two elements and leaves the rest in place (in other words, cycles of length 2);

(3)

transpositions $(1i)$ , $i=2,3,\ldots ,n$ .

Problem 1.7.8

Find two permutations whose compositions yield every permutation of an $n$ -element set.

Permutations $a$ and $b$ are called conjugate if $a = xbx^{-1}$ for some permutation $x$ .

?

Problem 1.7.9

(1)(2)(3)

?

(1)

Permutations $a$ and $b$ are conjugate if and only if their types are the same.

(2)

Let $a$ and $x$ be arbitrary permutations of an $n$ -element set. Then

xax^{-1} = \begin{pmatrix} x(1) & x(2) & \ldots & x(n) \\ x(a(1)) & x(a(2)) & \ldots & x(a(n)) \end{pmatrix}.

In other words, the cycle decomposition of the permutation $xax^{-1}$ is obtained from the cycle decomposition of the permutation $a$ by replacing each element with its $x$ -image: if $a = \displaystyle \prod_{j=1}^{q}(i_{j1},i_{j2},\ldots ,i_{js_j})$ , then

xax^{-1} = \prod _{j=1}^{q}(x(i_{j1}),x(i_{j2}),\ldots ,x(i_{js_j})).

(3)

Find $gf^{-1}g^{-1}f$ for $f := (1,2,\ldots ,N)$ and $g := (N,N+1,\ldots ,L)$ .