\documentclass[12pt]{article}
\newtheorem{probleme}{Probl\`eme}
\newtheorem{conjecture}{Conjecture}
\newtheorem{proposition}{Proposition}
\newtheorem{corollaire}{Corollaire}
\begin{document}
\title{Ensembles in\'evitables}
\author{Guo-Niu Han$^1$ et Dominique Perrin$^2$\\
\\
\small $^1$IRMA, CNRS et Universit\'e Louis-Pasteur, 7, rue Ren\'e-Descartes\\
\small F-67084 Strasbourg\\
\small \kern-6pt$^2$Institut Gaspard Monge, Universit\'e de Marne-la-Vall\'ee, 5, boulevard Descartes,\\
\small Champs sur Marne, F-77454 Marne la Vallee
}
\date{}
\def\id{\hbox{id}}
\maketitle

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8 
\font\its=cmti8 
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 47 \rms (2002), Article~B47e\hfill}
\def\thepage{}
%
%

{\bf R\'esum\'e}.
Un ensemble de mots $X$ sur un alphabet $A$ est dit
{\it in\'evitable} si tout mot infini sur $A$ a
un facteur dans $X$.  
Nous discutons ici sans la r\'esoudre une conjecture\footnote{
Cette conjecture vient d'\^etre r\'esolue par Georges Hansel et 
Jean-Marc Champarnaud.}
suivant laquelle, pour chaque entier $n$,
il existe un syst\`eme de repr\'esentants
des classes circulaires de mots de longueur $n$
qui est aussi un ensemble in\'evitable.
Dans cette Note, nous \'etudions des probl\`emes
directement li\'es \`a cette conjecture :
les classes permutativement circulaires,
la conjecture dans les cas des petits $n$
et l'extension aux syst\`emes de type fini.

\section{Introduction}

Un ensemble de mots $X$ sur un alphabet $A$ est dit
{\it in\'evitable} si tout mot infini sur $A$ a
un facteur dans $X$. Par exemple, $\{aa,b\}$
est un ensemble in\'evitable sur deux lettres, mais
$\{aa,bb\}$ ne l'est pas. On pourra se reporter \`a
\cite{Lothaire01} (Chapitre 1, Section 6)
%%Han: Pour un gros livre, il vaux mieux de preciser 
%%     le chapitre et les pages
pour des r\'ef\'erences sur cette
notion et sur les sources ant\'erieures.

Les ensembles in\'evitables form\'es de mots de
m\^eme longueur  ont \'et\'e
\'etudi\'es par M.-P. Sch\"utzengberger dans
\cite{Schutzenberger64}, qui a \'etudi\'e en particulier
le cardinal minimal des ensembles
in\'evitables de mots de longueur $n$ \`a $k$ lettres.


On note $s_n(k)$ (resp. $q_n(k)$) le nombre de classes 
de conjugu\'es de mots (resp. de mots primitifs) de 
longueur $n$ sur un alphabet \`a $k$ lettres.
On a  $s_n(k)=\sum_{d|n}q_d(k)$. De plus, comme cela est 
bien connu \cite{Lothaire01}
$$q_n(k)=\frac{1}{n}\sum_{d|n}\mu(n/d)k^d$$
o\`u $\mu$ d\'esigne la fonction de M\"obius, et aussi
$$s_n(k)=\frac{1}{n}\sum_{d|n}\varphi(n/d)k^d$$
o\`u $\varphi$ d\'esigne la fonction d'Euler. Ceci permet
un calcul direct des $s_n$.
Pour $k=2$, les valeurs de $q_n(2)$ et $s_n(2)$
pour $n\leq 13$ sont donn\'ees ci-dessous.
$$\begin{array}{c|ccccccccccccc}
n  &1&2&3&4 &5 &6 &7  &8  &9&10&11&12&13\\ \hline
q_n(2)&2&1&2&3 &6 & 9&18 & 30&56&99&186&335&630\\ 
s_n(2)&2&3&4&6 &8 &14&20 &36 &60&108&188&352&632
\end{array}$$
Pour $k=3$, on obtient
$$\begin{array}{c|cccccccccccc}
n  &1&2&3&4 &5 &6 &7  &8  &9&10&11\\ \hline
q_n(3)&3&3&8&18&48&116&312&810&2184&5880&16104\\ 
s_n(3)&3&6&11&24&51&130&315&834&2195&5934&16107
\end{array}
$$
A partir d'un mot de longueur $n$, on peut fabriquer
un mot infini dont tous les facteurs de longueur $n$
sont dans une m\^eme classe circulaire. On a ainsi~:

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
%\markboth{\SMALL ROLAND BACHER AND LAURENT MANIVEL}{\SMALL HOOKS AND POWERS OF PARTS IN PARTITIONS}
%
%

\begin{proposition}
Un ensemble in\'evitable de mots de longueur $n$ sur
un alphabet \`a $k$ lettres rencontre chaque classe
de conjugu\'es de mots de longueur $n$. Par cons\'equent, 
on a
$\alpha(k,n) \geq s_n(k)$.
\end{proposition}
Le r\'esultat suivant a \'et\'e d\'emontr\'e par
Sch\"utzenberger \cite{Schutzenberger64}.
\begin{proposition}

$$
\lim_{n\rightarrow\infty}  \alpha(k,n)/s_n(k) =1.
$$
\end{proposition}
Nous allons montrer, dans la section 3, qu'il 
existe un ensemble in\'evitable de mots binaires de 
longueur $n$ avec exactement $s_n(2)$ \'el\'ements 
pour $n\leq 9$. Ceci plaide en faveur de la conjecture 
suivante.
\begin{conjecture}
Pour tout entier  $n\geq 1$, il existe un ensemble
in\'evitable de $s_n(k)$ mots de longueur $n$ sur $k$ 
lettres, i.e., $\alpha(k,n) = s_n(k)$.
\end{conjecture}

Cette Note est organis\'ee comme suit~:
Dans la section 2, nous introduissons la notion
de classes permutativement circulaires, qui g\'en\'eralise
la notion de classe circulaire classique. Nous 
indiquons le lien avec les ensembles in\'evitables.
Des formules pour calculer les nombres de classes 
permutativement circulaires sont \'egalement fournies.
Dans la section 3, nous pr\'esentons les diff\'erents cas 
particulier pour v\'erifier la conjecture 1.
Enfin, nous \'etudions le probl\`eme des ensembles
in\'evitables pour les syst\`emes de type fini. 


\section{Classes permutativement circulaires}

Soient $A$ un alphabet fini et $\sigma$ une permutation
sur $A$, qui envoie la lettre $a$ en $a'=\sigma(a)$. 
Pour tout mot $w=x_1x_2x_3\cdots x_{n-1}x_n$
de longueur $n$, on pose
$w'=x_2x_3x_4\cdots x_{n} x_1'$. 
On dit que $w'$ est le {\it permutativement circulaire} de $w$.
Cet op\'erateur permutativement circulaire d\'efinit bien
une relation d'\'equivalence, associ\'ee 
\`a $\sigma$, sur l'ensemble des mots de $A$ de longueur $n$.
On peut donc former les classes d'\'equivalence permutativement 
circulaires.

En particulier, dans le cas des mots binaires, il existe deux
permutations d'ordre 2, ainsi deux classes permutativement circulaires.
Celle associ\'ee \`a la permutation identique $(a)(b)$
est simplement la classe circulaire classique. La seconde,
qui est associ\'ee \`a la permutation $(ab)$, est appel\'ee
aussi la classe {\it anti-circulaire}.

Par exemple, pour $n=5$, il y a 8 classes circulaires
classiques
$$
\begin{array}{c|c}
0  &aaaaa\cr\hline
1  &aaaab,aaaba,aabaa,abaaa,baaaa\cr\hline
2  &aaabb,aabba,abbaa,baaab,bbaaa\cr\hline
3  &aabab,abaab,ababa,baaba,babaa\cr\hline
4  &aabbb,abbba,baabb,bbaab,bbbaa\cr\hline
5  &ababb,abbab,babab,babba,bbaba\cr\hline
6  &abbbb,babbb,bbabb,bbbab,bbbba\cr\hline
7  &bbbbb\cr\hline
\end{array}
$$
et 4 classes anti-circulaire :
$$
\begin{array}{c|c}
anti0  &aaaaa,aaaab,aaabb,aabbb,abbbb,bbbbb,baaaa,bbaaa,bbbaa,bbbba\cr\hline
anti1  &aaaba,abaaa,baaab,aabab,babaa,abbba,ababb,bbaba,babbb,bbbab\cr\hline
anti2  &aabaa,aabba,abbaa,abaab,baaba,baabb,bbaab,abbab,babba,bbabb\cr\hline
anti3  &ababa,babab\cr\hline
\end{array}
$$
Soit $w=x_1x_2\cdots x_n$ un mot de longueur $n$.
On note $\sigma(w)=x_1'x_2'\cdots x_n'$. Alors tous
les facteurs du mot infini
$\cdots\sigma^{-2}(w)\cdot\sigma^{-1}(w)\cdot w\cdot
\sigma(w)\cdot\sigma^{2}(w)\cdots$
sont permutativement circulaires associ\'e \`a $\sigma$.
On obtient ainsi le r\'esultat suivant~:
\begin{proposition}
Pour toute permutation $\sigma$ sur $A$, tout ensemble 
in\'evitable de mots de longueur $n$ sur $A$ rencontre 
chaque classe permutativement circulaire associ\'ee \`a $\sigma$
de mots de longueur $n$.
\end{proposition}
Par exemple, pour les mots binaires de longueur $n=5$,
l'ensemble in\'evitable suivant (repr\'esent\'e en gras) 
rencontre \`a la fois chaque classe circulaire et 
anti-circulaire.
$$\begin{array}{c|c|c|c|c}
   & anti0  & anti1 & anti2 & anti3 \\ \hline 
0  &{\bf aaaaa} &&&\\ 
1  &{\bf aaaab},baaaa &aaaba,abaaa &aabaa&\\
2  &aaabb,bbaaa &{\bf baaab} &aabba,abbaa&\\ 
3  &  &aabab,babaa &{\bf abaab},baaba&ababa\\ 
4  &aabbb,bbbaa&abbba&baabb,{\bf bbaab}&\\ 
5  &  &ababb,bbaba &abbab,babba&{\bf babab}\\ 
6  &abbbb,bbbba& babbb,bbbab &{\bf bbabb}&\\ 
7  &{\bf bbbbb} &&&\\ \hline
\end{array}
$$
Pour toute permutation $\sigma$ sur $A$, on note
$s_n(\sigma)$ le nombre des classes permutativement circulaires
de mots de longueur $n$, associ\'ees \`a $\sigma$.
En utilisant la th\'eorie de P\'olya, en particulier,
le lemme de Cauchy-Frobenius-Burnside (voir par exemple \cite{Kerber91}),
nous obtenons la formule suivante pour calculer $s_n(\sigma)$.
\begin{proposition} % Prop 2
Soit $\sigma$ une permutation d'ordre $k$ ayant 
$c_1$ cycles de long\-ueur~$1$,
$c_2$ cycles de longueur~$2$, $\ldots$,
$c_k$ cycles de longueur~$k$.
Alors le nombre $s_n(\sigma)$ des classes permutativement 
conjugu\'ees associ\'ees \`a la permutation $\sigma$  
est donn\'e par la formule suivante~:
$$
s_n(\sigma) = {1\over mn} 
\sum_{d|n}
\sum_{j=0 \atop\gcd(j,d)=1}^{md-1} 
\Bigl( \sum_{r|j} rc_r \Bigr)^{n/d},
$$
o\`u $m$ est le plus petit entier tel que $\sigma^m=\id$.
\end{proposition}
\medskip
Nous ne reproduisons pas la d\'emonstration de cette Proposition.
Dans le cas classique, $\sigma$ est la permutation identique;
on retrouve imm\'edia\-te\-ment la formule $s_n(k)$. Nous allons
\'etudier un autre cas sp\'ecial, lorsque $\sigma$ est une permutation
circulaire $(123\cdots k)$. 
\begin{corollaire} % Prop 2
Soit $\sigma$ la permutation circulaire $(123\cdots k)$ d'ordre 
$k$.
Alors le nombre $s_n(\sigma)$ des classes permutativement 
conjugu\'ees associ\'ees \`a la permutation $\sigma$  
est donn\'e par la formule suivante~:
$$
s_n(\sigma) = {1\over kn} 
\sum_{d|n \atop\gcd(n/d,k)=1} 
\varphi(n/d) k^d.
$$
\end{corollaire}

\section{Les cas des  petits entiers $n$}
Nous pr\'esentons dans cette section les diff\'erents
cas pour les petites valeurs de $n$ ($n\leq 9$) et de
$k$  ($2\leq k\leq 4$). On verra que dans
tous les cas pour $k=2$ on trouve un ensemble in\'evitable
de cardinal minimal $s_n(k)$. Pour $k=3$, on n'est parvenu \`a 
atteindre que les valeurs $n\leq 4$.
\subsection{Les cas $n\leq 4$}
Pour $n=1$, il y a un seul ensemble in\'evitable qui est 
l'alphabet lui-m\^eme. Pour $n=2$, sur $A=\{a_0,a_1,\ldots,a_{k-1}\}$,
on a un ensemble in\'evitable de $s_2(k)=k(k+1)/2$ \'el\'ements
$$X=\{a_ia_j\mid i\leq j\}.$$
Pour $n=3,4$, on a $s_3(k)=(k^3+2k)/3$ et $s_4(k)=(k^4+k^2+2k)/4$.

Sur deux lettres, on a les ensembles suivants. Chaque mot
est donn\'e en regard de la puissance de mot de Lyndon correspondante.
$$\begin{array}{c|c|c}
&\mbox{Lyndon}&\mbox{In\'evitable}\\\hline
0&aaa&aaa\\
1&aab&aba\\
2&abb&abb\\
3&bbb&bbb\\
\end{array}
\qquad
\begin{array}{c|c|c}
&\mbox{Lyndon}&\mbox{In\'evitable}\\\hline
0&aaaa&aaaa\\
1&aaab&aaab\\
2&aabb&baab\\
3&abab&baba\\
4&abbb&bbab\\
5&bbbb&bbbb\\ 
\end{array}
$$
Le nombre d'ensembles in\'evitables des mots binaires
est donn\'e par le tableau 
ci-dessous.
$$\begin{array}{c|c|c|c|c|c|c|c|c|c}
n&1&2&3&4  &5 & 6 & 7 & 8 & 9 \\\hline
 &1&2&4&30 &28 & 68288 & \geq 6643 & \geq 8223 & \geq 1\\
\end{array}
$$

Pour $n=3$ et $k=3,4$ , on a les ensembles in\'evitables suivants.
$$\begin{array}{c|c|c}
&\mbox{Lyndon}&\mbox{In\'evitable}\\\hline
0&aaa&aaa\\
1&aab&aab\\
2&aac&caa\\
3&abb&bab\\
4&abc&cab\\
5&acb&acb\\
6&acc&cac\\
7&bbb&bbb\\
8&bbc&bcb\\
9&bcc&ccb\\
10&ccc&ccc\\
\end{array}
\qquad
\begin{array}{c|c|c||c|c|c}
&\mbox{Lyndon}&\mbox{In\'evit.}&
&\mbox{Lyndon}&\mbox{In\'evit.}\\\hline
0&aaa &aaa &12&add &dad\\
1&aab& aba & 13&bbb &bbb\\
2&aac& caa & 14&bbc &cbb\\
3&aad&daa & 15&bbd &dbb\\
4&abb& abb & 16&bcc &cbc\\
5&abc &cab & 17&bcd &dbc\\
6&abd& dab & 18&bdc &cbd\\
7& acb&cba & 19&bdc &dbd\\
8& acc&cac & 20&ccc &ccc\\
9&acd &cda & 21&ccd &cdc\\
10& adb&dba &22&cdd &cdd\\
11&adc &cad & 23& ddd&ddd \\
\end{array}
$$         
Pour $n=4$, on trouve
$$\begin{array}{c|c|c||c|c|c}
&\mbox{Lyndon}&\mbox{In\'evitable}&
&\mbox{Lyndon}&\mbox{In\'evitable}\\\hline
0&aaaa& aaaa & 12&abcc& ccab\\
1&aaab& aaab & 13&acac& caca\\
2&aaac& acaa & 14&acbb& cbba\\
3&aabb& baab & 15&acbc& acbc\\
4&aabc& caab & 16&accb& ccba\\
5&aacb& acba & 17&accc& cacc\\
6&aacc& aacc & 18&bbbb& bbbb\\
7&abab& baba & 19&bbbc& cbbb\\
8&abac& acab & 20&bbcc& cbbc\\
9&abbb& babb & 21&bcbc& cbcb\\
10&abbc& bcab & 22&bccc& cbcc\\
11&abcb& bcba & 23&cccc& cccc\\
\end{array}
$$   
\subsection{Le cas $n=5$}
 Pour $n=5$, on a l'ensemble suivant, d\^u \`a   Christopher Saker
  (communication personnelle, juin
2000).
$$\begin{array}{c|c|c}
&\mbox{Lyndon}&\mbox{In\'evitable}\\\hline
0&aaaaa&aaaaa\\
1&aaaab&aaaab\\
2&aaabb&baaab\\
3&aabab&abaab\\
4&aabbb&bbaab\\
5&ababb&babab\\
6&abbbb&bbabb\\
7&bbbbb&bbbbb\\     
\end{array}
$$
Il contredit l'affirmation donn\'ee dans
 Lothaire (\cite{Lothaire97}, Exercise 6.2
page 99) suivant laquelle 9 mots sont n\'ec\'essaires. Il n'est jamais
trop tard pour s'amender. Il y a en fait 28 ensembles in\'evitables
pour $n=5$.

\subsection{Le cas $n=6$}
Pour $n=6$, Christopher Saker (communication personnelle, septembre 2000,
\cite{HigginsSaker01})
a trouv\'e l'ensemble  figurant dans la seconde colonne ci-dessous.

Une \'enum\'eration syst\'ematique de tous les choix possibles
de $6^9\times 3^2\times 2\approx 10^8$ pour conjuguer les puissances
de mots de Lyndon  permet d'obtenir la troisi\`eme colonne
apr\`es $\approx 3\times 10^6$
it\'erations (quelques minutes).

Un tirage au hasard des 14 entiers  donne
la troisi\`eme colonne en moins de
 $10^{3}$ essais (instantan\'e).

$$
\begin{array}{r|c|c|c|c}
&\mbox{Lyndon}&\mbox{Saker}&\mbox{Enum}&\mbox{Random}\\
\hline
0&aaaaaa&aaaaaa&aaaaaa&aaaaaa\\
1&aaaaab&aaaaba&aaaaab&abaaaa\\
2&aaaabb&aaaabb&baaaab&abbaaa\\
3&aaabab&baaaba&abaaab&abaaab\\
4&aaabbb&baaabb&bbaaab&aabbba\\
5&aabaab&abaaba&abaaba&abaaba\\
6&aababb&bbaaba&aababb&abbaab\\
7&aabbab&abaabb&abaabb&bbabaa\\
8&aabbbb&bbaabb&bbaabb&abbbba\\
9&ababab&bababa&ababab&bababa\\
10&ababbb&bababb&abbbab&babbba\\
11&abbabb&bbabba&babbab&babbab\\
12&abbbbb&bbabbb&babbbb&abbbbb\\
13&bbbbbb&bbbbbb&bbbbbb&bbbbbb\\
\end{array}
$$

Le nombre total de syst\`emes de repr\'esentants des classes
circulaires  est
 $6^9\times 3^2\times 2\approx 10^8$.
Le nombre d'ensembles in\'evitables minimaux est $68288$.
La densit\'e des ensembles in\'evitables par rapport au nombre total 
de syst\`emes de repr\'esentants des classes circulaires pour
$n\leq 6$ est donn\'ee ci-dessous.
$$\begin{array}{c|cccccc}
n&1 &2 &3   &4  &5       &6\\ \hline
 &1 &1 &0,4 &0,2&10^{-2} &6\times10^{-3}
\end{array}
$$
\subsection{Le cas $n=7$}
Le nombre total de syst\`emes de repr\'esentants des classes
circulaires est $7^{18}\approx 10^{15}$.
Nous avons obtenu l'ensemble ci-dessous par une m\'ethode mixte
\'enum\'e\-ra\-tion/tirage au hasard. Le nombre de tirages porte sur
$\approx 10^6$ ensembles (ex\'ecution en moins d'une heure). 
L'\'enum\'eration consiste \`a choisir les mots
de petite p\'eriode. Par exemple, le mot de p\'eriode 2
doit \^etre un conjugu\'e du mot de Lyndon d'indice
 10 ou
15 (avec une seule possibilit\'e pour chacun).
L'\'enum\'eration pure peut tourner pendant plusieurs heures
sans r\'esultat.

$$
\begin{array}{r|c|c||c|c|c}
&\mbox{Lyndon}&\mbox{In\'evitable}&
&\mbox{Lyndon}&\mbox{In\'evitable}\\ \hline
0&aaaaaaa&aaaaaaa&10&aababab&abababa\\
1&aaaaaab&aaabaaa&11&aababbb&abbbaab\\
2&aaaaabb&aaabbaa&12&aabbabb&abbabba\\
3&aaaabab&aababaa&13&aabbbab&abbbaba\\
4&aaaabbb&abbbaaa&14&aabbbbb&bbbbaab\\
5&aaabaab&aabaaba&15&abababb&babbaba\\
6&aaababb&ababbaa&16&ababbbb&bbbbaba\\
7&aaabbab&aabbaba&17&abbabbb&bbbabba\\
8&aaabbbb&bbbbaaa&18&abbbbbb&bbbabbb\\
9&aabaabb&baabbaa&19&bbbbbbb&bbbbbbb\\
\end{array}
$$
\subsection{Les cas $n=8,9$}
Pour $n=8,9$ sur deux lettres, des ensembles in\'evitables minimaux 
contiennent 36 et 60 mots respectivement.
Dans le cas $n=8$, le nombre total de syst\`emes de repr\'esentants
de classes circulaires est 
$$1^2 \cdot 2^2 \cdot 4^3\cdot 8^{30} \approx 1,58 \times 10^{29}.$$
Dans le cas $n=9$, le nombre total de syst\`emes de repr\'esentants
des classes circulaires est 
$$1^2\cdot 3^2 \cdot 9^{56} \approx 2,46 \times 10^{54}.$$
Comme la densit\'e des ensembles in\'evitables est de plus en plus
faible (Y a-t-il une d\'emonstration math\'ematique?), 
pour trouver les quelques ensembles in\'evitables parmi une quantit\'e
astronomique d'ensembles possibles, nous utilisons le fait suivant~:
 
\medskip
{\bf Fait}: Soit $A$ un ensemble in\'evitable de longueur $n$. On construit
un ensemble $B$ par enl\`evement de la derni\`ere lettre des mots dans $A$.
Alors $B$ est un ensemble in\'evitable de longueur $n-1$.
\medskip

En effet, on doit utiliser l'inverse du fait pr\'ec\'edent, qui 
n'est plus un fait, mais plut\^ot une pr\'evoyance :
\medskip

{\bf Pr\'evoyance}: Soit $B$ un ensemble in\'evitable de longueur
$n-1$. On construit une famille d'ensembles $A_1, A_2, \ldots$
par ajout d'une derni\`ere lettre (soit $a$, soit $b$) dans les mots
de $B$.
Alors il y a beaucoup de chances de trouver un ensemble in\'evitable
de longueur $n$ parmi les ensembles $A_i$.
\medskip

Pour utiliser cette m\'ethode, nous avons d'abord \'enum\'er\'e
tous les ensembles in\'evitables de longueur $6$. Il y en a
68288. A partir de cette famille d'ensemble, nous avons trouv\'e
6643 ensembles in\'evitables de longueur $7$, 
8223 ensembles in\'evitables de longueur $8$, 
1 ensemble in\'evitable de longueur $9$. 
La liste des ensembles peut \^etre consult\'e sur le web~:

\centerline{\tt http://www-irma.u-strasbg.fr/\~{}guoniu/papers/set}



\section{Syst\`emes de type fini}
Soit $S$ un syst\`eme de type fini, c'est \`a dire un ensemble
de mots infinis dans lequel on interdit l'apparition d'un
nombre fini de mots. (voir \cite{LindMarcus95}
pour la d\'efinition pr\'ecise de ce terme). On note $s_n=s_n(S)$
le nombre d'orbites de points de p\'eriode $n$ dans $S$ (aussi
appel\'ees {\em colliers} de longueur $n$). On note
$p_n=p_n(S)$
le nombre de points de p\'eriode $n$ et $q_n=q_n(S)$ le nombre
d'orbites de p\'eriode exatement $n$. On pose
$$\zeta(S)=\exp\sum_{n\geq 1}\frac{p_n}{n}z^n=\frac{1}{1-\sum_{n\geq
    1}u_nz^n}.$$
On a alors pour tout $n\geq 1$
$$p_n=nu_n+\sum_{1\leq i\leq n-1}p_iu_{n-i}$$
et
$$p_n=\sum_{d|n}dq_d.$$
Comme $s_n=\sum_{d|n}q_d$ ces formules permettent de calculer
$s_n$ en fonction des $p_n$ et donc des $u_n$.
De plus, on a
$$s_n=\frac{1}{n}\sum_{d|n}\varphi(n/d)p_d$$
o\`u $\varphi$ d\'esigne la fonction d'Euler. Ceci permet
un calcul direct des $s_n$.


Si $S$ est une partie de $A^Z$ et $X$ une partie de $A^*$, on dit
que $X$ est in\'evitable dans $S$ si tout \'el\'ement de $S$
a un facteur dans $X$.
\begin{proposition}
Soit $S$ un syst\`eme de type fini sur l'alphabet $A$
 et $n\geq 0$ un entier. Si $X$ est un ensemble in\'evitable
de mots de longueur $n$, il contient au moins un repr\'esentant
de chaque collier 
de p\'eriode $d$ pour $d|n$. On a donc $Card(X)\geq s_n(S)$.
\end{proposition} 
D\'emonstration. Soit $s=w^\zeta$ un mot de p\'eriode  $n$ de $S$. Comme $X$
est in\'evitable, il existe un facteur de $s$ qui est dans $X$. Ainsi,
$X$ contient un conjugu\'e de $w$.

\begin{probleme}  Soit $S$ un systeme de type fini. Pour quels
entiers $n$  existe-t-il un ensemble in\'evitable de $s_n(S)$
mots de longueur $n$?
\end{probleme}
La r\'eponse n'est pas toujours positive. En effet, si $S=(ab)^\zeta$,
un tel ensemble n'existe que pour $n$ pair (on a $s_n=0$ pour $n$ impair).

\subsection{Pas de $bb$}
Si $S$ est le syst\`eme $S_{bb}$
des mots qui \'evitent $bb$ sur deux lettres,
on a $$\zeta(S)=\frac{1}{1-z-z^2}.$$ On en d\'eduit les valeurs
suivantes.

$$\begin{array}{c|ccccccccccccc}
n  &1&2&3&4&5 &6 &7 &8 &9&10&11&12&13\\ \hline
p_n&1&3&4&7&11&18&29&47&76&123&199&322&521\\\hline
q_n&1&1&1&1&2 &2 &4 &5 &8&11&18&25&40\\ \hline
s_n&1&2&2&3&3 &5 &5 &8 &10&15&19&31&41
\end{array}$$
Pour $S_{bb}$, on a les ensembles in\'evitables minimaux suivants
pour $n\leq 9$.

$$\begin{array}{c|c|c|c|c|c|c|c|c|c}
 &1&2 & 3 &4   &5    &6     &7      &8       &9\\ \hline
0 &a&aa&aaa&aaaa&aaaaa&aaaaaa&aaaaaaa&aaaaaaaa&aaaaaaaaa \\ \hline
1 & &ab&aba&aaba&aabaa&aaaaba&aaabaaa&aaaabaaa&aaaabaaaa\\ \hline
2 & &  &   &baba&ababa&abaaab&aababaa&ababaaaa&aababaaaa\\ \hline
3 & &  &   &    &     &abaaba&aabaaba&aabaabaa&aaaabaaba\\ \hline
4 & &  &   &    &     &bababa&abababa&abaaabaa&aabaaabaa\\\hline
5 & &  &   &    &     &      &       &ababaaab&aabababaa\\\hline
6 & &  &   &    &     &      &       &ababaaba&aababaaab\\\hline
7 & &  &   &    &     &      &       &abababab&aababaaba\\\hline
8 & &  &   &    &     &      &       &        &baabaabaa\\\hline
9 & &  &   &    &     &      &       &        &ababababa\\\hline
\end{array}$$
Sur 3 lettres, on a pour le syst\`eme $S_{aa}$ des mots qui \'evitent
$aa$ sur 3 lettres $a,b,c$ tout d'abord $\zeta(S)=\frac{1}{1-2z-2z^2}$.
On en d\'eduit les valeurs suivantes.
$$\begin{array}{c|ccccc}
n  &1&2&3&4&5\\ \hline
p_n&2&8&20&56&152\\\hline
q_n&2&3&6&12&30\\ \hline
s_n&2&5&8&17&32
\end{array}$$
Pour $n\leq 4$, on obtient les ensembles in\'evitables suivants.
$$\begin{array}{c|c|c|c|c|c|c|c|c|c}
n&1&2 & 3 &4   \\ \hline
 &b&ab&bab&abab\\ \hline
 &c&ac&bca&abac\\ \hline
 & &bb&bac&bbab\\ \hline
 & &bc&cac&bcab\\ \hline
 & &cc&bbb&abcb\\\hline
 & &  &bcb&abcc\\\hline
 & &  &bcc&acac\\\hline
 & &  &ccc&bbac\\\hline
 & &  &   &bcac\\\hline
 & &  &   &cbac\\\hline
 & &  &   &ccac\\\hline
 & &  &   &bbbb\\\hline
 & &  &   &bbcb\\\hline
 & &  &   &bbcc\\\hline
 & &  &   &cbcb\\\hline
 & &  &   &ccbc\\\hline
 & &  &   &cccc\\\hline
\end{array}$$
\subsection{Pas de $bbb$}
Pour $S_{bbb}$, on a 
$$\zeta(z)=\frac{1}{1-z-z^2-z^3}.$$
On en d\'eduit les valeurs suivantes.
$$\begin{array}{c|ccccccccccccc}
n  &1&2&3&4&5 &6 &7 &8 &9&10&11&12&13\\ \hline
p_n&1&3&7&11&21&39&71&131&241&443&2757\\\hline
q_n&1&1&2&2&4 &5 & 10&15 &26&42&74&121&212\\ \hline
s_n&1&2&3&4&5 &9 & 11& 19&29&48&75&132&213
\end{array}$$
On a pour $n\leq 7$ les ensembles in\'evitables minimaux suivants.
$$\begin{array}{c|c|c|c|c|c|c|c}
 &1&2 & 3 &4   &5    &6     &7      \\ \hline
0 &a&aa&aaa&aaaa&aaaaa&aaaaaa&aaaaaaa\\ \hline
1 & &ab&aab&aaba&aabaa&aaaaba&aaabaaa\\ \hline
2 & &  &bab&abba&aabba&abaaab&aababaa\\ \hline
3 & &  &   &abab&ababa&abaaba&aabaaba\\ \hline
4 & &  &   &    &babba&bababa&abababa\\\hline
5 & &  &   &    &     &bbabba&abbabba\\\hline
6 & &  &   &    &     &ababba&aababba\\\hline
7 & &  &   &    &     &baabba&aabbaba\\\hline
8 & &  &   &    &     &aaabba&aabbaaa\\\hline
9 & &  &   &    &     &      & bababba\\\hline
10& &  &   &    &     &      &aabbaab \\\hline
\end{array}$$
\subsection{Autres syst\`emes}

Le probl\`eme peut se pr\'esenter differemment pour des syst\`emes
de type finis isomorphes. Ainsi, pour $S=(a+bc)^\zeta$ qui est
isomorphe a $(a+ba)^\zeta$, on a tout d'abord pas d'ensemble in\'evitable
de $s_n$ mots de longueur $n$ pour $n$ impair. En effet, le mot
$(bc)^\zeta$ n'a pas de facteur r\'ep\'etable de longueur impaire. Les ensembles
suivants sont in\'evitables pour $n=2,4,6$.
$$\begin{array}{c|c|c|c}
n&2 &4    &6\\ \hline
 &aa&aaaa &aaaaaa \\ \hline
 &bc&abca &bcbcbc  \\ \hline
 &  &bcbc&aabcaa \\ \hline
 &  &    &abcbca \\ \hline
 &  &    &bcabca  \\ \hline
\end{array}
$$
Pour $n=8$, il n'existe pas d'ensemble in\'evitable de 8 mots de longueur
$8$. En effet, le seul facteur r\'ep\'etable de longueur 8 de $(abc)^\zeta$
est $w=bcabcabc$. Mais les seuls facteurs r\'ep\'etables de longueur 8
du mot $(abcbc)^\zeta$ sont $abcbcabc$ et $bcabcbca$ qui sont conjugu\'es
de $w$.
\section{Emboitements}
On peut imaginer construire des ensembles in\'evitables pour le
syst\`eme plein en compl\'etant progressivement des ensembles
in\'evitables pour des syst\`emes de type fini plus petits.

Plus pr\'ecis\'ement, on peut construire un ensemble in\'evitable
minimal $X=\{aaaa,baba,aaba,abba,bbba,bbbb\}$
pour $n=4$ de la fa\c{c}on suivante.
On consid\`ere la suite
$$ \emptyset\subset S_b\subset S_{bb}\subset S_{bbb}.$$
et aussi
$$ X_3\subset X_2\subset X_1\subset X,$$
o\`u
$X_3\!=\!\{bbbb,bbba\}, X_2\!=\!\{bbbb,bbba,abba\},
X_1\!=\!\{bbbb,bbba,abba,aaba,baba\}$.
On a
\begin{eqnarray*}
S_{bbb}&=&S_{X_3}\\
S_{bb}&=&S_{X_2}\\
S_b&=&S_{X_1}\\
\emptyset&=&S_X
\end{eqnarray*}
On peut compl\'eter un ensemble in\'evitable du syst\`eme $S_{bb}$
en un ensemble in\'evitable du syst\`eme $S_{bbb}$ en construisant
un ensemble in\'evitable pour les mots qui ont le facteur $bb$
mais pas le facteur $bbb$. 



Les r\'esultats pour $n\leq 8$ sont
repr\'esent\'es ci-dessous.
$$\begin{array}{c|c|c|c|c|c|c|c|c}
 &1&2 & 3 &4   &5    &6     &7      &8\\ \hline
0 & &bb&abb&abba&abbaa&abbaaa&aaabbaa&abbaaaaa \\\hline
1 & &  &   &    &abbab&abbaab&aababba&abbaaaab \\\hline
2 & &  &   &    &     &abbaba&baabbaa&abbaaaba \\\hline
3 & &  &   &    &     &abbabb&abbabba&abbaaabb \\\hline
4 & &  &   &    &     &      &aabbaba&abbaabaa \\\hline
5 & &  &   &    &     &      &bababba&abbaabab \\\hline
6 & &  &   &    &     &      &       &abbaabba \\\hline
7 & &  &   &    &     &      &       &aaabbaba \\\hline
8 & &  &   &    &     &      &       &ababbaba \\\hline
9 & &  &   &    &     &      &       &abaabbab \\\hline
10 & &  &   &    &     &      &       &abbabbab \\\hline
\end{array}
$$
Pour le syst\`eme plein sur deux lettres $S=\{a,b\}^Z$, on parvient \`a construire pour chaque  $n\leq 7$ un ensemble in\'evitable
par emboitement des syst\`emes $S_{b^i}$ pour $i\leq n$.
$$\begin{array}{c|c|c|c|c|c|c|c|}
 &1&2 & 3 &4   &5    &6     &7      \\ \hline
0 &a&aa&aaa&aaaa&aaaaa&aaaaaa&aaaaaaa       \\ \cline{2-8}
1 &b&ab&aba&aaba&aabaa&aaaaba&aaabaaa       \\ \cline{2-4}
2 & &bb&abb&baba&ababa&abaaab&aababaa       \\ \cline{3-6}
3 & &  &bbb&abba&abbaa&abaaba&aabaaba       \\ \cline{4-5}
4 & &  &   &bbba&abbab&bababa&abababa       \\ \cline{5-8}
5 & &  &   &bbbb&abbba&abbaaa&aaabbaa       \\ \cline{5-6}
6 & &  &   &    &bbbba&abbaab&aababba       \\ \cline{6-6}
7 & &  &   &    &bbbbb&abbaba&baabbaa       \\ \cline{6-6}
8 & &  &   &    &     &abbabb&abbabba       \\ \cline{7-7}
9 & &  &   &    &     &abbbaa&aabbaba       \\ 
10 & &  &   &    &     &abbbab&bababba       \\ \cline{7-8}
11 & &  &   &    &     &abbbba&abbbaaa       \\ \cline{7-7}
12 & &  &   &    &     &abbbbb&abbbaab       \\ \cline{7-7}
13 & &  &   &    &     &bbbbbb& abbbaba      \\ \cline{7-7}
14 & &  &   &    &     &      & abbbabb     \\ \cline{8-8}
15 & &  &   &    &     &      &abbbbaa  \\ 
16 & &  &   &    &     &      &abbbbab  \\ \cline{8-8}
17 & &  &   &    &     &      &abbbbba  \\ \cline{8-8}
18 & &  &   &    &     &      &bbbbbba  \\ \cline{8-8}
19 & &  &   &    &     &      &bbbbbbb  \\ \cline{8-8}
\end{array}$$
On obtient donc ainsi une m\'ethode de construction d'ensembles
in\'evitables minimaux.
Nous ne savons pas si cette construction est toujours possible.

\bibliographystyle{plain}
%\bibliography{Inevitables}
\begin{thebibliography}{1}

\bibitem{HigginsSaker01}
Peter~M. Higgins and Christopher~J. Saker.
\newblock Unvoidable sets of words of uniform length.
\newblock Technical report, University of Essex, 2001.

\bibitem{Kerber91}
Adalbert Kerber.
\newblock {\em Algebraic combinatorics via finite group actions}.
\newblock Wissenschaftsverlag, 1991.

\bibitem{LindMarcus95}
Douglas Lind and Brian~H. Marcus.
\newblock {\em An Introduction to Symbolic Dynamics and Coding}.
\newblock Cambridge, 1995.

\bibitem{Lothaire97}
M.~Lothaire.
\newblock {\em Combinatorics on words}.
\newblock Cambridge University Press, Cambridge, 1997.

\bibitem{Lothaire01}
M.~Lothaire.
\newblock {\em Algebraic Combinatorics on Words}.
\newblock Cambridge University Press, 2001.
\newblock \`a para\^{\i}tre, disponible sur \\ {\tt
  http://www-igm.univ-mlv.fr/\~{}berstel/Lothaire/index.html}.

\bibitem{Schutzenberger64}
Marcel-Paul Sch{\"u}tzenberger.
\newblock On the synchronizing properties of certain prefix codes.
\newblock {\em Inform. and Control}, 7:23--36, 1964.

\end{thebibliography}



\end{document}