Quantas palavras de comprimento

EDITADO PARA ADICIONAR : Esta questão agora está essencialmente respondida; consulte esta entrada do blog para obter mais detalhes. Obrigado a todos que postaram comentários e respostas aqui.

---

PERGUNTA ORIGINAL

Esta é uma versão esperançosamente mais inteligente e bem informada de uma pergunta que fiz no MathOverflow. Quando fiz essa pergunta, eu nem sabia o nome da área da matemática em que estava o meu problema. Agora, tenho certeza de que está na Combinatória Algorítmica de Palavras Parciais. (Livro recente sobre o assunto aqui .)

Quero fazer uma lista de palavras em $l$ letras. Cada palavra tem comprimento exatamente $k$ . O negócio é, se $a \lozenge ^j b$ está na lista, onde $\lozenge$ é um símbolo wildcard /-cuidado não tem, então, $a \lozenge ^j b$ pode nunca aparecem novamente na lista. (O mesmo vale se $a=b$ , ou se $j=0$ e, portanto, a subpalavra proibida é $ab$ .)

Exemplo onde $k=4$ e $l=5$ :

$abcd$
$bdce$
$dcba$ <- proibida por causa$dc$ apareceu na linha acima
$aeed$ <- proibida porque$a \lozenge \lozenge d$ apareceu na primeira linha

A literatura sobre "palavras parciais evitáveis" que encontrei foi infinita - eventualmente algum padrão de palavras é inevitável se o tamanho da palavra for grande o suficiente. Eu gostaria de encontrar versões financeiras de tais teoremas. Então, pergunta:

Dada uma palavra parcial da forma em um alfabeto de l letras, quantas palavras de comprimento k a evitam e podem ser explicitamente produzidas em tempo polinomial?$a \lozenge^j b$$l$$k$

Não espero que a pergunta acima seja difícil e, a menos que exista uma sutileza, posso calcular ela mesma. A verdadeira razão pela qual estou postando neste site é porque preciso saber muito mais sobre as propriedades dessas listas de palavras para o meu aplicativo, por isso espero que alguém possa responder à pergunta a seguir:

Isso foi estudado em geral? Quais são alguns artigos que consideram, não apenas se uma palavra parcial é inevitável, mas "quanto tempo leva" antes de se tornar inevitável?

Obrigado.

Aqui é um caso especial: o número de palavras binárias de comprimento de tal modo que não há dois uns aparecem consecutivamente é F ( k + 3 ) , em que M ( N ) é o n t h número de Fibonacci (começando com F ( 1 ) = 1 , F ( 2 ) = 1 ). A prova é através da representação Zeckendorf .$k$$F(k+3)$$F(n)$$n^{th}$$F(1)=1, F(2)=1$

EDIT: Podemos estender esse caso especial inicial para o caso especial um pouco maior de . Considere cadeias de comprimento k sobre um alfabeto de tamanho l + 1 , para que a letra a não apareça duas vezes consecutivas. Seja f ( k ) o número de tais strings (que chamaremos de "válidos"). Afirmamos 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)$$ O intuição é que podemos construir uma cadeia válida de comprimento k , alternativamente: a) adjacente qualquer das l letras que não são um a uma cadeia válida de comprimento k - 1 , ou b) ao lado da letra a e, em seguida, qualquer outra letra, exceto a, a uma sequência válida de comprimento k - 2 . $$f(0) = 1, f(1) = l+1$$ $k$$l$$a$$k-1$$a$$a$$k-2$

Você pode verificar se o seguinte é um formulário fechado para a recorrência acima: onde entendemos quando .

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

EDIÇÃO # 2: Vamos eliminar mais um caso - a . Chamaremos as strings sobre um alfabeto de elemento que não contém a subcadeia , "valid" e deixaremos denotar o conjunto de strings válidas de comprimento . Além disso, vamos definir ser o subconjunto de consistindo de cordas começando com e a ser aqueles que não comece por . Finalmente, deixe,,.$\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|$

Observa-se que e . Em seguida, inferimos as seguintes recorrências: O primeiro vem do fato de que adicionar ao início de qualquer elemento de produz um elemento de . O segundo vem da observação de que podemos construir um elemento de adicionando qualquer caractere, mas à frente de qualquer elemento de ou adicionando qualquer caractere, mas ou à frente de qualquer elemento em .$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$

Em seguida, reorganizamos as equações de recorrência para obter:

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

Podemos obter uma solução de forma fechada bastante opaca para essa recorrência, mexendo um pouco com a geração de coisas funcionais ou, se tivermos preguiça, indo direto para o Wolfram Alpha . No entanto, com um pouco de pesquisa e pesquisa no OEIS , descobrimos que realmente temos: onde é o polinômio Chebyshev do segundo tipo (!) .

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

Uma abordagem completamente diferente para a primeira pergunta reutiliza as respostas da pergunta recente sobre a geração de palavras em uma linguagem regular : basta aplicar esses algoritmos para o comprimento na linguagem regular , onde é o alfabeto.$k$$\Sigma^\ast a\Sigma^j b\Sigma^\ast$$\Sigma$

Atualizado: esta resposta está incorreta :

assumindo que é fixo, podemos contar o número de maneiras que um padrão pode ser correspondido: o primeiro que símbolo pode ser correspondido em alguma posição , e temos possibilidades antes desse ponto, entre e , e para o restante da corda, assim, um total de casos. Conforme observado por Tsuyoshi Ito nos comentários, essa contagem não é o número de palavras diferentes correspondentes$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$uma vez que uma única palavra poderia corresponder ao mesmo padrão de maneiras diferentes. Por exemplo, é correspondido três vezes em , duas vezes em e duas vezes em . Podemos tentar contar o número de maneiras de combinar padrões várias vezes e exibir uma expressão de "inclusão-exclusão", mas a maneira como o padrão pode se sobrepor torna isso muito longo.$aa$$aaaa$$ab$$abab$$a\lozenge b$$aabb$

---

Para a primeira pergunta, entendendo que não é fixo, ou seja, queremos evitar a incorporação da palavra :$j$$ab$

• quer primeiro símbolo nunca aparece, o que representa palavras possíveis,$a$$(l-1)^k$
• ou aparece em primeiro lugar em alguma posição , então não pode utilizar no restante da palavra: existem escolhas para o factor de até , e opções para o restante, fornecendo um total de palavras possíveis. Se é irrelevante.$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$

Para a segunda pergunta, não tenho muito o que sugerir; existe uma relação com a incorporação de palavras, mas os resultados que conheço sobre más sequências para o lema de Higman não se aplicam imediatamente.