La exponencial de la fórmula nos dice que el ciclo de índice $Z(P_k)$ de la
sin etiquetar un conjunto de operador $\mathfrak{P}$ $k$ ranuras tiene OGF
$A$Z(P_k) = [w^k]
\exp\left(\sum_{l\ge 1} (-1)^{l-1} a_l \frac{w^l}{l}\right).$$
El deseado de probabilidad está dada por
$${n\elegir k}^{-1} \frac{1}{n}
\sum_{p=0}^{n-1}
\a la izquierda. Z(P_k)
\left(\sum_{q=1}^n z^q\ \ derecho)\right|_{z=\exp(2\pi ip/n)}.$$
Este es
$${n\elegir k}^{-1} \frac{1}{n}
\sum_{p=0}^{n-1} \left. [w^k]
\exp\left(\sum_{l\ge 1} (-1)^{l-1} \left(\sum_{q=1}^n z^{ql}\right)
\frac{w^l}{l}\right)\right|_{z=\exp(2\pi ip/n)}.$$
La evaluación de la contribución de $p=0$ primera obtenemos
$${n\elegir k}^{-1} \frac{1}{n}
[w^k] \exp\left(\sum_{l\ge 1} (-1)^{l-1} n
\frac{w^l}{l}\right)
\\ = {n\elegir k}^{-1} \frac{1}{n}
[w^k] \exp\left(n \log(1+w)\right)
\\ = {n\elegir k}^{-1} \frac{1}{n}
[w^k] (1+w)^n
= {n\elegir k}^{-1} \frac{1}{n} {n\elegir k}
= \frac{1}{n}.$$
Queda por evaluar la contribución de $1\le p\le n-1.$ Ahora para
estos $p$ si $l$ es un múltiplo de a $m = n/\gcd(p, n)$ hemos
$$\sum_{q=1}^n \exp(2\pi ip/n)^{ql} = n.$$
Tenemos cero en caso contrario. Este rendimientos para el resto de los términos sin el
escalar en frente
$$\sum_{p=1}^{n-1} [w^k]
\exp\left(\sum_{l\ge 1} (-1)^{ml-1} n
\frac{w^{ml}}{ml} \right)
= \sum_{p=1}^{n-1} [w^k]
\exp\left(-\frac{n}{m} \sum_{l\ge 1}
\frac{(-w)^{ml}}{l} \right)
\\ = \sum_{p=1}^{n-1} [w^k]
\exp\left(-\frac{n}{m}\log\frac{1}{1-(-w)^m}\right)
= \sum_{p=1}^{n-1} [w^k] (1-(-w)^{n/\gcd(p, n)})^{\gcd(p, n)}
\\ = \sum_{p=1}^{n-1} [w^k] (1+(-1)^{1+n/\gcd(p, n)}
w^{n/\gcd(p, n)})^{\gcd(p, n)}.$$
El uso de un Iverson, soporte de esta se convierte en
$$\sum_{p=1}^{n-1} [[n/\gcd(p,n)|k]] \times
{\gcd(p, n)\elegir k\gcd(p,n)/n}
(-1)^{k\gcd(p,n)/n+k}.$$
Poniendo todo junto obtenemos así
$$\bbox[5px,border:2px solid #00A000]{
\frac{1}{n} + (-1)^k
{n\elegir k}^{-1} \frac{1}{n}
\sum_{p=1}^{n-1} [[n/\gcd(p,n)|k]] \times
{\gcd(p, n)\elegir k\gcd(p,n)/n}
(-1)^{k\gcd(p,n)/n}.}$$
Tenga en cuenta que $n/\gcd(p,n)$ es un divisor de a $n$ que es al menos dos (nos
necesitaría $p=n$ conseguir $n/\gcd(p,n) = 1$ pero $p\lt n$). Esto significa
al $\gcd(k, n) = 1$ la Iverson soporte de falla para todos los $p$ y sólo
el primer término sigue siendo, que es lo que queríamos demostrar.
Como una comprobación de validez se evalúa la fórmula de al $k=n.$ La suma de los
un subconjunto es$n(n+1)/2$, por lo que debemos conseguir para la probabilidad de uno cuando
$n$ es impar y cero cuando es aún. Nos encontramos
$$\frac{1}{n} + (-1)^n
{n\elegir n}^{-1} \frac{1}{n}
\sum_{p=1}^{n-1}
{\gcd(p, n)\elegir \gcd(p,n)}
(-1)^{\gcd(p,n)}
\\ = \frac{1}{n} + (-1)^n \frac{1}{n}
\sum_{p=1}^{n-1}
(-1)^{\gcd(p,n)}
= (-1)^n \frac{1}{n}
\sum_{p=1}^{n}
(-1)^{\gcd(p,n)}
\\ = (-1)^n \frac{1}{n}
\sum_{d|n} \sum_{\gcd(p,n) = d} (-1)^d
= (-1)^n \frac{1}{n}
\sum_{d|n} (-1)^d \sum_{\gcd(p,n/d) = 1} 1
\\ = (-1)^n \frac{1}{n} \sum_{d|n} (-1)^d \varphi(n/d).$$
Evaluamos este uso formal de Dirichlet de la serie, a partir de
$\sum_{d|n} \varphi(d) = n$ que los rendimientos de
$$\sum_{n\ge 1} \frac{\varphi(n)}{n^s} = \frac{\zeta(s-1)}{\zeta(s)}.$$
Además, hemos
$$\sum_{n\ge 1} \frac{(-1)^n}{n^s} =
-\left(1-\frac{2}{2^s}\right)\zeta(s).$$
Esto significa que
$$\sum_{n\ge 1} \frac{1}{n^s} \sum_{d|n} (-1)^d \varphi(n/d)
= -\left(1-\frac{2}{2^s}\right) \zeta(s-1).$$
Ahora tenemos para $n$ incluso
$$- (-1)^n \frac{1}{n} [n^{-s}] \left(1-\frac{2}{2^s}\right) \zeta(s-1)
= - (-1)^n \frac{1}{n} (n - 2 [(n/2)^{-s}] \zeta(s-1))
\\ = - (-1)^n \frac{1}{n} (n - 2 \times n/2) = 0.$$
Obtenemos cero como sea necesario. Por otro lado, con $n$ impar encontramos
$$- (-1)^n \frac{1}{n} [n^{-s}] \left(1-\frac{2}{2^s}\right) \zeta(s-1)
= - (-1)^n \frac{1}{n} [n^{-s}] \zeta(s-1)
\\ = - (-1)^n \frac{1}{n} \times n = 1,$$
nuevamente, como lo requieren. Esto concluye la verificación de cordura. y, de hecho, la
todo el argumento.
Observación. Parte de este material está duplicado en los que no he
encuentra los enlaces, sin embargo.
