Contando Las Cadenas

Question

---

Hay 7 ⁵ = 16,807 cadenas de longitud 5 formado a partir de las 7 letras un, b, c, d, e, f, & g. Por ejemplo, una cadena es ebdbg.

---

¿En cuántos de estos 16,807 cadenas son las letras b y d adyacentes (que aparecen en bd o db ) ?

---

En otras palabras, cómo muchos de estos 16,807 cadenas contienen cualquiera de bd como una subcadena o contener db como una subcadena?

---

Answer 1

Esta respuesta se basa en la Goulden-Jackson Clúster Método que es una excelente técnica para derivar una generación de función para problemas de este tipo.

Tenemos en cuenta las palabras de longitud $n\geq 0$ construido a partir de un alfabeto $$\mathcal{V}=\{a,b,c,d,e,f,g\}$$ and the set $B=\{bd,db\}$ of bad words, which are not allowed to be part of the words we are looking for. We derive a generating function $f(s)$ with the coefficient of $s^n$ being the number of searched words of length $n$.The wanted number of words of length $5$ que hacer contener una de las malas palabras es, en consecuencia, \begin{align*} \color{blue}{7^5-[s^5]f(s)} \end{align*} con $[s^n]$ denota el coeficiente de $f(s)$ de una serie.

Según el periódico (p.7) la generación de la función de $f(s)$es \begin{align*} f(s)=\frac{1}{1-ds-\text{weight}(\mathcal{C})} \end{align*} con $d=|\mathcal{V}|=7$, el tamaño de las letras del alfabeto y $\mathcal{C}$ el peso numerador de malas palabras con \begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[bd])+\text{weight}(\mathcal{C}[db]) \end{align*}

Calculamos de acuerdo con el documento \begin{align*} \text{weight}(\mathcal{C}[bd])&=-s^2-\text{weight}(\mathcal{C}[db])s\\ \text{weight}(\mathcal{C}[db])&=-s^2-\text{weight}(\mathcal{C}[bd])s\\ \end{align*} y obtener \begin{align*} \text{weight}(\mathcal{C}[bd])&=\text{weight}(\mathcal{C}[db])=\frac{-s^2}{1+s}\\ \text{weight}(\mathcal{C})&=\text{weight}(\mathcal{C}[bd])+\text{weight}(\mathcal{C}[db])\\ &=\frac{-2s^2}{1+s} \end{align*}

Ahora podemos calcular el $f(s)$

\begin{align*} \color{blue}{f(s)}&=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\\ &=\frac{1}{1-7s+\frac{2s^2}{1+s}}\\ &=\frac{1+s}{1-6s-5s^2}\\ &=1+7s+47s^2+317s^3+2\,137s^4+\color{blue}{14\,407}s^5+97\,127s^6+\cdots\tag{1} \end{align*} donde la última línea fue hecho con la ayuda de Wolfram Alpha.

Podemos concluir a partir de (1) el número de palabras que contiene al menos una subcadena de $\{bd,db\}$es \begin{align*} 7^5-[x^5]f(s)=16\,807-14\,407=\color{blue}{2\,400} \end{align*}

Sugerencia: Algunos aspectos de este enfoque se proporcionan en el Add-on de parte de esta respuesta.

Answer 2

Para un entero no negativo $n$, una cadena de longitud $n$ compuesto por las letras, $a,b,c,d,e,f,g$ contiene $bd$ o $db$ como una subcadena se dice $n$-apto. Deje $x_n$ denotar el número de $n$-apropiado cadenas. Claramente, $x_0=0$, $x_1=0$, $x_2=2$, e $x_3=26$.

Para $n>1$, se puede observar que $$x_n=5x_{n-1}+10x_{n-2}+10x_{n-3}+\ldots+10x_1+2\cdot 7^{n-2}+2\cdot 7^{n-3}+\ldots +2\cdot 7^0\,.\tag{*}$$ Para mostrar esto, mira el final de una $n$-apropiado cadena de $t_1t_2\ldots t_n$. Si $t_n\notin\{b,d\}$, entonces la cadena de $t_1t_2\ldots t_{n-1}$ debe $(n-1)$-apto. Hay $5$ opciones para $t_n$, y por lo $5x_{n-1}$ posible $n$-apropiado cadenas con $t_n\notin\{b,d\}$.

Ahora, supongamos que el $t_n\in\{b,d\}$. Deje $k$ ser el menor entero positivo tal que $$t_k=t_{k+1}=\ldots=t_{n}\,.$$ Claramente, $k>1$. Si $t_{k-1}\in\{b,d\}\setminus\{t_n\}$, a continuación, $t_1t_2\ldots t_{k-2}$ puede ser arbitraria, por lo que tenemos $2\cdot 7^{k-2}$ posibilidades, recordando que hay dos opciones para $t_n$.

Si $t_{k-1}\notin\{b,d\}$, a continuación, $t_1t_2\ldots t_{k-2}$ es $(k-2)$-apropiado cadena. Hay $5$ opciones de $t_{k-1}$ e $2$ opciones para $t_n$. Por lo tanto, tenemos en total $10x_{k-2}$ posibles variedades.

A partir de (*), tenemos $$x_{n-1}=5x_{n-2}+10x_{n-3}+\ldots+10x_1+2\cdot 7^{n-3}+2\cdot 7^{n-4}+\ldots+2\cdot7^0$$ para $n>2$. Restando el resultado anterior por (*), obtenemos $$x_n-x_{n-1}=5x_{n-1}+5x_{n-2}+2\cdot 7^{n-2}\,,$$ así $$x_n-6x_{n-1}-5x_{n-2}=2\cdot7^{n-2}\,.$$ La solución de la recurrencia de la relación da $$x_n=7^n-\left(\frac{7-2\sqrt{14}}{14}\right)(3-\sqrt{14})^n-\left(\frac{7+2\sqrt{14}}{14}\right)(3+\sqrt{14})^n\,.$$

Sin embargo, para obtener $x_5$, no necesita la fórmula general. Sólo mantener el uso de la recurrencia de la relación, usted recibirá su respuesta deseada. En otras palabras, calcular $x_4$ conseguir $$x_4=6x_3+5x_2+2\cdot 49=264\,.$$ A continuación, $$x_5=6x_4+5x_3+2\cdot 343=2400\,.$$