Question 138
Let $n \ge 3$ be a positive integer, the set $S = \{1, 2, 3, \dots, n\}$, and the set $\mathcal{F}$ of functions from $S$ to $S$. We say that a set $\mathcal{G} \subset \mathcal{F}$ is a *generating set* for the set $\mathcal{H} \subset \mathcal{F}$ if every function in $\mathcal{H}$ can be represented as a composition of functions from $\mathcal{G}$.
a. Let $a : S \to S$ be defined by $a(n-1) = n$, $a(n) = n-1$, $a(k) = k$ for $k \in S \setminus \{n-1, n\}$, and let $b : S \to S$ be defined by $b(n) = 1$ and $b(k) = k+1$ for $k \in S \setminus \{n\}$. Show that $\{a, b\}$ is a generating set for the set $\mathcal{B}$ of bijective functions from $\mathcal{F}$.
b. Show that the minimum number of elements in a generating set for $\mathcal{F}$ is 3.
a. Let $a : S \to S$ be defined by $a(n-1) = n$, $a(n) = n-1$, $a(k) = k$ for $k \in S \setminus \{n-1, n\}$, and let $b : S \to S$ be defined by $b(n) = 1$ and $b(k) = k+1$ for $k \in S \setminus \{n\}$. Show that $\{a, b\}$ is a generating set for the set $\mathcal{B}$ of bijective functions from $\mathcal{F}$.
b. Show that the minimum number of elements in a generating set for $\mathcal{F}$ is 3.