Wie viele Wörter der Länge

EDITIERT ZUM HINZUFÜGEN : Diese Frage ist jetzt im Wesentlichen beantwortet; Weitere Informationen finden Sie in diesem Blogeintrag . Vielen Dank an alle, die hier Kommentare und Antworten gepostet haben.

---

URSPRÜNGLICHE FRAGE

Dies ist eine hoffentlich intelligentere und besser informierte Version einer Frage, die ich in MathOverflow gestellt habe. Als ich diese Frage stellte, wusste ich nicht einmal, in welchem ​​Bereich der Mathematik sich mein Problem befand. Jetzt bin ich mir ziemlich sicher, dass es in der algorithmischen Kombinatorik für Teilwörter liegt. (Aktuelles Buch zu diesem Thema hier .)

Ich möchte eine Liste von Wörtern auf $l$ Buchstaben erstellen. Jedes Wort hat eine Länge von genau $k$ . Der Deal ist, wenn $a \lozenge ^j b$ in der Liste ist, wobei $\lozenge$ ein Platzhalter / egal-Symbol ist, dann kann $a \lozenge ^j b$ nie wieder in der Liste erscheinen. (Dasselbe gilt, wenn $a=b$ oder wenn $j=0$ und daher das verbotene Unterwort $ab$ .)

Beispiel mit $k=4$ und $l=5$ :

$abcd$
$bdce$
$dcba$ <- verboten, weil$dc$ in der Zeile über
$aeed$ <erschien - verboten, weil$a \lozenge \lozenge d$ in der ersten Zeile erschien

Die Literatur zu "vermeidbaren Teilwörtern", die ich gefunden habe, war alle unendlich - schließlich ist ein Wortmuster unvermeidlich, wenn die Wortgröße groß genug ist. Ich würde gerne Endversionen solcher Theoreme finden. Also, Frage:

Wie viele Wörter der Länge k vermeiden ein Teilwort der Form in einem Alphabet aus l Buchstaben und können explizit in Polynomzeit erzeugt werden?$a \lozenge^j b$$l$$k$

Ich erwarte nicht, dass die obige Frage schwierig sein wird, und wenn es keine Subtilität gibt, die mir fehlt, könnte ich sie selbst berechnen. Der wahre Grund, warum ich auf dieser Website poste, ist, dass ich viel mehr über die Eigenschaften solcher Wortlisten für meine Anwendung wissen muss. Ich hoffe, dass jemand die folgende Frage beantworten kann:

Wurde dies allgemein untersucht? Was sind einige Artikel, die berücksichtigen, nicht nur, ob ein Teilwort letztendlich unvermeidbar ist, sondern "wie lange es dauert", bis es unvermeidlich wird?

Vielen Dank.

Hier ist ein Sonderfall: Die Anzahl der binären Wörter der Länge so dass keine zwei nacheinander erscheinen, ist F ( k + 3 ) , wobei F ( n ) die n t h Fibonacci-Zahl ist (beginnend mit F ( 1 ) = 1 , F ( 2 ) = 1 ). Der Nachweis erfolgt über die Zeckendorfer Darstellung .$k$$F(k+3)$$F(n)$$n^{th}$$F(1)=1, F(2)=1$

EDIT: Wir können diesen anfänglichen Sonderfall auf den etwas größeren Sonderfall von . Betrachten Sie Zeichenfolgen der Länge k über einem Alphabet der Größe l + 1 , sodass der Buchstabe a nicht zweimal hintereinander erscheint. Sei f ( k ) die Anzahl solcher Strings (die wir "gültig" nennen werden). Wir behaupten, dass: 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)$$ Die Intuition ist, dass wir eine gültige Zeichenfolge der Länge k konstruieren können, indem wirentweder: a) einen der l Buchstaben, die nicht a sind, an eine gültige Zeichenfolge der Länge k anschließen - 1 oder b) neben dem Buchstaben a und dann jedem anderen Buchstaben außer a an eine gültige Zeichenfolge der Länge k - 2 . $$f(0) = 1, f(1) = l+1$$ $k$$l$$a$$k-1$$a$$a$$k-2$

Sie können überprüfen, ob das Folgende eine geschlossene Form für die obige Wiederholung ist: wo wir verstehen wenn .(

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

EDIT # 2: Lassen Sie uns einen weiteren Fall - a . Wir werden Strings über ein Element-Alphabet aufrufen , das nicht die Teilzeichenfolge , "valid", und die Menge der gültigen Strings der Länge . Weiter definieren wir als die Teilmenge von die aus Zeichenfolgen besteht, die mit und als Zeichenfolgen , die nicht mit . Schließlich sei,,.l a b S k k T k S k b U k b f ( k ) = | S k | g ( k ) = | T k | h ( k ) = | U k $\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|$

Wir beobachten, dass und . Als nächstes schließen wir die folgenden Wiederholungen: Das erste ergibt sich aus der Tatsache, dass das Hinzufügen eines zum Anfang eines Elements von ein Element von . Die zweite ergibt sich aus der Beobachtung, dass wir ein Element von konstruieren können, indem wir ein beliebiges Zeichen außer an die Vorderseite eines Elements von hinzufügen oder indem wir ein beliebiges Zeichen außer oder an die Vorderseite eines Elements hinzufügen in .g ( 1 ) = 1 , h ( 1 ) = l - 1 , f ( 1 ) = l g ( k + 1 $g(0)=0, h(0)=1, f(0)=1$$g(1)=1, h(1)=l-1, f(1)=l$ bSkTk+1Uk+1bUkabT

$$\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$

Als nächstes ordnen wir die Wiederholungsgleichungen neu an, um zu erhalten:

$$\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}$$

Wir können eine ziemlich undurchsichtige Lösung in geschlossener Form für diese Wiederholung erhalten, indem wir ein bisschen mit dem Generieren von Funktionsmaterial herumspielen oder, wenn wir faul sind, direkt zu Wolfram Alpha gehen . Mit ein wenig googeln und herumstöbern in OEIS stellen wir jedoch fest, dass wir tatsächlich haben: wobei das Chebyshev-Polynom der zweiten Art (!) .U k k t

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

Ein völlig anderer Ansatz für die erste Frage verwendet die Antworten auf die jüngste Frage zur Erzeugung von Wörtern in einer regulären Sprache erneut : Es reicht aus, diese Algorithmen für die Länge auf die reguläre Sprache anzuwenden wo das Alphabet ist.Σ * a Σ j b Σ *$k$$\Sigma^\ast a\Sigma^j b\Sigma^\ast$$\Sigma$

Aktualisiert: Diese Antwort ist falsch :

unter der Annahme festgelegt ist, können wir die Anzahl der Zählung Wege ein Muster angepaßt werden kann: der erste Symbol kann an einer bestimmten Position angepasst werden , und wir haben Möglichkeiten vor diesem Punkt, zwischen und und für den Rest der Zeichenkette, also insgesamt Fälle. Wie von Tsuyoshi Ito in den Kommentaren bemerkt, ist diese Anzahl nicht die Anzahl der verschiedenen Wörter, die mit übereinstimmena ◊ j b a 1 ≤ i ≤ k - j - 1 l i - 1 l j a b l k - j - i - 1 k - j - 1 ∑ i = 1 l i - 1 ⋅ l j ⋅ l k - j - i - 1 = ( k - $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$da ein einzelnes Wort auf unterschiedliche Weise mit demselben Muster übereinstimmen könnte. Zum Beispiel wird dreimal in , zweimal in und zweimal in . Wir können versuchen, die Anzahl der Arten des Abgleichs von Mustern mehrmals zu zählen und einen "Einschluss-Ausschluss" -Ausdruck anzuzeigen, aber die Art und Weise, wie sich Muster überlappen, macht dies zu lang.$aa$$aaaa$$ab$$abab$$a\lozenge b$$aabb$

---

Für die erste Frage, unter der Voraussetzung, dass nicht festgelegt ist, dh dass wir vermeiden möchten, das Wort :$j$$ab$

• entweder das erste Symbol erscheint nie, was mögliche Wörter erklärt,$a$$(l-1)^k$
• oder erscheint zuerst an einer Position , dann können wir im Rest des Wortes nicht verwenden: Es gibt Auswahlmöglichkeiten für den Faktor bis zu und Auswahlmöglichkeiten für den Rest, wobei insgesamt mögliche Wörter. Ob ist irrelevant.1 ≤ i ≤ k b ( l - 1 ) i - 1 a ( l $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$

Für die zweite Frage habe ich nicht viel vorzuschlagen; Es gibt eine Beziehung zu Worteinbettungen, aber die Ergebnisse, die ich über schlechte Sequenzen für Higmans Lemma kenne, gelten nicht sofort.