En esta respuesta, le presentaré una prueba que me vino a la mente hace cinco años cuando me encontraba con gente en una sesión Waldorf en mi ciudad natal...
En primer lugar, escribamos una permutación $\pi$ en $n$ números $\left[n\right]$ como
$$\pi = \begin{pmatrix} 1 & 2 & 3 & \cdots & n \\ \pi(1) & \pi(2) & \pi(3) & \cdots & \pi(n) \end{pmatrix}$$
A continuación, definiremos una función $C(\pi)$ como el número de ciclos por permutación dada $\pi$ . El conjunto de todas las permutaciones de la longitud $n$ se denota como $S_n$ . Para la longitud de una permutación escribiremos $l(\pi)=n$ Entonces, consideremos esta suma
$$C_n(x) = \sum_{l(\pi)=n} x^{C(\pi)}$$
donde sumamos sobre todas las permutaciones $\pi$ con longitud $n$ . Claramente $C_n(1)=n!$ y $C_1(x) = x$ . Demostraremos que existe una relación de recurrencia simple, a saber $C_{n+1}(x)=(x+n)C_n(x).$
En primer lugar, construyamos el conjunto de todas las permutaciones en $\left[n+1\right]$ . En primer lugar, elija cualquier $\pi$ con $l(\pi)=n$ y añadir un ciclo $(n+1, n+1)$ es decir, tenemos la permutación $\pi^*$
$$\pi^* = \begin{pmatrix} 1 & 2 & 3 & \cdots & n & n+1 \\ \pi(1) & \pi(2) & \pi(3) & \cdots & \pi(n) & n+1 \end{pmatrix}$$
Por lo tanto, esta permutación tiene exactamente $C(\pi^*) = C(\pi)+1$ ciclos. A partir de esta permutación, utilizando una inversión, podemos construir otra $n$ permutaciones distintas ${\pi^*_i}_{i=1}^n$ de la forma
$$\pi^*_i = \begin{pmatrix} 1 & 2 & 3 & \cdots & i & \cdots & n & n+1 \\ \pi(1) & \pi(2) & n+1 & \cdots & n & \cdots & \pi(n) & \pi(i) \end{pmatrix}$$
El número de ciclos de $\pi^*_i$ es uno menos que $\pi^*$ ya que la inversión fusiona dos ciclos disjuntos, por lo que $C(\pi^*_i)=C(\pi)$ (ver la imagen de abajo para una explicación, allí $\pi^*$ representa una composición de $\pi$ con la inversión de elementos $x,y$ ).
![enter image description here]()
Sin embargo, no hemos alterado el orden de los números ${1,2,3,\dots,n}$ por lo que existe una inyección de $\pi^*_i$ a $\pi$ . El número total de $\pi^*_i$ permutaciones es por tanto $n n!$ junto con $\pi^*$ permutaciones que hemos construido $nn!+n! = (n+1)!$ permutaciones distintas por lo que hemos cubierto todas las permutaciones en $S_{n+1}$ . Por lo tanto,
$$C_{n+1}(x) = \!\!\!\!\sum_{l(\pi)=n+1} \!\! \!\! x^{C(\pi)} = \!\!\!\!\sum_{l(\pi^*)=n+1} \!\! \!\!\! x^{C(\pi^*)} + \!\sum_{i=1}^{n}\!\sum_{l(\pi^*_i)=n+1} \!\! \!\!\! x^{C(\pi^*_i)} = \!\sum_{l(\pi)=n} \!\! x^{C(\pi)+1} + \!\sum_{i=1}^{n}\!\sum_{l(\pi)=n+1} \!\! \!\! x^{C(\pi)}= (x+n)C_n(x)$$
Es decir, esto demuestra que
$$C_n(x) = (x+n-1)(x+n-2)\cdots (x+3)(x+2)(x+1)x$$
o
$$D_n(x) = \ln C_n(x) = \sum_{k=1}^n \ln(x+k-1)$$
Definamos el nº número armónico del mº tipo $H_n^{(m)}$ como
$$H_n^{(m)} = \sum_{k=1}^{n} \frac{1}{k^m}$$
con asintótica $H_n=H_n^{(1)} \sim \gamma + \ln n$ , donde $\gamma$ es la constante de Euler-Mascheroni, y para $m>1$ tenemos en el límite
$$\lim_{n\rightarrow\infty}H_n^{(m)} = \sum_{k=1}^{\infty} \frac{1}{k^m} = \zeta(m)$$
où $\zeta$ es la función zeta de Riemann. Evidentemente, puedes comprobar por ti mismo, para las derivadas de $D_n(x)$ en $x=1$ que
$$D_n^{(m)}(1) = (-1)^{m-1}(m-1)! H_n^{(m)}$$
para $m>1$ y $D_n(1)=\ln n!$ . La estadística completa viene dada por $C_n(x)$ (o $D_n(x)$ ). Para encontrar la media $\mu_n$ un número medio de ciclos en una permutación aleatoria de longitud $n$ sólo tenemos que calcular la relación
$$\mu_n=\mathbb{E}\left[C\right]=\frac{1}{n!}\sum_{l(\pi)=n} C(\pi) = \frac{1}{n!}\left(\sum_{l(\pi)=n} x^{C(\pi)}\right)'\bigg{|}_{x=1}=\frac{1}{n!}\left(C_n(x)\right)'=\frac{C_n(1)}{n!}D_n'(1)=H_n=\sum_{k=1}^n \frac{1}{k}.$$
La varianza se define como $\sigma^2_n = \mathbb{E}\left[C^2\right]-\mathbb{E}^2\left[C\right]$ . Primero tenemos
$$\mathbb{E}\left[C^2\right]=\frac{1}{n!}\sum_{l(\pi)=n} C^2(\pi) = \frac{1}{n!} (x C'_n(x))'\bigg{|}_{x=1}=\frac{1}{n!} (x C_n(x) D'_n(x))'\bigg{|}_{x=1}=\frac{1}{n!} C_n(1)\left(D'_n(1)+D'^2(1)+ D''_n(1)\right)= H_n^2 + H_n + H_n^{(2)}.$$
Por lo tanto,
$$\sigma_n^2 = H_n + H_n^{(2)} \rightarrow \gamma + \frac{\pi^2}{6} + \ln n$$
