Propabilidad de los mismos caracteres uno al lado del otro en las palabras

Question

Al principio, tengo la palabra de longitud N (N caracteres en una palabra) Y cada carácter sólo puede ser A, B o C

Ahora las palabras que quiero son palabras que tienen 3 o más caracteres iguales que están uno al lado del otro.

Ejemplo N=4

Quiero: AAAB,BBBB,ACCC........ No quiero: AABC CACC...

Ahora quiero saber cuántas palabras quiero en la longitud N

Ejemplo

N=3, solo quiero 3 palabras , AAA,BBB,CCC

Lo que se me ocurre es utilizar el sistema numérico ternario. Pero todavía no tengo ninguna idea.

¿Pueden ayudarme a resolver este problema? Gracias.

---¡¡¡EDITADO!!! He encontrado este conjunto de números que puedo utilizar, pero no tengo ni idea de cómo se relacionan entre sí, si se puede, por favor me proporcione respuesta :)

3, 15, 63, 237, 843, 2889, 9651.......

Answer 1

Será mucho más sencillo describir palabras con dos o menos caracteres repetidos. Ésas pueden construirse inductivamente:

---

Sea $A_n$ denotan el número de palabras de longitud $n$ final con dos personajes diferentes y dejar que $B_n$ denotan el número de palabras de longitud $n$ que termina con dos caracteres idénticos. Entonces debemos tener $$ \begin{align} A_{n+1}&=2(A_n+B_n)\\ B_{n+1}&=A_n \end{align} $$ Desde $B_n=A_{n-1}$ pueden combinarse con la relación de recurrencia $$ A_{n+1}=2(A_n+A_{n-1}) $$ A continuación, observe que $A_1=3$ y $A_2=6$ . Esta recurrencia puede ser resuelto para obtener $$ A_n=\frac{\sqrt 3\left((1+\sqrt 3)^n-(1-\sqrt 3)^n\right)}2 $$ Este produce una lista empezando por 3, 6, 18, 48, 132, 360, 984, 2688, 7344, 20064, 54816, 149760, 409152, 1117824, 3053952, 8343552, 22795008, 62277120, 170144256, 464842752.

---

Ahora podemos dar una expresión de forma cerrada para el número $C_n$ de palabras de longitud $n$ que tiene como máximo dos repeticiones consecutivas de una letra, a saber: $$ C_n=A_n+B_n=A_n+A_{n-1} $$ y de ahí obtenemos fácilmente el número $D_n$ de palabras de longitud $n$ tener al menos tres repeticiones consecutivas de alguna letra: $$ D_n=3^n-C_n=3^n-(A_n+A_{n-1}) $$

---

Basándonos en esto deberíamos tener: $$ \begin{align} D_2&=3^2-(6+3)&&=0\\ D_3&=3^3-(18+6)&&=3\\ D_4&=3^4-(48+18)&&=15\\ D_5&=3^5-(132+48)&&=63\\ &\vdots\\ D_{20}&=3^{20}-(464842752+170144256)&&=2851797393 \end{align} $$ etc. Los valores de $D_3,...,D_{20}$ formar la lista :

3, 15, 63, 237, 843, 2889, 9651, 31641, 102267, 326865, 1035411, 3255993, 10177131, 31649217, 98001603, 302348361, 929840091, 2851797393

Answer 2

No puedo añadir a String magnífico responder de manera significativa, excepto para decir que podría ser útil aclarar que $B_{n}$ es el número de cadenas que terminan en 2 caracteres idénticos pero no 3 o más.

De lo contrario, se daría el caso de que:

$B_{n+1} = A_{n} + B_{n}$

Para luego decir que $A_{2} = 6$ y puesto que $B_{2} = 3$ establecer formalmente $A_{1} = 3$