Ile słów długości

EDYTOWANO, ABY DODAĆ : Na to pytanie zasadniczo udzielono odpowiedzi; zobacz ten wpis na blogu, aby uzyskać więcej informacji. Dziękujemy wszystkim, którzy opublikowali tutaj komentarze i odpowiedzi.

---

PYTANIE ORYGINALNE

Jest to, mam nadzieję, mądrzejsza i lepiej poinformowana wersja pytania, które zadałem na MathOverflow. Kiedy zadałem to pytanie, nie znałem nawet nazwy dziedziny matematyki, w której tkwi mój problem. Teraz jestem całkiem pewien, że leży ona w kombinatoryce algorytmicznej na słowach częściowych. (Najnowsza książka na ten temat tutaj .)

Chcę zrobić listę słów $l$listy. Każde słowo ma dokładnie długość$k$. Umowa jest, jeśli$a \lozenge ^j b$ jest na liście, gdzie $\lozenge$ jest zatem symbolem wieloznacznym / nieważnym $a \lozenge ^j b$nigdy więcej nie pojawi się na liście. (To samo dotyczy, jeśli$a=b$, albo jeśli $j=0$ i stąd zabronione jest podtytuł $ab$.)

Przykład gdzie $k=4$ i $l=5$:

$abcd$
$bdce$
$dcba$ <- zabronione, ponieważ $dc$ pojawił się w linii powyżej
$aeed$ <- zabronione, ponieważ $a \lozenge \lozenge d$ pojawił się w pierwszej linii

Znaleziona przeze mnie literatura na temat „częściowych słów, których można uniknąć”, jest nieskończona - ostatecznie nie można uniknąć jakiegoś wzoru słów, jeśli rozmiar słowa jest wystarczająco duży. Chciałbym znaleźć skończone wersje takich twierdzeń. Pytanie:

Biorąc pod uwagę częściowe słowo formy $a \lozenge^j b$ w alfabecie $l$ litery, ile słów długości $k$ unikaj go i czy można je jawnie wytworzyć w czasie wielomianowym?

Nie oczekuję, że powyższe pytanie będzie trudne i, chyba że brakuje mi subtelności, sam bym mógł ją obliczyć. Prawdziwym powodem, dla którego publikuję na tej stronie jest to, że muszę dowiedzieć się znacznie więcej o właściwościach takich list słów dla mojej aplikacji, dlatego mam nadzieję, że ktoś odpowie na kolejne pytanie:

Czy zbadano to ogólnie? Co rozważają niektóre dokumenty, nie tylko to, czy częściowe słowo jest w końcu nieuniknione, ale „ile czasu” zajmuje, zanim staje się nieuniknione?

Dzięki.

Oto szczególny przypadek: liczba dwójkowych słów długości $k$ tak, że nie pojawiają się dwa kolejne $F(k+3)$, gdzie $F(n)$ jest $n^{th}$ Liczba Fibonacciego (od $F(1)=1, F(2)=1$). Dowodem jest reprezentacja Zeckendorfa .

EDYCJA: Możemy rozszerzyć tę początkową specjalną skrzynkę na nieco większy specjalny przypadek $a\lozenge^0a$. Rozważ ciągi długości$k$ ponad alfabet wielkości $l+1$ tak, że list $a$nie pojawia się dwa razy pod rząd. Pozwolić$f(k)$być liczbą takich ciągów (które nazywamy „prawidłowymi”). Twierdzimy, że:

$$f(k) = l*f(k-1) + l*f(k-2)$$ $$f(0) = 1, f(1) = l+1$$ Intuicja polega na tym, że możemy skonstruować prawidłowy ciąg długości $k$ przez: a) przyleganie do dowolnego z $l$ litery, które nie są $a$ na prawidłowy ciąg długości $k-1$lub b) przylegające do litery $a$ a następnie każdy inny list oprócz $a$ na prawidłowy ciąg długości $k-2$.

Możesz sprawdzić, czy poniższy formularz jest zamknięty dla powyższej rekurencji: gdzie rozumiemy gdy .

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

EDYCJA 2: Wyrzućmy jeszcze jedną sprawę - a . łańcuchy nad alfabetem elementowym, który nie zawiera podłańcucha , „ważny”, a oznacza zbiór prawidłowych łańcuchów o długości . Ponadto, zdefiniujmy jako podzbiór składający się z łańcuchów zaczynających się na a na te, które nie zaczynają się na . Na koniec niech,,.$\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|$

Obserwujemy i . Następnie wnioskujemy o następujących nawrotach: Pierwszy wynika z faktu, że dodanie na początku dowolnego elementu daje element . Drugi wynika z obserwacji, że możemy zbudować element , dodając dowolny znak oprócz z przodu dowolnego elementu lub dodając dowolny znak oprócz lub z przodu dowolnego elementu w .$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$

Następnie przestawiamy równania rekurencyjne, aby uzyskać:

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

Możemy uzyskać raczej nieprzejrzyste zamknięte rozwiązanie tego nawrotu, trochę się mijając z generowaniem funkcji lub, jeśli jesteśmy leniwi, kierujemy się prosto do Wolfram Alpha . Jednak przy odrobinie googlingu i przeszukiwania w OEIS , okazuje się, że faktycznie mamy: gdzie jest wielomianem drugiego rodzaju (!) .

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

Zupełnie inne podejście do pierwszego pytania ponownie wykorzystuje odpowiedzi na ostatnie pytanie dotyczące generowania słów w zwykłym języku : wystarczy zastosować te algorytmy dla długości w zwykłym języku gdzie jest alfabetem.$k$$\Sigma^\ast a\Sigma^j b\Sigma^\ast$$\Sigma$

Zaktualizowano: ta odpowiedź jest niepoprawna :

przy założeniu, jest stała, można policzyć liczbę sposobów, wzór można dopasować: pierwszy symbol może być dopasowana w pewnej pozycji , i mają możliwości wcześniejszy, między a i dla pozostałej części łańcucha, przez co w sumie . Jak zauważył Tsuyoshi Ito w komentarzach, liczba ta nie jest liczbą różnych słów pasujących$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$ponieważ jedno słowo może pasować do tego samego wzoru na różne sposoby. Na przykład, jest dopasowywana trzy razy w , dwa razy w , a dwa razy w . Możemy spróbować policzyć liczbę sposobów dopasowania wzorców kilka razy i wyświetlić wyrażenie „wykluczenie włączenia”, ale sposoby, w jakie wzór może się nakładać, powodują, że jest to zbyt długie.$aa$$aaaa$$ab$$abab$$a\lozenge b$$aabb$

---

W przypadku pierwszego pytania, przy założeniu, że nie jest ustalone, tzn. Że chcemy uniknąć osadzania słowa :$j$$ab$

• albo pierwszy symbol nigdy nie pojawia się, co stanowi możliwych słów$a$$(l-1)^k$
• lub pojawia się najpierw w jakiejś pozycji , a następnie nie możemy użyć w pozostałej części słowa: istnieją opcje dla współczynnika do , i wyborów dla reszty, dając w sumie możliwe słowa. Czy jest nieistotne.$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$

W przypadku drugiego pytania nie mam wiele do zaproponowania; istnieje związek z osadzaniem słów, ale wyniki, które znam o złych sekwencjach dla Lemmy Higmana, nie mają natychmiastowego zastosowania.