Combien de mots de longueur

MODIFIÉ POUR AJOUTER : Il est maintenant essentiellement répondu à cette question; veuillez consulter cette entrée de blog pour plus de détails. Merci à tous ceux qui ont posté des commentaires et des réponses ici.

---

QUESTION ORIGINALE

Il s'agit, espérons-le, d'une version plus intelligente et mieux informée d'une question que j'ai posée sur MathOverflow. Lorsque j'ai posé cette question, je ne connaissais même pas le nom du domaine des mathématiques dans lequel se trouvait mon problème. Maintenant, je suis presque sûr que cela réside dans la combinatoire algorithmique des mots partiels. (Livre récent sur le sujet ici .)

Je veux faire une liste de mots sur $l$ lettres. Chaque mot a une longueur exactement $k$ . Le problème est que, si $a \lozenge ^j b$ est dans la liste, où $\lozenge$ est un symbole générique / indifférent, alors $a \lozenge ^j b$ ne peut plus réapparaître dans la liste. (Il en va de même si $a=b$ , ou si $j=0$ et donc le sous-mot interdit est $ab$ .)

Exemple où $k=4$ et $l=5$ :

$abcd$
$bdce$
$dcba$ <- interdit car$dc$ apparaissait dans la ligne au
dessus de a e e $aeed$ <- interdit car$a \lozenge \lozenge d$ apparaissait sur la première ligne

La littérature sur les «mots partiels évitables» que j'ai trouvée a tous été infinitaire - éventuellement un modèle de mot est inévitable si la taille du mot est assez grande. Je voudrais trouver des versions finitaires de ces théorèmes. Alors, question:

Etant donné un mot partiel de forme dans un alphabet de l lettres, combien de mots de longueur k l' évitent et peuvent-ils être explicitement produits en temps polynomial?$a \lozenge^j b$$l$$k$

Je ne m'attends pas à ce que la question ci-dessus soit difficile et, à moins qu'il n'y ait une subtilité qui me manque, je pourrais la calculer moi-même. La vraie raison pour laquelle je poste sur ce site est parce que j'ai besoin d'en savoir beaucoup plus sur les propriétés de ces listes de mots pour mon application, j'espère donc que quelqu'un pourra répondre à la question de suivi:

Cela a-t-il été étudié en général? Quels sont les articles qui examinent, non seulement si un mot partiel est finalement inévitable, mais "combien de temps cela prend" avant qu'il ne devienne inévitable?

Merci.

Voici un cas particulier: le nombre de mots binaires de longueur tels qu'aucun deux n'apparaissent consécutivement est F ( k + 3 ) , où F ( n ) est le n t h nombre de Fibonacci (commençant par F ( 1 ) = 1 , F ( 2 ) = 1 ). La preuve se fait via la représentation de Zeckendorf .$k$$F(k+3)$$F(n)$$n^{th}$$F(1)=1, F(2)=1$

EDIT: Nous pouvons étendre ce cas spécial initial dans le cas spécial légèrement plus grand de . Considérons des chaînes de longueur k sur un alphabet de taille l + 1 de sorte que la lettre a n'apparaisse pas deux fois de suite. Soit f ( k ) le nombre de ces chaînes (que nous appellerons "valides"). Nous affirmons que: f ( k ) = l ∗ f ( k - 1 ) + l ∗ f ( k - 2 $a\lozenge^0a$$k$$l+1$$a$$f(k)$

$$f(k) = l*f(k-1) + l*f(k-2)$$ L'intuition est que nous pouvons construire une chaîne valide de longueur k soit: a) en joignant l'une des l lettres qui ne sont pas a à une chaîne valide de longueur k - 1 , ou b) à côté de la lettre a puis de toute autre lettre sauf a à une chaîne valide de longueur k - 2 . $$f(0) = 1, f(1) = l+1$$ $k$$l$$a$$k-1$$a$$a$$k-2$

Vous pouvez vérifier que ce qui suit est un formulaire fermé pour la récurrence ci-dessus: où nous comprenons lorsque .

$$f(k) = \sum_{i=0}^{k} {{k+1-i}\choose{i}} l^{k-i}$$ ${{n}\choose{i}} = 0$$i>n$

EDIT # 2: Supprimons un autre cas - un . Nous appellerons des chaînes sur un alphabet à éléments qui ne contiennent pas la sous-chaîne , "valide" et laissons désigner l'ensemble des chaînes valides de longueur . De plus, définissons comme le sous-ensemble de composé de chaînes commençant par et comme étant celles ne commençant pas par . Enfin, soit,,.$\lozenge^0 b, a \neq b$$l$$ab$$S_k$$k$$T_k$$S_k$$b$$U_k$$b$$f(k) = |S_k|$$g(k) = |T_k|$$h(k) = |U_k|$

On observe que et . Ensuite, nous déduisons les récurrences suivantes: La première vient du fait que l'ajout d'un au début de tout élément de produit un élément de . La seconde vient de l'observation que l'on peut construire un élément de en ajoutant n'importe quel caractère mais au début de n'importe quel élément de ou en ajoutant n'importe quel caractère sauf ou au début de n'importe quel élément dans .$g(0)=0, h(0)=1, f(0)=1$$g(1)=1, h(1)=l-1, f(1)=l$

$$\begin{eqnarray} g(k+1) &=& f(k) \\ h(k+1) &=&(l-1)*h(k) + (l-2)*g(k) \end{eqnarray}$$ $b$$S_k$$T_{k+1}$$U_{k+1}$$b$$U_{k}$$a$$b$$T_k$

Ensuite, nous réorganisons les équations de récurrence pour obtenir:

$$\begin{eqnarray} f(k+1) &=& g(k+1) + h(k+1) \\ &=& f(k) + (l-1)*h(k) + (l-2)*g(k) \\ &=& f(k) + (l-1)*f(k) - g(k) \\ &=& l*f(k) - f(k-1) \end{eqnarray}$$

Nous pouvons obtenir une solution de forme fermée plutôt opaque à cette récurrence en nettoyant un peu avec la génération de choses fonctionnelles ou, si nous sommes paresseux, en nous dirigeant directement vers Wolfram Alpha . Cependant, avec un peu de recherche et de fouille dans OEIS , nous constatons que nous avons en fait: où est le polynôme de Chebyshev du deuxième type (!) .

$$f(k) = U_k(l/2)$$ $U_k$$k^{th}$

Une approche complètement différente pour la première question réutilise les réponses à la question récente sur la génération de mots dans une langue régulière : il suffit d'appliquer ces algorithmes de longueur sur la langue régulière où est l'alphabet.$k$$\Sigma^\ast a\Sigma^j b\Sigma^\ast$$\Sigma$

Mis à jour: cette réponse est incorrecte :

en supposant que est fixe, nous pouvons compter le nombre de façons dont un motif peut être mis en correspondance: le premier symbole peut être mis en correspondance à une position , et nous avons possibilités avant ce point, entre et , et pour le reste de la chaîne, donc un total de cas. Comme indiqué par Tsuyoshi Ito dans les commentaires, ce nombre n'est pas le nombre de mots différents correspondant à$j$$a\lozenge^j b$$a$$1\leq i\leq k-j-1$$l^{i-1}$$l^j$$a$$b$$l^{k-j-i-1}$

$$\sum_{i=1}^{k-j-1}l^{i-1}\cdot l^{j}\cdot l^{k-j-i-1}=(k-j-1)l^{k-2}$$ $a\lozenge^j b$puisqu'un seul mot peut correspondre au même modèle de différentes manières. Par exemple, correspond trois fois dans , deux fois dans et deux fois dans . Nous pouvons essayer de compter le nombre de façons de faire correspondre les motifs plusieurs fois et de présenter une expression "inclusion-exclusion", mais les façons dont les motifs peuvent se chevaucher la rendent trop longue.$aa$$aaaa$$ab$$abab$$a\lozenge b$$aabb$

---

Pour la première question, étant entendu que n'est pas fixe, c'est-à-dire que l'on veut éviter d'incorporer le mot :$j$$ab$

• soit premier symbole n'apparaît jamais, ce qui représente mots possibles,$a$$(l-1)^k$
• ou apparaît d'abord dans une position , alors nous ne pouvons pas utiliser dans le reste du mot: il y a choix pour le facteur jusqu'à , et choix pour le reste, donnant au total mots possibles. Si n'est pas pertinent.$a$$1\leq i\leq k$$b$$(l-1)^{i-1}$$a$$(l-1)^{k-i}$$\sum_{i=1}^k(l-1)^{i-1}\cdot(l-1)^{k-i}=k(l-1)^{k-1}$$a=b$

Pour la deuxième question, je n'ai pas grand-chose à suggérer; il y a une relation avec l'intégration de mots, mais les résultats que je connais sur les mauvaises séquences du lemme de Higman ne s'appliquent pas immédiatement.