# Generators of Transformation Monoid

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?

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.