Wikipedia y en Wolfram MathWorld dicen que la fórmula para el número de distinto $k$-ary collares de longitud $n$ es:
$ N_k(n) = \frac{1}{n}\sum_{d|n} {\phi (d) k ^ {n/d}} $$
¿Qué es la intuición detrás de esta fórmula?
Respuesta
¿Demasiados anuncios?
user1952009
Puntos
81
El uso de la conmutatividad de la convolución de Dirichlet
$$n N_k(n)= \sum_{d |n} k^{n/d} \phi(d) = \sum_{d |n} k^{n/d} \sum_{l | d} \mu(l) \frac{d}{l} =\sum_{d |n} \frac{n}{d} \sum_{l | d} \mu(l) k^{d/l}$$
donde
$k^n$ es el número de $n$-periódico $k$-ary secuencias
$f_k(n)=\sum_{l | n} \mu(l) k^{n/l}$ (Möbius de la inversión) es el número de periódicos $k$-ary secuencias cuyo período de menos es $n$
$\frac{1}{n} f_k(n)$ es el número de $k$-ary secuencias cuyo período de menos es $n$ y quotiented por el cambio de equivalencia
$\sum_{d | n} \frac{f_k(d)}{d} $ es el número de $k$-ary secuencias cuyo período de $| n$ y quotiented por el cambio de equivalencia, es decir,. el número de collares de longitud $n$.
