Cuerdas ternarias con 3 o más 2's consecutivos

Question

Estoy tratando de averiguar cómo encontrar el número de cuerdas ternarias de longitud $n$ que tienen 3 o más 2 consecutivos. Hasta ahora he podido establecer que hay $n(2^{n-1})$ con un solo 2. Y creo (pero no estoy seguro) que esto puede ser extrapolado al número de cuerdas con un solo grupo de 2 de longitud $x$ por: $$ \bigl (n-(x-1) \bigr )(2^{n-x})$$ Lo que me está atrapando es la "o más parte", cualquier ayuda sería muy apreciada.

Answer 1

Denota por $c_n$ el número de palabras ternarias que no contienen $222$ . Luego $c_1=3$ , $c_2=9$ , $c_3=26$ y tenemos la recursividad $$c_n=2c_{n-1}+2c_{n-2}+2c_{n-3} \qquad (n \geq4 )\ . \tag {1}$$ Prueba. Una palabra admisible $w$ puede empezar con $Z$ , $2Z$ o $22Z$ con $Z \in\ {0,1\}$ seguido de una palabra admisible $w'$ .

Desafortunadamente la ecuación característica de $(1)$ no tiene raíces racionales, por lo que queda por enumerar los primeros valores: $$(c_n)_{n \geq1 }=(3, 9, 26, 76, 222, 648, 1892, 5524, 16128, 47088, 137480, 401392, \ldots )\ .$$ Los valores $a_n=3^n-c_n$ requerido por la OP entonces son $$(a_n)_{n \geq1 }=(0, 0, 1, 5, 21, 81, 295, 1037, 3555, 11961, 39667, 130049, \ldots )\ .$$

Answer 2

Consideramos que el alfabeto $V=\{0,1,2\}$ y estamos buscando el número $c_n$ de cuerdas de longitud $n$ que tienen carreras de $2$ menos de tres. El número buscado es $$a_n=3^n-c_n$$

Derivamos una función generadora $C(z)= \sum_ {n=0}^ \infty c_nz^n$ de la cual el número $a_n$ puede obtenerse fácilmente ya que \begin {alineado*} a_n=[z^n] \left ( \frac {1}{1-3z}-C(z) \right ) \tag {1} \end {alineado*} con $[z^n]$ que denota el coeficiente de $z^n$ de una serie.

Las cadenas sin caracteres iguales consecutivos se llaman palabras de Smirnov o Carlitz. Véase el ejemplo III.24 Palabras de Smirnov de Combinatoria analítica por Philippe Flajolet y Robert Sedgewick para más información.

Una función generadora del número de palabras de Smirnov sobre un alfabeto ternario $V$ está dada por \begin {alineado*} \left (1- \frac {3z}{1+z} \right )^{-1} \tag {2} \end {alineado*}

Reemplazar las ocurrencias de $0$ en una palabra de Smirnov por uno o más ceros genera palabras que tienen corridas de $0$ con la longitud $ \geq 1$ . \begin {alineado*} z \longrightarrow z+z^2+z^3+ \cdots = \frac {z}{1-z} \end {alineado*}

Lo mismo se puede hacer con el dígito $1$ .

Reemplazar las ocurrencias de $2$ en una palabra de Smirnov por uno o dos $2$ genera palabras con tiradas de $2$ de longitud inferior a tres. \begin {alineado*} z \longrightarrow z+z^2=z(1+z) \end {alineado*}

La función generadora resultante es según (2) \begin {alineado*} \color {azul}{C(z)}= \left (1- 2 \cdot\frac { \frac {z}{1-z}}{1+ \frac {z}{1-z}- \frac {z(1+z)}{1+z(1+z)} \right )^{-1} & \color {azul}{= \frac {1+z+z^3}{1-2z-2z^2-2z^3}} \tag {3} \end {alineado*}

Obtenemos para $n \geq 3$ el número de palabras de longitud deseada $n$ de acuerdo con (1) y (3) como \begin {alineado*} \color {azul}{a_n}&=3^n-c_n \\ &=[z^n] \left ( \frac {1}{1-3z}- \frac {1+z+z^3}{1-2z-2z^2-2z^3} \right ) \\ &=[z^n] \left ( \color {azul}{1}z^3+ \color {azul}{5}z^4+ \color {azul}{21}z^5+ \color {azul}{81}z^6+ \color {azul}{295}z^7+ \color {azul}{1\,037}z^8+ \color {\i1}{\b1}{\b1}Azul{\b}{\b}} \cdots\right ) \end {alineado*}

por lo que la última línea fue obtenida con algo de ayuda de Wolfram Alpha.

Answer 3

Intentar contarlos directamente no te llevará a ninguna parte, debido a la doble contabilidad. El mejor enfoque es llegar a una relación de recurrencia, para el número de cuerdas de longitud aceptable $n$ en cuanto al número de cuerdas más cortas aceptables. Llama a una cadena ternaria con al menos tres cadenas consecutivas $2$ es "bueno" y otras cuerdas ternarias "malas".

Deje que $a_n$ ser el número de buenas cuerdas de longitud $n$ . Para hacer una buena cuerda de longitud $n+1$ podemos añadir cualquier dígito a una buena cadena de longitud $n$ o podemos añadir un $2$ hasta el final de una mala cadena de longitud $n$ que termina en dos $2$ 's. Así que tenemos $$a_{n+1}=3a_n+b_n$$ Entonces, ¿cuántas cuerdas malas de longitud $n$ terminan en dos $2$ 's? Los conseguimos sumando dos $2$ es a una mala cadena de longitud $n-2$ que no termina en un $2$ . $$b_{n}=c_{n-2}$$ Entonces, ¿cuántas cuerdas malas de longitud $n-2$ no terminan en $2$ ? Sólo añadimos $0$ o $1$ a una mala cadena de longitud $n-3$ y hay $3^{n-3}-a_{n-3}$ malas cuerdas de longitud $n-3$ . $$ a_{n+1}=3a_{n}+2(3^{n-3}-a_{n-3}) \implies a_{n+1}-3{a_n}+2a_{n-3}=2 \cdot 3^{n-3} \tag 1$$

(Creo que las definiciones de $b_n, c_n$ son obvios por el contexto).

Tenemos los datos iniciales $$a_0=a_1=a_2=0,a_3=1$$

Un pequeño experimento con la pitón confirma esta fórmula. La recurrencia no es fácil de resolver. Además de la raíz obvia en $1$ , la ecuación característica tiene una raíz positiva, que Wolframio Alfa calcula como $2.9196.$ (Puedes hacer clic en el botón "Formas exactas" para obtener la expresión en términos de radicales, por lo que vale la pena.)

Puedes intentar usar el RSolve de Wolfram Alpha para obtener una solución exacta. No tengo experiencia en esto.

Para sonreír, lo hice con Resuelve.

También escribí una pitón script para calcularlo hasta $n=15$ de tres maneras diferentes: explícitamente, generando las cuerdas de terneros y contando las buenas, a partir de la relación de recurrencia, y de la fórmula aproximada de Wolfram Alfa. Aquí está el código:

from itertools import product

print("Explicit")
chars = '0 1 2'.split()
for n in range(4,16):
    print(n, len([s for s in product(chars, repeat=n) if '222' in ''.join(s)]))

print("Recurrence")
a=[0,0,0,1]
for n in range(4,16):
    a.append(3*a[n-1]-2*a[n-4]+2*3**(n-4))
    print(n, a[n])

r1 = .0231038-.0550705j
r2 = -.45982+.688173j
r3 = -1.04621
r4 = 2.91964

print("Formula")
for n in range(3,16):
    x = r1*r2**n
    print(n, 2*x.real+r3*r4**n+3**n)

Esto produjo la salida:

Explicit
4 5
5 21
6 81
7 295
8 1037
9 3555
10 11961
11 39667
12 130049
13 422403
14 1361385
15 4359115
Recurrence
4 5
5 21
6 81
7 295
8 1037
9 3555
10 11961
11 39667
12 130049
13 422403
14 1361385
15 4359115
Formula
3 0.9999269125799088
4 4.999775013651643
5 20.999310049238204
6 80.99788957631085
7 294.99355667854866
8 1036.9803663807425
9 3554.940278866641
10 11960.818633386094
11 39666.45003106547
12 130047.3346004755
13 422397.96336414735
14 1361369.7860350916
15 4359069.095182693

La recurrencia da el valor exacto, y es más eficiente para calcular que la fórmula aproximada. Por supuesto, sería posible obtener valores exactos para las constantes de la fórmula, ya que son las raíces de los cúbicos, pero eso haría la fórmula aún más difícil de calcular.

Answer 4

Siguiendo otro enfoque, considera una palabra binaria, donde el uno representa al ternario $2$ y el cero significa $0,1$ .

Tome una palabra binaria de longitud $n$ , teniendo $s$ y $n-s$ ceros en total, con no más que $r$ consecutivos.

Ahora el número de tales palabras binarias está dado por
$$ \eqalign { & M_b (s,r,n) = N_b (s,r,n - s + 1) \quad \left | {\;0 \le { \rm integers }s,n,r} \right.\quad = \cr & = \sum\limits_ { \left ( {0\, \le } \right )\,\,k\,\, \left ( { \le \, \min \left ( {{s \over {r + 1}}\,,\,n - s + 1} \right )} \right )} { \left ( { - 1} \right )^k \left ( \matrix { n - s + 1 \cr k \cr } \right ) \left ( \matrix { n - k \left ( {r + 1} \right ) \cr s - k \left ( {r + 1} \right ) \cr } \right )} \cr } $$ como se explica en este post relacionado .

Volviendo a las palabras ternarias, sólo tenemos que multiplicar $N_b$ por el número de formas para acolchar el $n-s$ ceros con $0$ o $1$ . Así que en general tenemos $$ \eqalign { & M_t (s,r,n) = 2^{\,n - s} M_b (s,r,n) = \cr & = 2^{\,n - s} \sum\limits_ { \left ( {0\, \le } \right )\,\,k\,\, \left ( { \le \, \min \left ( {{s \over {r + 1}}\,,\,n - s + 1} \right )} \right )} { \left ( { - 1} \right )^k \left ( \matrix { n - s + 1 \cr k \cr } \right ) \left ( \matrix { n - k \left ( {r + 1} \right ) \cr s - k \left ( {r + 1} \right ) \cr } \right )} \cr } $$ que sumó más de $s$ da
$T(r,n)=$ el número de cuerdas ternarias de longitud $n$ teniendo como máximo $r$ dos consecutivos $$ \bbox [lightyellow] { T(r,n) = \sum\limits_ { \left ( {0\, \le } \right )\,\,s\,\, \left ( { \le \,n} \right )} {2^{\,n - s} \sum\limits_ { \left ( {0\, \le } \right )\,\,k\,\, \left ( { \le \, \min \left ( {{s \over {r + 1}}\,,\,n - s + 1} \right )} \right )} { \left ( { - 1} \right )^k \left ( \matrix { n - s + 1 \cr k \cr } \right ) \left ( \matrix { n - k \left ( {r + 1} \right ) \cr s - k \left ( {r + 1} \right ) \cr } \right )} } }$$

Note que puede extenderse fácilmente a palabras cuaternarias, quinarias, ...

Para su caso particular entonces, el número está dado por $3^n-T(2,n)$ que se comprueba con las fórmulas ya dadas en las respuestas precedentes.