Número de prefijos que coinciden con los sufijos

Question

Considere todos los pares de cadenas $A$ y $B$ cada una de ellas con una longitud $n$ donde $A_i, B_i \in \{0,1\}$ . Comparamos todos los prefijos de $A$ con todos los sufijos de $B$ de la misma longitud e informar cuando coincidan exactamente. Por ejemplo, considere $A=01011$ y $B=11010$ . Tenemos $0 = 0$ , $01 \ne 10$ , $010 = 010$ , $0101 \ne 1010$ y $01011 \ne 11010$ .

Para las cuerdas $A$ y $B$ informaremos de esta secuencia de coincidencias y no coincidencias como una tupla de $1$ s y $0$ s donde $1$ indica una coincidencia y $0$ indica que no hay coincidencia. Así que en el caso anterior obtenemos $(1,0,1,0,0)$ .

Tomado sobre todo $2^{2n}$ diferentes pares de $A$ y $B$ cadenas, ¿cuál es el número total de tuplas diferentes de coincidencias y no coincidentes que se obtienen?

Para $n = 1,\dots, 10$ las cifras exactas son $2,4,7,11,17,25,35,48,65,86$ .

Answer 1

La secuencia $1,2,4,7,11,17,...$ parece ser

$$\sum_{i=0}^n\kappa(i)$$ donde $\kappa(i)$ es el función de (auto)correlación kappa .

No hay fórmula para $\kappa(i)$ es conocido. Aparece en la OEIS como A005434 y se introdujo en este artículo :

• L. J. Guibas y A. M. Odlyzko, Periods in Strings, Revista de teoría combinatoria A 30:1 (1980) 19-42