Dado $n$ (longitud de la cadena) y $k$ (número de caracteres para formar la cadena). Encontrar el número de la cadena con $0$ a $k$ subcadenas repetitivas

Question

Pregunta: Dado $n$ (longitud de la cadena) y $k$ (número de caracteres que se utilizarán para formar la cadena). Encontrar el número de la cadena con $0$ a $k$ subcadenas repetitivas.

Por ejemplo: $k=2$ y $n=3$ . $S(1)$ -número de cadenas posibles que tienen subcadena sin caracteres repetidos (por ejemplo $101,010$ ). $S(2)$ -número de cadenas posibles que tienen una subcadena con dos caracteres repetidos (por ejemplo $001,100,110,011$ ). $S(3)$ número de cadenas posibles que tienen una subcadena con tres caracteres repetidos (por ejemplo $000,111$ ).

No soy capaz de abordar este problema. Por favor, ayúdenme a resolverlo.

Answer 1

Para el caso $k=2$ consideramos $S_q$ el número de cadenas con al menos como máximo $q$ caracteres que se repiten. Introducimos

$$F(z) = z + z^2 + \cdots + z^q = z(1+\cdots+z^{q-1}) = z \frac{1-z^q}{1-z}$$

y obtener la función generadora ( $z$ para un dígito y $w$ para un dígito cero)

$$G(z, w) = (1 + F(w)) \left(\sum_{q\ge 0} F(z)^q F(w)^q\right) (1 + F(z)) = (1+F(w))\frac{1}{1-F(z)F(w)} (1+F(z)).$$

Como sólo nos interesa el recuento podemos poner $z=w$ para obtener

$$H(z) = \frac{(1+F(z))^2}{1-F(z)^2} = \frac{(1-z^{q+1})^2}{(1-z)^2-z^2(1-z^q)^2} \\ = \frac{1-2z^{q+1}+z^{2q+2}}{1-2z+2z^{q+2}-z^{2q+2}}.$$

Para una forma cerrada que no requiera los recursos de diferenciación extraemos

$$T_p = [z^p] \frac{1}{1-2z+2z^{q+2}-z^{2q+2}} = [z^p] \sum_{r_1\ge 0} z^{r_1} (2 - 2z^{q+1} + z^{2q+1})^{r_1} \\ = \sum_{r_1=0}^p [z^{p-r_1}] (2 - 2z^{q+1} + z^{2q+1})^{r_1} \\ = \sum_{r_1=0}^p [z^{p-r_1}] \sum_{r_2=0}^{r_1} {r_1\choose r_2} 2^{r_1-r_2} z^{(q+1)r_2} (z^{q}-2)^{r_2} \\ = \sum_{r_1=0}^p \sum_{r_2=0}^{r_1} {r_1\choose r_2} 2^{r_1-r_2} [z^{p-r_1-(q+1)r_2}] (z^{q}-2)^{r_2} \\ = \sum_{r_2=0}^p \sum_{r_1=r_2}^p {r_1\choose r_2} 2^{r_1-r_2} [z^{p-r_1-(q+1)r_2}] (z^{q}-2)^{r_2} .$$

Aquí debemos tener $p-r_1-(q+1)r_2 = q r_3$ donde $0\le r_3 \le \lfloor p/q \rfloor$ y por lo tanto $r_1 = p - (q+1) r_2 - q r_3 \ge 0$ para que $r_2 \le (p - q r_3) / (q+1)$ que da como resultado

$$\sum_{r_3=0}^{\lfloor p/q \rfloor} \sum_{r_2=0}^{\lfloor (p - q r_3) / (q+1) \rfloor} {p - (q+1) r_2 - q r_3 \choose r_2} 2^{p - (q+2) r_2 - q r_3} [z^{q r_3 }] (z^{q}-2)^{r_2} \\ = \sum_{r_3=0}^{\lfloor p/q \rfloor} \sum_{r_2=0}^{\lfloor (p - q r_3) / (q+1) \rfloor} {p - (q+1) r_2 - q r_3 \choose r_2} {r_2\choose r_3} (-1)^{r_2-r_3} 2^{p - (q+1) (r_2 + r_3)}.$$

Obtenemos entonces la forma cerrada

$$T_p - 2 T_{p-q-1} + T_{p-2q-2}$$

con índices negativos que representan sumas vacías y contribuyen con cero. Por ejemplo, obtenemos para cadenas de longitud $40$ clasificado en función de según el valor máximo $q$ de subcadenas repetidas la secuencia para $q=30..40$

$$1099511622144, 1099511625216, 1099511626624, 1099511627264, \\ 1099511627552, 1099511627680, 1099511627736, 1099511627760, \\ 1099511627770, 1099511627774, 1099511627776.$$

donde $2^{40} = 1099511627776.$ Este ejemplo se incluye aquí porque documenta los límites de la extracción de coeficientes utilizando el sistema de Maple coeftayl y es obviamente imposible de atacar por medio de la enumeración total enumeración.

Una importante comprobación de cordura aquí es que debemos tener $[z^p] H(z) = 2^p$ cuando $q\ge p$ (este es el caso en el que el límite de la repetición subcadenas es al menos la longitud de las cadenas que se consultadas). En efecto, para estas $p$

$$[z^p] \frac{1-2z^{q+1}+z^{2q+2}}{1-2z+2z^{q+2}-z^{2q+2}} = [z^p] \frac{1}{1-2z+2z^{q+2}-z^{2q+2}} \\ = \sum_{r_1=0}^p [z^{p-r_1}] \sum_{r_2=0}^{r_1} {r_1\choose r_2} 2^{r_1-r_2} z^{(q+1)r_2} (z^{q}-2)^{r_2} = \sum_{r_1=0}^p [z^{p-r_1}] 2^{r_1} = 2^p.$$

Este fue el código de Maple que se utilizó para trabajar con estos funciones generadoras y verificar los datos por enumeración en la medida de lo posible.

RL :=
proc(n, q)
option remember;
local ind, d, pos, cur, run, runs, res, allq;
    res := 0;

    for ind from 2^n to 2\*2^n-1 do
        d := convert(ind, base, 2);

        cur := -1; pos := 1;
        run := \[\]; runs := \[\];

        while pos <= n do
            if d\[pos\] <> cur then
                if nops(run) > 0 then
                    runs :=
                    \[op(runs), \[run\[1\], nops(run)\]\];
                fi;

                cur := d\[pos\];
                run := \[cur\];
            else
                run := \[op(run), cur\];
            fi;

            pos := pos + 1;
        od;

        runs := \[op(runs), \[run\[1\], nops(run)\]\];

        allq := select(r -> r\[2\] <= q, runs);

        if nops(allq) = nops(runs) then
            res := res + 1;
        fi;
    od;

    res;
end;

X := (n, q) ->
coeftayl((1-2\*z^(q+1)+z^(2\*q+2))/(1-2\*z+2\*z^(q+2)-z^(2\*q+2)),
         z=0, n);

T := (p, q) ->
add(add(binomial(p-(q+1)\*r2-q\*r3, r2)\*binomial(r2, r3)
        \*(-1)^(r2-r3)\*2^(p-(q+1)\*(r2+r3)),
        r2 = 0 .. floor((p-q\*r3)/(q+1))), r3=0..floor(p/q));

S := (n, q) -> T(n, q)-2\*T(n-q-1, q)+T(n-2\*q-2, q);

Adenda. Un medio alternativo de cálculo $T_p$ es utilizar una recurrencia. Obtenemos

$$[z^p] H(z) (1-2z+2z^{q+2}-z^{2q+2}) = [[p=0]] - 2 [[p=q+1]] + [[p=2q+2]]$$

o

$$T_p = 2 T_{p-1} - 2 T_{p-q-2} + T_{p-2q-2} + [[p=0]] - 2 [[p=q+1]] + [[p=2q+2]]$$

donde los índices negativos producen una contribución nula.

Observación. Utilice $S_q-S_{q-1}$ para el caso en que al menos una instancia de una cadena de $q$ se requieren caracteres de repetición.