Bonne réponse, bravo Je trouve les mes nombres que toi.

@nodgim : non, les résultats divergent légèrement de ta formule à partir de n=6.

J'ai employé la même méthode qu'enigmatus, si tu vois ce que je veux dire. Ça ne veut pas pour autant dire qu'il n'y a pas une autre façon de faire, mais ça me parait compliqué.

@Franky1103 : effectivement, il doit y avoir des doublons car la bonne réponse est nettement inférieure. Quant à la loi forte des petits nombres, elle dit en substance que ce n'est pas parce qu'une suite commence par 1,2,3,4,5 que le terme suivant sera 6, il faut se méfier des motifs que l'on voit parfois émerger.

Bonjour,
J'en trouve 390 de aaabaaac à cccbcccc

Merci aux participants. Félicitations à ceux qui ont trouvé : la méthode la plus évidente était de fabriquer un programme pour calculer la valeur recherchée. Il est, comme souvent, surprenant qu'une définition aussi simple engendre tant de complications.

Ha, ravi de voir que tu t'es penché sur la question. J'ai commencé à creuser, mais je n'ai pas encore tout essayé.

Pour l'instant, j'ai remarqué que la parité du nombre de "a" de tous les mots de taille n est la même que celle de n, et celle de"b" et de "c" est différente de celle de n. Par exemple, les mots de taille 6 ont 0, 2 ou 4 "a", et 1, 3 ou 5 "b", ainsi que 1, 3 ou 5 "c".

Par ailleurs, si un mot appartient au dictionnaire, c'est le cas de son "antisymétrique" obtenu en le renversant et en inversant les "b" et "c" : par exemple, "acaaab" appartient au dictionnaire, donc "caaaba" aussi. À noter que certains mots sont leur propre antisymétrique, comme caab.

J'ai tendance à représenter le dictionnaire sur un arbre, dont la racine est "a", et dont un étage contient tous les mots de taille n. On relie par une arête un mot de taille n à tous les mots de taille n+1 obtenus en transformant une seule de ses lettres, par exemple, les fils du mot cac sont abac, cbcc et caab.

On remarque facilement que si un mot a deux fils, alors ces deux fils ont eux-mêmes un fils commun. En ce moment, j'essaie de mettre à jour de telles propriétés, plus précises, pour affiner un encadrement du nombre de mots de taille n.

Par exemple, j'ai trouvé un mot qui a deux parents, mais ces deux parents ne sont pas des frères. Ça fait un bon exercice pour ceux qui ont le courage

Quel est le plus long mot du dico d'Ebichu qu'on peut trouver dans cette suite de 40 lettres ?

bacbcbbcbacaccccccbbcbbabbccaacbaccabbcc

Suite fournie par la fonction " ALEA() " d'un tableur.

ça se fait à la main, moyennant une bonne méthode.

Je suis impatient de voir ça....

Un autre truc marrant, c'est qu'on peut fabriquer un mot du dico avec autant de lettres qu'on veut sans la moindre analyse ni référence aux nombres plus petits.

Non, je n'ai pas de recette pour éviter de tester les différents cas. Il s'agit juste de les ordonner de la façon la plus efficace possible, aussi je ne garantis pas d'avoir la meilleure méthode. J'attends encore un peu avant de la présenter.

Sinon, encore une singularité sur les mots de ce dico (il ne payait pas de mine comme ça au début, cet algorithme, mais il est plein de ressources...) : En partant de 2  nombres du dico longs de x et y lettres, on peut les concaténer, moyennant une adaptation simple, pour en faire un autre mot du dico long de x+y lettres.

Ben, on remarque qu'en développant à partir de "a" systématiquement la lettre de droite, on obtient :
a
bc
bab
baca
bacbc
bacbab
bacbaca...
c'est-à-dire n fois "bac" suivi de "a", ou "bc", ou "bab". Ainsi on a un mot du dico de la taille que l'on veut.

Pour la concaténation, on sait que le premier mot comme le deuxième se ramènent à "a". Si on décale toutes les lettres du premier d'un rang, et toutes les lettres du deuxième de deux rangs, ils se ramènent respectivement à "b" et à "c", donc la concaténation de ces deux nouveaux mots se ramène à "bc", donc à "a". C'est donc un mot du dico. Etait-ce ton idée ?

Mmh, cette histoire de concaténation est intéressante.

On démontre assez facilement que tout mot du dico issu de a s'exprime comme concaténation de deux mots plus petits. Jusqu'aux mots de 6 lettres, il y a une unique façon de procéder, ce qui permet de justifier l'égalité entre le nombre de mots de n lettres et les nombres de Catalan. En effet, un mot correspond à un parenthésage : par exemple, (a+(a+a))+a = (a+bc)+a = bab + a = cbcc.

À partir des mots de 7 lettres, il y a divergence : le nombre de Catalan vaut 132, mais la suite ne vaut que 128, ce qui traduit qu'il doit y avoir des mots de 7 lettres qui s'expriment de plusieurs façons comme la concaténation de mots plus petits. Lesquels ? Je n'ai pas encore eu le temps de le déterminer (un petit programme devrait faire ça très bien).

Ainsi, on obtient une majoration du n-ième terme de la suite par les nombres de Catalan qui est efficace pour les petites valeurs de n, mais nettement moins ensuite (asymptotiquement, moins que le majorant de l'ordre de 3^n/8 que j'ai donné plus haut).

L'arbre

Pour fabriquer un mot du dico de n lettres, on fabrique un arbre avec n-1 " V ". Un 1er V en bas et pour les suivants on pose leur pointe sur l'une des branches libres. Toutes les combinaisons sont autorisées, ainsi on peut concevoir un arbre élancé mais étroit si chaque V est posé sur l'une des branches les plus hautes, ou au contraire un arbre étalé mais bas où chaque V est posé sur l'une des branches les plus basses.

Une fois le dessin fait, il faut donner une lettre a, b ou c à chaque branche. On établit pour cela un chemin orienté qui démarre en bas à gauche de l'arbre et qui longe toutes les branches 2 fois, le 1er passage en montant par la gauche, le second en descendant par la droite. Quand le chemin est tracé, c'est comme si on avait enveloppé l'arbre d'une écorce.
Les lettres qu'on donnera aux différentes branches successives rencontrées le long du chemin sont : bcabcabc... et si on n'a pas fait d'erreur la dernière branche est obligatoirement "c".

Le mot se lit alors directement sur le chemin orienté: ce sont les seules n branches à extrémités libres successivement rencontrées.