Contar la suma de ciclos de los elementos en $S_n$ .

Question

Dejemos que $\sigma\in S_n$ se le dará. Escribamos $\sigma$ en su descomposición en ciclos disjuntos. Definir por $w(\sigma)$ el número de ciclos (por ejemplo, si tenemos la permutación $1\mapsto 2, 2\mapsto 4, 3\mapsto 3, 4\mapsto 1, 5\mapsto 5$ lo escribimos como $(124)(3)(5)$ así que $w(\sigma)=3$ ).

Me pidieron que encontrara $$A_n=\sum_{\sigma\in S_n}w(\sigma)$$ He encontrado la fórmula recursiva $$A_n=n!+(n-1)!\left[\frac{A_{n-1}}{(n-1)!}+\frac{A_{n-2}}{(n-2)!}+\ldots+\frac{A_{1}}{1!}\right]$$

Estuve intentando trastear con ella para ver si podía conseguir una fórmula que no dependiera de la recursividad, pero fracasé en el intento. Cualquier ayuda o pista que me lleve a hacer mi solución para $A_n$ "mejor".

Answer 1

Dejemos que $b_n=\dfrac{A_n}{n!}$ entonces su recurrencia puede ser reescrita

$$b_n=1+\frac1n\sum_{k=1}^{n-1}b_k\;,\tag{1}$$

con $b_1=1$ . Calcula algunos valores:

$$\begin{align*} &b_1=1\\ &b_2=1+\frac12\cdot1=\frac32\\ &b_3=1+\frac13\left(1+\frac32\right)=\frac{11}6\\ &b_4=1+\frac14\left(1+\frac32+\frac{11}6\right)=\frac{25}{12} \end{align*}$$

Reconozco que esos son los cuatro primeros números armónicos : $$b_n=H_n=\sum_{k=1}^n\frac1k\;.$$

Y efectivamente, los números armónicos satisfacen $(1)$ :

$$\begin{align*} 1+\frac1n\sum_{k=1}^{n-1}H_k&=1+\frac1n\sum_{k=1}^{n-1}\sum_{i=1}^k\frac1i\\ &=1+\frac1n\sum_{i=1}^{n-1}\sum_{k=i}^{n-1}\frac1i\\ &=1+\frac1n\sum_{i=1}^{n-1}\frac{n-i}i\\ &=1+\frac1n\sum_{i=1}^{n-1}\left(\frac{n}i-1\right)\\ &=1+\sum_{i=1}^{n-1}\frac1i-\frac{n-1}n\\ &=1+H_{n-1}-1+\frac1n\\ &=H_n\;. \end{align*}$$

Así, $A_n=n!H_n$ .

Añadido: He aquí otro enfoque del problema. No es demasiado difícil demostrar que el número de $\pi\in S_n$ con $k$ ciclos es $\left[n\atop k\right]$ , a Número Stirling del primer tipo . Estos tienen la función generadora $$\sum_{k\ge 0}\left[n\atop k\right]x^k=x^{\overline{n}}=x(x+1)(x+2)\dots(x+n-1)\;.$$ Diferenciar los rendimientos

$$\begin{align*} \sum_{k\ge 1}k\left[n\atop k\right]x^{k-1}&=\frac{d}{dx}\Big(x(x+1)(x+2)\dots(x+n-1)\Big)\\ &=\sum_{k=0}^{n-1}\frac{\prod_{i=0}^{n-1}(x+i)}{x+k}\;, \end{align*}$$

y evaluando en $x=1$ produce $$\sum_{k\ge 1}k\left[n\atop k\right]=\sum_{k=0}^{n-1}\frac{n!}{k+1}=n!H_n\;.$$

Answer 2

Se puede obtener una recurrencia más fácil considerando el último elemento $n$ en la permutación.

O bien $n$ se produce en un ciclo de duración mínima $2$ o forma un "ciclo" por sí mismo. En el primer caso, sacarlo de su ciclo deja una permutación de $n-1$ con el mismo número de ciclos, y dada una permutación de $n-1$ podemos insertar $n$ en $n-1$ plazas en un ciclo existente, para una contribución total de $(n-1)A_{n-1}$ a $A_n$ . En este último caso, la eliminación de $n$ sólo deja una permutación de $n-1$ que aquí surge de una sola manera; sin embargo, el número de ciclos es uno más para la permutación de $n$ que para la permutación de $n-1$ Así que en todo esto contribuye $A_{n-1}+(n-1)!$ a $A_n$ (el segundo término es para el ciclo extra en $(n-1)!$ permutaciones). Como ahora hemos contabilizado cada contribución una vez, obtenemos $$ A_n=(n-1)A_{n-1}+A_{n-1}+(n-1)! = nA_{n-1} + (n-1)! $$ Se puede simplificar dividiendo por $n!$ , dando $$ \frac{A_n}{n!}= \frac{A_{n-1}}{(n-1)!} + \frac1n, $$ que junto con $A_0=0$ obviamente da $\frac{A_n}{n!}=\sum_{i=1}^n\frac1i=H_n$ y $A_n=n!H_n$ .

Answer 3

La mejor manera de abordar esta cuestión es mediante el método simbólico.

Las permutaciones son conjuntos de ciclos, con especificación de clase combinatoria $\mathfrak P(\mathfrak C(\mathfrak Z))$ . Por lo tanto, la correspondiente función generadora exponencial (EGF) es $$ \exp \log \frac{1}{1-z} = \frac{1}{1-z},$$ donde $$ \log \frac{1}{1-z} $$ es el FEAG de los ciclos etiquetados. (Estos dos son fácilmente verificables ya que hay $n!$ permutaciones y $n!/n$ ciclos).

Si queremos contar el número de ciclos tenemos que marcar cada ciclo con una nueva variable, $u$ que da la función generadora mixta $$G(z, u) = \exp \left( u \log \frac{1}{1-z} \right).$$

Ahora un término $u^k z^n / n!$ en $G(z, u)$ representa una permutación de $n$ elementos que tienen $k$ ciclos. Para contarlos, tenemos que diferenciar con respecto a $u$ y establecer $u=1$ , obteniendo $$ \left. \frac{d}{du} G(z, u) \right|_{u=1} = \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} .$$

Pero $$ [z^n] \frac{1}{1-z} \log \frac{1}{1-z} = H_n $$ por un cálculo trivial y hemos terminado.

Hay mucho más sobre este método en Wikipedia .