Contando cadenas que contienen apariencias específicas de palabras

Question

Hay una buena fórmula (o de generación de función) para que el número de cadenas binarias de longitud $n$ que contienen exactamente $k$ apariciones de una palabra determinada $w$? Por ejemplo, entre las cadenas binarias de longitud 7, exactamente quince contienen exactamente dos apariciones de ${101}$, a saber: $$ \begin{array}{llll} 0\color{red}{101}\color{blue}{101}&1\color{red}{101}\color{blue}{101}&\\ \color{red}{101}\color{blue}{101}0&\color{red}{101}\color{blue}{101}1&\\ \color{red}{101}1\color{blue}{101}&&\\ 00\color{red}{101}\color{blue}{01}&01\color{red}{101}\color{blue}{01}&11\color{red}{101}\color{blue}{01}\\ \color{red}{101}\color{blue}{01}00&\color{red}{101}\color{blue}{01}10&\color{red}{101}\color{blue}{01}11\\ 0\color{red}{101}\color{blue}{01}0&0\color{red}{101}\color{blue}{01}1&1\color{red}{101}\color{blue}{01}0&1\color{red}{101}\color{blue}{01}1\\ \end{array} $$

En Wilf del Generatingfunctionology (sección 4.12) hay un caso muy especial de este, donde $k=0$ e $w=\mathtt{111...1}$. Incluso este ejemplo es un poco involucrados, pero tal vez el caso general no es mucho más difícil.

Answer 1

He aquí una breve explicación de la Goulden-Jackson clúster método , tal como se aplica a este problema. Definir un marcado palabra a ser una palabra con cierta subpalabras y su ubicación en la palabra marcada. Voy a ilustrar esto con parenthesizing ciertos subpalabras, con colores para indicar cómo los paréntesis son coincidentes. Por ejemplo,

$$\color{red}(\text{S}\color{green}(TU\color{green})\color{blue}(F\color{red})F\color{blue}).$$

Dado un conjunto de "malas" palabras $B$, con ninguna mala palabra contenida en otra, definir un clúster de ser una marcada palabra para que cada uno marcado subword es en $B$, y la marcada subpalabras se superponen de tal manera que la palabra no es la concatenación de dos vacío palabras marcadas. Por ejemplo, si $B = \{AAA, AB\}$ luego

$$\color{red}(AA\color{blue}(A\color{red})B\color{blue})$$ is a cluster but $$\color{red}(AAA\color{red})\color{blue}(AB\color{blue})$$ no es ya que las palabras marcadas no se superponen.

Ahora vamos a $\mathcal{C}$ el conjunto de clusters, y deje $\mathcal{C}(x,y)$ ser la generación de la función $\sum_{C \in \mathcal{C}} (y-1)^{m(C)} x^{n(C)}$ donde $n(W)$ es la longitud de la palabra $C$ e $m(C)$ es el número de marcado subpalabras. Supongamos que estas palabras están hechas de letras en un alfabeto $S$ del tamaño de la $k$, y para una palabra $W$ a $S$ definir el peso de $W$ a $w(W) = x^n y^b$ donde $n$ es la longitud de $W$ e $b$ es el número de ocurrencias de las malas palabras. A continuación, el hecho es hermosa

$$\sum_W w(W) = \frac{1}{1 - kx - \mathcal{C}(x,y)}$$

donde la suma se toma sobre todas las palabras $W$ sobre el alfabeto $S$.

El artículo que he enlazado se describe un algoritmo para encontrar una expresión para $\mathcal{C}(x,y)$ como una función racional mediante álgebra lineal, pero en este caso lo podemos encontrar con la mano. Dejando $B = \{101\}$, vemos que la única posible clusters son

$$\color{red}(101\color{red}), \color{red}(10\color{blue}(1\color{red})01\color{red}), \color{red}(10\color{blue}(1\color{red})0\color{green}(1\color{blue})01\color{green}), \ldots$$

con cada aparición de $101$ marcado. La palabra en esta lista con $m$ apariciones de $101$ tendrá la longitud de la $2m+1$, por lo que

\begin{align*} \mathcal{C}(x,y) &= \sum_{m=1}^\infty (y-1)^mx^{2m+1}\\ &= x\sum_{m=1}^\infty (x^2 (y-1) )^m\\ &= \frac{x^3(y-1)}{1 - x^2 (y-1)}\\ \end{align*}

y así el deseado de generación de función es

$$\sum_W w(W) = \frac{1}{1 - 2x - \frac{x^3(y-1)}{1 - x^2 (y-1)}}.$$

Se puede comprobar que el coeficiente de $x^7y^2$ es $15$, lo que representa el $15$ binario palabras de longitud $7$ que contienen dos copias de $101$. Tenga en cuenta que si ponemos $y=0$ obtenemos la generación de la función de las palabras que evite $101$.

Recomiendo la lectura del artículo anterior para los detalles, las pruebas no son demasiado complicados.

Answer 2

He aquí una serie de enlaces que el documento de la técnica.

• Sistemas de generación de funciones, la sección 11.1
• Buena introducción a la racional funciones de generación
• Excelente explicación del método de la matriz de transferencia
• Esto tiene la matriz de transferencia de fórmulas y una bibliografía.

Si hay preguntas específicas sobre el algoritmo o lo que mi Maple programa, a continuación, voy a responder en los comentarios. Yo soy esencialmente el uso de la matriz de transferencia sin la construcción como tal, con el fin de obtener la condicional ordinaria de la generación de funciones para la distribución de la palabra ocurrences después de $n$ pasos para cada estado de la DFA, que corresponden a los prefijos de $w$ (incluyendo $w$), donde el coeficiente de $[z^n]$ contiene la distribución exacta de las apariciones dado que el DFA estaba en ese estado después de $n$ pasos. La suma de estos para obtener el GF de todos los ocurrences después de $n$ pasos, sin importar lo que el último era el estado. Las transiciones de un estado a otro producirse si el prefijo correspondiente a la meta es el más prefijo contenida en el prefijo de la situación actual con la transición de la carta anexa, a partir de la derecha de la fuente con la transición que se anexa. E. g. si la palabra $w$ es $101$, los posibles prefijos $\epsilon, 1, 10$ e $101.$ Calcular el transtions entre los estados mediante la máxima longitud del prefijo de la regla. Recoger un $z$ para cada transición y un $uz$ para las transiciones a $101$, para tener en cuenta el hecho de que hemos visto una ocurrencia de $w$. Por ejemplo, si usted está en $101$ a $0$ transición a la $10$ y en $1$, a $1$.

Answer 3

Aquí es una observación. Aunque estoy seguro de que el anterior tratamiento avanzado merece protagonismo, me gustaría señalar que uno puede obtener buenos resultados (bivariante funciones de generación) simplemente mediante el análisis de un mínimo de autómata con los prefijos de $w$ como los estados y de computación en la transición de un prefijo a otro de modo que el máximo de prefijo es elegido en cada paso, y a partir de entonces resolver el sistema resultante de la probabilidad de generación de funciones. Muy simple, de hecho. Las funciones de generación en $z$ e $u$ donde $z$ los índices de la longitud de la cadena y $u$ el número de ocurrencias de $w.$ Estas rendimiento condicional resultados, es decir, el PGF para un cierto estado da la distribución de probabilidad de ocurrences de $w$ como un polinomio en $u$ (que es el coeficiente de $z^n$ de la PGF) dado que el autómata está en ese estado. Para obtener todas las apariciones, la suma de las fuerzas progubernamentales para todos los estados y extraer los coeficientes.

El ejemplo ha $w=101$, dando funciones de generación $$\begin{align} a & =-2\,{\frac {{z}^{2}u+2\,z-4}{8-8\,z-2\,{z}^{2}u+{z}^{3}u+2\,{z}^{2}-{z}^ {3}}},\\ a_1 & =-{\frac { \left( -4+{z}^{2}u \right) z}{8-8\,z-2\,{z}^{2}u+{z}^{3}u+ 2\,{z}^{2}-{z}^{3}}}\\ a_{10} & =2\,{\frac {{z}^{2}}{8-8\,z-2\,{z}^{2}u+{z}^{3}u+2\,{ z}^{2}-{z}^{3}}}\\ a_{101} & ={\frac {{z}^{3}u}{8-8\,z-2\,{z}^{2}u+{z}^{3}u+2\,{z}^{2}-{z}^{3}}} \end{align}$$ Añadir estos y simplificar para obtener $$ g(z, u) = -2\,{\frac {{z}^{2}u-4-{z}^{2}}{8-8\,z-2\,{z}^{2}u+{z}^{3}u+2\,{z}^{2}-{z}^{3}}}.$$ Finalmente extraer el coeficiente de $[u^2]$, al pasar $$ [u^2] g(z, u) = 8\,{\frac {{z}^{5} \left( -2+z \right) }{ \left( -8+8\,z-2\,{z}^{2}+{z}^{3}\right) ^{3}}}.$$ Ahora los coeficientes (veces $2^n$ porque tenemos un PGF) de este último término (a partir de $n=5$) $$1, 5, 15, 38, 91, 210, 468, 1014, 2151, 4487, 9229, 18756, 37728, 75219, 148803, 292354,$$ y de hecho hay quince de estos para $n=7$.

Vamos a tratar otro ejemplo, $w=1111.$ se obtiene el siguiente conjunto de las fuerzas progubernamentales: $$\begin{align} a & =-8\,{\frac {-2+uz}{16-8\,uz-8\,z+4\,{z}^{2}u-4\,{z}^{2}+2\,{z}^{3}u-2\,{ z}^{3}+{z}^{4}u-{z}^{4}}}\\ a_{1} & =-4\,{\frac {z \left( -2+uz \right) }{16-8\,uz-8 \,z+4\,{z}^{2}u-4\,{z}^{2}+2\,{z}^{3}u-2\,{z}^{3}+{z}^{4}u-{z}^{4}}}\\ a_{11} & =-2\, {\frac {{z}^{2} \left( -2+uz \right) }{16-8\,uz-8\,z+4\,{z}^{2}u-4\,{z}^{2}+2\,{z}^ {3}u-2\,{z}^{3}+{z}^{4}u-{z}^{4}}}\\ a_{111} & =-{\frac {{z}^{3} \left( -2+uz \right) }{16-8\,uz-8\,z+4\,{z}^{2}u-4\,{z}^{2}+2\,{z}^{3}u-2\,{z}^{3}+{z}^{4}u-{z} ^{4}}}\\ a_{1111} & ={\frac {{z}^{4}u}{16-8\,uz-8\,z+4\,{z}^{2}u-4\,{z}^{2}+2\,{z}^{3 }u-2\,{z}^{3}+{z}^{4}u-{z}^{4}}} \end{align}$$ Agregar y simplificar para obtener $$ g(z,u) = -2\,{\frac {-8+4\,uz-4\,z+2\,{z}^{2}u-2\,{z}^{2}+{z}^{3}u-{z}^{3}}{16-8\,uz-8\,z+4\,{z}^{2}u-4\,{z}^{2}+2\,{z}^{3}u-2\,{z}^{3}+{z}^{4}u-{z}^{4}}}. $$ Ahora supongamos que queremos que el contar con cuatro ocurrences de $w$ a que la PGF $$ [u^4] g(z,u) = 16\,{\frac {{z}^{7} \left( -8+4\,z+2\,{z}^{2}+{z}^{3} \right) ^{3}}{ \left( -16+8\, z+4\,{z}^{2}+2\,{z}^{3}+{z}^{4} \right) ^{5}}}.$$ Claramente necesitamos al menos siete bits, y de hecho la secuencia (veces $2^n$ porque tenemos un PGF) de los coeficientes de este último término es (a partir de $n=7$) $$ 1, 2, 5, 12, 31, 71, 163, 369, 829, 1835, 4032, 8795, 19064, 41081.$$

Estoy publicando el Arce código que he utilizado para calcular estos y el lector es invitado a probarlo al invocar la función "eqsys" con una lista de los bits de la palabra $w$).

Aquí es un reto para el lector: verificar de forma independiente que el acumulado de PGF para $w=10101$ está dado por $$ g(z, u) = -2\,{\frac {4\,{z}^{2}u-16-4\,{z}^{2}+{z}^{4}u{z}^{4}}{8\,{z}^{3}u-32\,z-8\,{z}^{2 }u+32-8\,{z}^{3}-2\,{z}^{4}u+8\,{z}^{2}+2\,{z}^{4}-{z}^{5}+{z}^{5}u}}.$$

Este es el Arce código:

prfx :=
proc(w ww)
 local pos, s1, s2;

 para pos de nops(ww) a 1 por -1 ¿
 s1 := cat(seq(w[k], k=1..pos));
 s2 := cat(seq(ww[k], k=nops(ww)-pos+1..nops(ww)));

 si s1=s2, a continuación, volver s1; fi;
od;

 return "";
end;

eqsys :=
proc(w)
 local mx, prf, ww, ww_name, sysl, eq, eqs_tbl;

 sysl := [];

 para mx de 0 a nops(w)-1 ¿
 ww := [seq(w[k], k=1..mx), 0];
 ww_name := cat(`a`, seq(ww[k], k=1..nops(ww)-1));
 prf := cat(`a`, prfx(w ww));

 sysl := [op(sysl), [prf, ww_name, 0]];

 ww := [seq(w[k], k=1..mx), 1];
 ww_name := cat(`a`, seq(ww[k], k=1..nops(ww)-1));
 prf := cat(`a`, prfx(w ww));

 sysl := [op(sysl), [prf, ww_name, 1]];
od;

 ww := [seq(w[k], k=2..nops(w)), 0];
 ww_name := cat(`a`, seq(w[k], k=1..nops(w)));
 prf := cat(`a`, prfx(w ww));

 sysl := [op(sysl), [prf, ww_name, 0]];

 ww := [seq(w[k], k=2..nops(w)), 1];
 ww_name := cat(`a`, seq(w[k], k=1..nops(w)));
 prf := cat(`a`, prfx(w ww));

 sysl := [op(sysl), [prf, ww_name, 1]];

de impresión(sysl);

 eqs_tbl := tabla();
 para v en indets(sysl) ¿
 si v = `a` entonces
 eqs_tbl[v] := 1;
otra cosa
 eqs_tbl[v] := 0;
fi;
od;

 ww_name = cat(`a`, seq(w[k], k=1..nops(w)));

 para eq en sysl ¿
 si eq[1] = ww_name, a continuación,
 eqs_tbl[eq[1]] :=
 eqs_tbl[eq[1]] + 1/2*u*z*eq[2];
otra cosa
 eqs_tbl[eq[1]] :=
 eqs_tbl[eq[1]] + 1/2*z*eq[2];
fi;
od;

 sysl := [];
 para eq [índices(eqs_tbl, 'nolist')] ¿
 sysl := [op(sysl), eq = eqs_tbl[eq]];
od;

de impresión(sysl);

 resolver(sysl, indets(sysl) menos {u,z});
end;

Answer 4

Para el problema de cero ocurrences de $q$ me sale el siguiente las fuerzas progubernamentales:$$\begin{align} g_1 = & -2\, \left( -2+z \right) ^{-1} \\ g_2 = & -2\,{\frac {-2-z}{4-2\,z-{z}^{2}}} \\ g_3 = & -2\,{\frac {-4-2\,z-{z}^{2}}{8-4\,z-2\,{z}^{2}-{z}^{3}}} \\ g_4 = & -2\,{\frac {-8-4\,z-2\,{z}^{2}-{z}^{3}}{16-8\,z-4\,{z}^{2}-2\,{z}^{3}-{z}^{4}}} \\ g_5 = & -2\,{\frac {-16-8\,z-4\,{z}^{2}-2\,{z}^{3}-{z}^{4}}{32-16\,z-8\,{z}^{2}-4\,{z}^{3}- 2\,{z}^{4}-{z}^{5}}}\end{align}.$$

El Arce de código para este va como sigue:

queridos :=
proc(n)
 locales sol, los estados, s;

 sol := eqsys([seq(1, k=1..n)]);

 estados := convert(indets(sol) menos {u, z}, lista);

 s := `+`(seq(estados[k], k=1..nops(estados unidos)));
 factor(subs(sol, s));
end;

El valor de estas para $q=1$ es ${2}^{-n}$, lo cual es obviamente correcto. Multiplicar por $2^n$ para compensar la PGF y obtenga $1$, y hay, efectivamente, una cadena que no contiene la palabra $1$, que es una cadena de ceros.

Answer 5

Después de trabajar a través de algunos de los materiales de Jair se hizo evidente para mí que nada se gana con esos probabilidad de generación de funciones, sólo se satura la salida con la predicción de los coeficientes, por lo que uno definitivamente debe uso ordinario de la generación de funciones en su lugar.

El siguiente DIFF muestra cómo modificar el Arce código para cambiar de esas fuerzas a OGFs.

63c63
< eqs_tbl[eq[1]] + 1/2*u*z*eq[2];
---
> eqs_tbl[eq[1]] + u*z*eq[2];
66c66
< eqs_tbl[eq[1]] + 1/2*z*eq[2];
---
> eqs_tbl[eq[1]] + z*eq[2];

Con la nueva configuración, el reto de la función de $10101$ se convierte en $$ g(z,u) = -{\frac {{z}^{2}u-1-{z}^{2}+{z}^{4}u-{z}^{4}}{1-{z}^{2}u-2\,z+2\,{z}^{3}u-2\,{z}^{3}+{z}^{2}-{z}^{4}u+{z}^{4}-{z}^{5}+{z}^{5}u}}.$$

El reto para $101010$ se convierte en $$ g(z,u) = {\frac {{z}^{2}u-1-{z}^{2}+{z}^{4}u-{z}^{4}}{2\,{z}^{5}-1+{z}^{2}u+2\,z-2\,{z}^{3}u+2\,{z}^{3}-2\,{z}^{5}u-{z}^{6}-{z}^{2}+{z}^{4}u-{z}^{4}+{z}^{6}u}}.$$