The semigroup of all order-preserving and decreasing transformations in full transformations semigroup $T\_n$ is denoted $C\_n$. 


I consider the idempotent set $A=\{\begin{bmatrix}2\\1 \end{bmatrix},\begin{bmatrix}3\\2 \end{bmatrix},\cdots, \begin{bmatrix}n\\n-1 \end{bmatrix}\}$.
It is well known that $\langle A \rangle = C\_n$. 


I want to determine smallest $k$ suct that $C\_n=\bigcup\limits\_{i=1}^{k} A^k$



A question about semigroup union
$\DeclareMathOperator\im{im}$For ease of notation, let me denote $a\_i=\genfrac[]{0pt}{}{i+1}i$, so that $A=\{a\_1,\dots,a\_{n-1}\}$. I will write multiplication so that $(fg)(x)=f(g(x))$; reverse everything if you want the opposite convention.



> 
> **Proposition:** For any $f\in C\_n$, the least $k$ such that $f$ can be written in the form
>  $$f=a\_{i\_1}a\_{i\_2}\cdots a\_{i\_k}\tag1$$
>  for some $i\_1,\dots,i\_k\in[n-1]$ is
>  $$k=\sum\_{y\in\im(f)}\bigl(\max(f^{-1}(y))-y\bigr).\tag2$$
>  Moreover, for each $i\in[n-1]$, the minimal number of occurrences of $a\_i$ in (1) is
>  $$\bigl|\{y\in[n]:\exists x\in[n]\,(f(x)=y\le i<x)\}\bigr|.\tag3$$
> 
> 
> 


**Proof:**


To prove the upper bound, let me fix $f\in C\_n$ with image
$$\im(f)=\{y\_1,\dots,y\_l\},\qquad1=y\_1<y\_2<\dots<y\_l\le n.$$
Putting $x\_j=\max(f^{-1}(y\_j))$, we have
$$1\le x\_1<x\_2<\dots<x\_l=n,$$
and if we also define $x\_0=0$, then for each $i\in[l]$:
$$f^{-1}(y\_i)=[x\_{i-1}+1,x\_i].$$
In particular, $y\_i\le x\_{i-1}+1$. Now it remains to observe that
$$f=(a\_{y\_l}a\_{y\_l+1}\cdots a\_{x\_l-1})\cdots(a\_{y\_2}a\_{y\_2+1}\cdots a\_{x\_2-1})(a\_{y\_1}a\_{y\_1+1}\cdots a\_{x\_1-1}).$$


For the lower bound, assume $f$ is written as in (1), and let $i\in[n-1]$ and $x\in[n]$ be such that $f(x)\le i<x$. Then
$$x,a\_{i\_k}(x),(a\_{i\_{k-1}}a\_{i\_k})(x),\dots,(a\_{i\_1}a\_{i\_2}\cdots a\_{i\_k})(x)=f(x)$$
is a nonincreasing sequence which may decrease by at most $1$ at each step, hence there is a unique step where it goes from $i+1$ to $i$: that is, there is $j(x)\in[k]$ such that
$$(a\_{i\_{j(x)+1}}\cdots a\_{i\_k})(x)=i+1,\qquad (a\_{i\_{j(x)}}a\_{i\_{j(x)+1}}\cdots a\_{i\_k})(x)=i.$$
Clearly, we must have $i\_{j(x)}=i$. Moreover, if $x'$ is such that $f(x')\le i<x'$, then
$$f(x)\ne f(x')\implies j(x)\ne j(x').\tag4$$
Indeed, if we had $j(x)=j(x')=j$, then
$$(a\_{i\_j}\cdots a\_{i\_k})(x)=(a\_{i\_j}\cdots a\_{i\_k})(x')=i,$$
hence
$$f(x)=(a\_{i\_1}\cdots a\_{i\_k})(x)=(a\_{i\_1}\cdots a\_{i\_{j-1}})(i)=(a\_{i\_1}\cdots a\_{i\_k})(x')=f(x').$$
Now, (4) implies that the number of occurrences of $a\_i$ in (1) is at least (3). Summing over all $i$, we have
$$\begin{align\*}
k&\ge\sum\_i\bigl|\{y\le i:\exists x\in f^{-1}(y)\,(i<x)\}\bigr|\\
&=\bigl|\{(i,y):y\le i\land\exists x\in f^{-1}(y)\,(i<x)\}\bigr|\\
&=\sum\_y\bigl|\{i:y\le i\land\exists x\in f^{-1}(y)\,(i<x)\}\bigr|\\
&=\sum\_{y\in\im(f)}\bigl(\max(f^{-1}(y))-y\bigr),
\end{align\*}$$
proving (2). QED


If $f\in C\_n$ of image size $l$ is written as in the proof of the upper bound, (2) gives
$$k=\sum\_{j=1}^l(x\_j-y\_j).$$
This expression is maximized (for a given $l$) when the $x\_j$ are maximized, i.e., $x\_j=n+j-l$, and $y\_j$ are minimized, i.e., $y\_j=j$. Thus,
$$k\le\sum\_{j=1}^l(n+j-l-j)=l(n-l)\le\lfloor n/2\rfloor\lceil n/2\rceil=\lfloor n^2/4\rfloor.$$
This bound is attained for the function $f(x)=\max(1,x-\lfloor n/2\rfloor)$. Thus:



> 
> **Corollary:** The answer to the question is $k=\lfloor n^2/4\rfloor$.
> 
> 
> 


