Nota: Esta respuesta no es correcta porque cuenta los duplicados. Por ejemplo, la cadena aabaa se contaría dos veces ya que el prefijo a coincide con el sufijo a y el prefijo aa coincide con el sufijo aa. Si tengo tiempo, arreglaré la respuesta. Espero que alguien más lo haga antes de que lo haga.
Rompemos la cadena en tres partes: prefijo, sufijo y medio. El prefijo y el sufijo son idénticos. Supongamos que tienen una longitud [matemática] m [/ matemática] . Observe que [math] m \ le \ left \ lfloor {\ frac n 2} \ right \ rfloor [/ math] (de lo contrario, la longitud combinada del prefijo y sufijo sería mayor que [math] n [/ math]. Entonces hay [math] k ^ m [/ math] tales prefijos. Hay [math] n – 2m [/ math] letras restantes en la palabra, cada una de las cuales puede tomar cualquiera de [math] k [/ math] letras. Así que hay [math] k ^ {n-2m} [/ math] tales cadenas “intermedias”. Combinando esto nos dice que hay exactamente [math] k ^ {nm} [/ math] cadenas del tipo que desea tener un prefijo de longitud [math] m \ le \ left \ lfloor {\ frac n 2} \ right \ rfloor [/ math].
Ahora podemos sumar esto sobre todas las posibles longitudes de prefijo para obtener el número total de cadenas, [math] N [/ math]:
[matemáticas] N = \ sum_ {m = 1} ^ {\ left \ lfloor {\ frac n 2} \ right \ rfloor} k ^ {nm} [/ math]
- ¿Cuál sería un protocolo para hacer que dos personas presenten dos números únicos en un intervalo sin revelar sus números?
- Cómo encontrar el punto máximo en un polígono convexo usando la búsqueda ternaria
- Cómo encontrar si un número entero ‘M’ es divisible por ‘N’ (número entero) o no sin usar la operación de división / módulo y tampoco se permiten bucles
- ¿Cuál es más lento entre: encontrar el inverso de una matriz y el determinante de una matriz? ¿Por qué?
- Cómo calcular la distribución de una variable aleatoria [matemática] Z [/ matemática] compuesta de [matemática] n [/ matemática] variables aleatorias independientes [matemática] X_i [/ matemática] con funciones de distribución continua arbitrarias
[matemáticas] N = k ^ {n-1} \ sum_ {m = 1} ^ {\ left \ lfloor {\ frac n 2} \ right \ rfloor} k ^ {1-m} [/ math]
[matemáticas] N = k ^ {n-1} \ sum_ {m = 0} ^ {\ left \ lfloor {\ frac n 2} \ right \ rfloor-1} k ^ {- m} [/ math]
La suma es solo una serie geométrica finita de [math] \ left \ lfloor {\ frac n 2} \ right \ rfloor [/ math] términos que comienzan con 1 que tiene una relación [math] 1 / k [/ math]. Puede buscar la fórmula si no la conoce. (Creo que lo tengo aquí mismo).
[matemáticas] N = k ^ {n-1} \ frac {1 – k ^ {- \ left \ lfloor {\ frac n 2} \ right \ rfloor}} {1 – \ frac 1 k} [/ math]
[matemáticas] N = k ^ {n} \ frac {1 – k ^ {- \ left \ lfloor {\ frac n 2} \ right \ rfloor}} {k-1} [/ math]