Contar las combinaciones totales

Question

Suponga que tiene K caracteres distintos. Con estos caracteres se pueden hacer varias cadenas de longitud de 1 a N y los caracteres se pueden repetir en estas cadenas. Ahora tienes que contar el total de combinaciones de tres cadenas que no tengan un prefijo común (propio/no propio). Por ejemplo, si K=2 y N=2 la respuesta es 6. Llegué a un enfoque que resulta en la siguiente suma.

$$\sum_{i=1}^n \sum_{k=j}^n \sum_{j=i}^n K^j(K^i-1)(K^k-K^{k-i}-K^{k-j})$$

Por favor, justifique si esto es correcto o bien sugiera algún buen enfoque para esto.

Answer 1

Permítanme usar $M$ en lugar de su $K$ . Entonces su fórmula, después de pulir los índices y corregir los recuentos repetidos, da

$$C_{N,M}=\sum_{i=1}^N \sum_{j=i}^N \sum_{k=j}^N \frac{M^i (M^j-M^{j-i})(M^k-M^{k-j}-M^{k-i})}{a_{i,j,k}!}$$

donde $a_{i,j,k}\in \{ 1,2,3\}$ es el número de elementos iguales en $\{i,j,k\}$

Algunos valores: $C_{2,2}=6$ , $C_{2,3}=139$ , $C_{3,2}=166$ , $C_{3,3}=7060$

Actualización: parece difícil evaluarlo exactamente para grandes $N$ . Tal vez se pueda obtener alguna asintótica mediante argumentos probabilísticos, pero no he conseguido nada útil. Una sustitución directa de la suma por una integral (suponiendo $a_{i,j,k}=1$ ) da un término principal de la forma

$$C_{N,M}\approx \frac{M^{3N}}{6 \log^3(M)}$$

Esto parece numéricamente justo.