0.2.1 Un exemple

Nous allons voir quelles sont ces fonctions dans le cas du système $S=(\{a,b\},<,a^*b^*)$, où $a<b$. Commençons par $val_S$ qui possède une expression simple à formuler (^0.9):

$$val_s(a^pb^q)=\frac{1}{2}(p+q)(p+q+1)+q.$$ (0.3)

Rangés dans l'ordre généalogique, les mots de longueur $t$ de $a^*b^*$ sont en effet les $t+1$ mots

$$a^t<a^{t-1}b<\cdots<ab^{t-1}<b^t$$

et le mot $a^pb^q, p+q=t$, est le $(q+1)$-ième d'entre eux. Ceux qui les précèdent sont en nombre $1+2+\cdots+t=t(t+1)/2$. Le numéro de $a^pb^q$ a donc bien la valeur de $val_S(a^pb^q)$ indiquée ci-dessus.

Pour calculer $r_S(n)$, il faut d'abord déterminer sa longueur. Elle est donnée par

$$t=\sup\{s\in{\rm I\!N}\vert s(s+1)\leq 2n\}.$$

On obtient ensuite $q$ et $p$ par les formules $q=n-\frac{1}{2}t(t+1)$ et $p=t-q$. Vu le choix de $t$, on a en effet $0\leq q\leq t$. De là, $p\geq 0$ et, finalement, $n=val(a^pb^q)$.

Ainsi, pour $n=127$, comme $15.16=240<2.127=254<16.17=272$, il vient $t=15$, $q=n-120=7$ et $p=8$. Par conséquent $127=val_S(a^8b^7)$.