MathDB

We consider an integer

n \ge 3,

the set

S=\{1,2,3,\ldots,n\}

and the set

\mathcal{F}

of the functions from

S

S.

We say that

\mathcal{G} \subset \mathcal{F}

is a generating set for

\mathcal{H} \subset \mathcal{F}

if any function in

\mathcal{H}

can be represented as a composition of functions from

\mathcal{G}.

a) Let the functions

a:S \to S,

a(n-1)=n,

a(n)=n-1

and

a(k)=k

for

k \in S \setminus \{n-1,n\}

and

b:S \to S,

b(n)=1

and

b(k)=k+1

for

k \in S \setminus \{n\}.

Prove that

\{a,b\}

is a generating set for the set

\mathcal{B}

of bijective functions of

\mathcal{F}.

b) Prove that the smallest number of elements that a generating set of

\mathcal{F}

has is

3.

Problem Statement