Longitud media de un ciclo de una permutación de n

Question

¿Cuál es la duración media de un ciclo de una permutación de $\{1,2,3,\dots ,n\}$?

Answer 1

Sugerencia: El número esperado de $k$-ciclos en una permutación al azar de $[n]$ es $\frac1k$. Así, el número esperado de ciclos en una permutación al azar de $[n]$ es $\sum_{k=1}^n\frac1k=H_n$, el número de $n$-ésimo armónico.

• ¿Cuántos ciclos hay en conjunto en todas las permutaciones de $[n]$?
• ¿Cuál es la longitud total de todos estos ciclos?
• ¿Cuál es su longitud media?

Answer 2

Por medio de enriquecimiento aquí es una alternativa mediante la formulación de la combinatoria de las especies. Las especies de permutaciones con la duración del ciclo marcado es

$$\mathfrak{P}(\mathcal{U}\mathfrak{C}_{=1}(\mathcal{Z}) + \mathcal{U}^2\mathfrak{C}_{=2}(\mathcal{Z}) + \mathcal{U}^3\mathfrak{C}_{=3}(\mathcal{Z}) + \mathcal{U}^4\mathfrak{C}_{=4}(\mathcal{Z}) + \cdots).$$

Esto le da a la generación de la función $$G(z, u) = \exp\left(uz + u^2\frac{z^2}{2} + u^3\frac{z^3}{3} + u^4\frac{z^4}{4} + u^5\frac{z^5}{5} + \cdots\right)$$ que es $$G(z, u) = \exp\left(\log\frac{1}{1-uz}\right) = \frac{1}{1-uz}.$$

Como este es un FEAG para obtener la OGF del total de la longitud de ciclo de la en todas las permutaciones debemos calcular $$\left.\frac{\partial}{\partial u} G(z, u)\right|_{u=1}.$$

Este es $$\left. (-1) \times \frac{1}{(1-uz)^{2}} \times (-z)\right|_{u=1} = \frac{z}{(1-z)^{2}}.$$

Este rendimientos $$n! [z^n] \frac{z}{(1-z)^{2}} = n! \times n.$$

Esto podría haber sido obtenida trivialmente por señalar que el ciclo de longitudes en cada permutación suma a $n$ e hay $n!$ permutaciones.

Por otro lado las especies de permutaciones con el conteo de ciclo marcado es

$$\mathfrak{P}(\mathcal{U}\mathfrak{C}_{=1}(\mathcal{Z}) + \mathcal{U}\mathfrak{C}_{=2}(\mathcal{Z}) + \mathcal{U}\mathfrak{C}_{=3}(\mathcal{Z}) + \mathcal{U}\mathfrak{C}_{=4}(\mathcal{Z}) + \cdots)$$

Esto le da a la generación de la función $$G(z, u) = \exp\left(uz + u\frac{z^2}{2} + u\frac{z^3}{3} + u\frac{z^4}{4} + u\frac{z^5}{5} + \cdots\right)$$ que es

$$G(z, u) = \exp\left(u\log\frac{1}{1-z}\right).$$

Continuar como antes, para obtener el número total de ciclos obtenemos $$\left. \exp\left(u\log\frac{1}{1-z}\right) \log\frac{1}{1-z} \right|_{u=1} = \frac{1}{1-z} \log\frac{1}{1-z}.$$

Esto le da $$n! [z^n] \frac{1}{1-z} \log\frac{1}{1-z} = n! H_n.$$

De ello se desprende que el promedio es de $$\frac{n}{H_n} \sim \frac{n}{\log n}.$$

El siguiente Arce programa muestra cómo calcular este estadístico utilizando el ciclo de índice $Z(S_n)$ del grupo simétrico.

pet_cycleind_symm :=
proc(n)
local p, s;
opción de recordar;

 si n=0 entonces devolver 1; fi;

 ampliar(1/n*añadir(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;


v :=
proc(n)
 opción de recordar;
 parte local, src, idx, totcyc;

 totcyc := 0; 

 si n=1 entonces
 idx : = [[1]];
otra cosa
 idx := pet_cycleind_symm(n);
fi;

 para la parte en idx ¿
 totcyc := totcyc + 
lcoeff(parte)*grado(parte);
od;

n/totcyc;
end;

Podemos obtener la secuencia de $$1,4/3,{\frac {18}{11}},{\frac {48}{25}},{\frac {300}{137}}, {\frac {120}{49}},{\frac {980}{363}},{\frac {2240}{761}},\ldots$$