Generators of Transformation Monoid

Question

Let X be a finite set of cardinality N. Then the set of all functions from X to X form a monoid wrt composition. What would be the size of its minimal set of generators?

Answer 1

The minimum number of generators is three (for $N\ge 3$). First, consider the permutations of $X$. It takes two permutations to generate $S_n$, so at least two generators need to be permutations. However, not all of the generators can be permutations, so at least one more generator is needed. Letting $X=\{0,1,2,\dots,n-1\}$, the following three functions suffice:

1. $x\mapsto x+1\pmod n$.
2. $f(0)=1,f(1)=0$, and $f(x)=x$ for $x=2,3,\dots,n-1$.
3. $g(0)=g(1)=0$,$\;\;\;$ and $g(x)=x$ for $x=2,3,\dots,n-1$.

The first two functions in the above list are permutations which are well known to generate $S_n$. The last function allows you to map two different inputs to the same output, which in combination with the first two functions lets you make all functions.