Número de palabras que utilizan $\{a,b,c,d,e\}$ sin "de" y "abd"

Question

Considerar las palabras sobre el alfabeto $\{a,b,c,d,e\}$ de longitud $7$ . ¿Cuál es el número de palabras que no contienen "de" y "abd"?

Una solución razonable (creo) es establecer $t_n$ para ser el número de $n$ -a palabras largas sin "de" y "abd", y luego encontrar una relación de recurrencia. A partir de esta recurrencia podemos calcular $t_7$ .

¿Cuál es esa relación de recurrencia? ¿Hay otra solución sin recurrencia? Gracias.

Answer 1

La siguiente respuesta se basa en la Método de agrupación de Goulden-Jackson . Consideramos el conjunto de palabras de longitud $n\geq 0$ construido a partir de un alfabeto $$\mathcal{V}=\{a,b,c,d,e\}$$ y el conjunto $B=\{abd,de\}$ de malas palabras que no pueden formar parte de las palabras que buscamos. Derivamos una función generadora $f(s)$ con el coeficiente de $s^n$ siendo el número de palabras deseadas de longitud $n$ .

Según el documento (p.7) la función generadora $f(s)$ es \begin{align*} f(s)=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\tag{1} \end{align*} con $d=|\mathcal{V}|=5$ el tamaño del alfabeto y $\mathcal{C}$ es el numerador de peso de malas palabras con \begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[abd])+\text{weight}(\mathcal{C}[de])\tag{2} \end{align*}

Calculamos según el documento \begin{align*} \text{weight}(\mathcal{C}[abd])&=-s^3\\ \text{weight}(\mathcal{C}[de])&=-s^2-s\cdot\text{weight}(\mathcal{C}[abd])\tag{3}\\ \end{align*} para que \begin{align*} \text{weight}(\mathcal{C})=-s^3+\left(-s^2-s\cdot\left(-s^3\right)\right)=-s^2-s^3+s^4 \end{align*} El término adicional en el lado derecho de (3) tiene en cuenta el solapamiento de $ab\color{blue}{d}$ con $\color{blue}{d}e$ .

Obtenemos según (1) y (3) \begin{align*} f(s)&=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\\ &=\frac{1}{1-5s+s^2+s^3-s^4}\\ &=1 + 5 s + 24 s^2 + 114 s^3 + 542 s^4 + 2577 s^5\\ &\qquad + 12\,253 s^6 + \color{blue}{58\,260} s^7 + 277\,012 s^8 + 1\,317\,124 s^9 +\cdots \end{align*} donde la última línea fue calculada con la ayuda de Wolfram Alpha.

Resultado: El coeficiente marcado en azul de $s^{7}$ muestra que hay $\color{blue}{58\,260}$ palabras de longitud $7$ sobre el alfabeto $\mathcal{V}$ que no contienen $abd$ o $de$ .

Answer 2

Nota: Esta respuesta es incorrecta; ver los comentarios más abajo para la discusión

---

Podemos justificar una recurrencia de la siguiente manera: tan pronto como haya una cadena inicial que "no sea" de o abd podemos añadir libremente cualquier cadena que no tenga de ni abd .

Podemos fallar produciendo una cadena prohibida de las siguientes maneras:

• Comienza con b,c, o e. (3 formas, 1 ranura utilizada),
• Comienza con la d, seguida de cualquier letra además de la e (4 formas, 2 ranuras utilizadas),
• Comienza con la a, seguida de cualquier letra además de la b (4 formas, 2 ranuras utilizadas),
• Comienza con ab, seguido de cualquier letra además de la d (4 formas, 3 ranuras utilizadas).

Esto lleva a la siguiente recurrencia: $$ t_n = 3t_{n-1} + 8t_{n-2} + 4t_{n-3}; n \geq 3. $$ Las condiciones iniciales son $$ t_0 = 1, \quad t_1 = 5, \quad t_2 = 24. $$

Answer 3

Aquí utilizamos _PIE_ el principio de inclusión-exclusión para contar el número de $7$ -palabras de letras del alfabeto $\{a,b,c,d,e\}$ que no contienen el mal palabras $\{abd,de\}$ .

Para realizar el trabajo es útil tener algún tipo de contabilidad. Consideramos \begin{align*} .\ .\ .\ .\ .\ .\ . &-\left(abd\ .\ .\ .\ .|de\ .\ .\ .\ .\ .\right)\tag{1}\\ &+\left(abd\ abd\ .|abd\ de\ .\ .|abde\ .\ .\ .|de\ de\ .\ .\ .\right)\tag{2}\\ &-\left(abde\ abd|abde\ de\ .|abd\, de\, de|de\ de\ de\ .\right)\tag{3} \end{align*}

Comentario:

• En (1) contamos todos los $7$ -palabras de letras indicadas por siete puntos que dan $5^7$ . Luego restamos todas las palabras que contienen al menos una mala palabra.

  Desde $abd$ consume tres caracteres y quedan cuatro para la asignación libre, contamos $\binom{5}{1}5^4$ palabras de este tipo y de manera similar $\binom{6}{1}5^5$ en el otro caso con la mala palabra $de$ .

• En (2) añadimos palabras que contienen dos palabras malas como compensación por las que hemos restado dos veces en (1), observando que también tenemos que considerar se solapa con $abd$ con $de$ dando $\color{blue}{abde}$ .

• En (3) finalmente restamos las palabras que contienen tres palabras malas que se añadieron dos veces en (2). Por ejemplo $abde\ abd$ se produce en $\color{blue}{abd\ abd\ .}$ así como en $\color{blue}{abde\ .\ .\ .}$

• No quedan más casos por considerar, ya que las palabras que contienen cuatro o más palabras malas tienen longitud $>7$ .

Obtenemos según (1) a (3): \begin{align*} 5^7&-\left(\binom{5}{1}5^4+\binom{6}{1}5^5\right)\\ &\quad+\left(\binom{3}{2}5^1+2\binom{4}{2}5^2+\binom{4}{1}5^3+\binom{5}{2}5^3\right)\\ &\quad-\left(2\binom{2}{2}5^0+2\binom{3}{2}5^1+\binom{3}{2}5^0+\binom{4}{3}5^1\right)\\ &=78\,125-(3\,125+18\,750)+(15+300+500+1\,250)-(2+30+3+20)\\ &=78\,125-21\,875+2\,065-55\\ &\,\,\color{blue}{=58\,260} \end{align*}

Nota: El Grupo Goulden-Jackson utilizado en otro post se basa en el enfoque PIE y nos oculta convenientemente toda esta contabilidad.