El número de permutaciones que corrige un cierto número de puntos

Question

Dado el conjunto a $N:=\{1,\cdots,n\}$, vamos a $\pi$ ser una permutación en $N$. Podemos decir $i \in \{1,\cdots,n\}$ es fijo por $g$ fib $\pi(i)=i.$

Denota el conjunto de todos los permuations en $N$$S_n$. Definir $f :~N \cup \{0\} \to \mathbb{N}_{\geq 0}$ por

$f(m):=$El número de permutaciones en $S_n$ que tiene exactamente $m$ puntos fijos. Demostrar que $$\sum_{m=0}^{n} f(m) m^2=2n!$$

Comentario: parece $f(0)$ juega un papel destacado.

Answer 1

Esta solución no es totalmente combinatoria, pero creo que funciona:

La suma que queremos es que el número de permutaciones con un par ordenado $(i,j)$ de manera tal que la permutación es fija en ambos $i$$j$. Podemos ver esto al señalar que para que una permutación con $m$ puntos fijos, tenemos $m^2$ opciones de un par ordenado.

Ahora, para evaluar este número, primero escogemos un par ordenado. Si $i \ne j$, $n^2-n$ opciones de par ordenado y $(n-2)!$ opciones de permutaciones. Si $i = j$, $n$ opciones de par ordenado y $(n-1)!$ opciones de permutación, que nos da una respuesta final de la $(n^2-n)(n-2)! + n(n-1)! = 2n!.$

Answer 2

Esta es otra pregunta que puede ser abordado mediante el método simbólico, como se ve aquí. Si bien esto no es necesariamente la solución más simple que produce las formas explícitas de todas las funciones de generación y hace que el problema susceptible de automática de la combinatoria, un poderoso método desarrollado por Chyzak, Salvy y Flajolet.

Las permutaciones son un conjunto de ciclos, teniendo combinatoria de especificaciones de clase $\mathfrak P(\mathfrak C(\mathfrak Z))$. Por tanto, la correspondiente exponencial de generación de función (EGF) es $$ \exp \log \frac{1}{1-z} = \frac{1}{1-z},$$ where $$ \log \frac{1}{1-z} $$ is the EGF of labelled cycles. (These two are easily verified as there are $n!$ permutations and $n!/$ n ciclos.)

Si queremos contar el número de puntos fijos necesitamos marcar cada punto fijo con una nueva variable, $u$, lo que da la clase especificación $\mathfrak P(\mathfrak C(\mathcal Z) -\mathcal Z + \mathcal U \mathcal Z )$. y la mezcla de generación de función $$G(z, u) = \exp \left( \log \frac{1}{1-z} -z + uz \right) = \frac{1}{1-z} e^{-z} e^{uz}. $$

Un plazo $u^m z^n/n!$ $G(z, u)$ representa una permutación de longitud $n$ $m$ puntos fijos. Buscamos multiplicar este término por $m^2$. Por lo tanto podemos diferenciar con respecto a $u$, se multiplica por $u$, se diferencian por $u$ nuevo y, finalmente, se multiplica por $u$ una vez más, la obtención de $$ H(z, u) = \frac{1}{1-u} u \left( \frac{d}{du} \left( u \frac{d}{du} G(z, u) \right)\right) = \frac{1}{1-u} \frac{1}{1-z} e^{-z} (uz + u^2z^2) e^{uz}.$$ El factor de $\frac{1}{1-u}$, cuando se produce en un producto con otro poder formal de la serie en $u$, producirá la serie para que la suma de la primera $n$ elementos. Se incluye aquí a construir una generación de función para la suma, por lo que $$ n! [u^n][z^n] H(z, u) = \sum_{m=0}^n f(m, n) m^2.$$

El diferenciar y multiplicar se sabe lo que se denomina una marca de operación en la simbólica de la combinatoria.

Queda por extraer de los coeficientes. Tenemos $$ \begin{align} & [z^n] \frac{1}{1-u} \frac{1}{1-z} e^{-z} \, uz \, e^{uz} = \frac{u}{1-u} [z^{n-1}] \frac{1}{1-z} e^{(u-1)z} \\ &= \frac{u}{1-u} \sum_{k=0}^{n-1} [z^k] e^{(u-1)z} = \frac{u}{1-u} \sum_{k=0}^{n-1} \frac{(u-1)^k}{k!} \\ &= u \left( \frac{1}{1-u} - \sum_{k=1}^{n-1} \frac{(u-1)^{k-1}}{k!}\right) \end{align}$$ Del mismo modo, $$ \begin{align} & [z^n] \frac{1}{1-u} \frac{1}{1-z} e^{-z} \, u^2z^2 \, e^{uz} = \frac{u^2}{1-u} [z^{n-2}] \frac{1}{1-z} e^{(u-1)z} \\ &= \frac{u^2}{1-u} \sum_{k=0}^{n-2} [z^k] e^{(u-1)z} = \frac{u^2}{1-u} \sum_{k=0}^{n-2} \frac{(u-1)^k}{k!} \\ &= u^2 \left( \frac{1}{1-u} - \sum_{k=1}^{n-2} \frac{(u-1)^{k-1}}{k!}\right) \end{align}$$

De ello se sigue que $$ n! H(z, u) = n! [u^n] \left( u \left( \frac{1}{1-u} - \sum_{k=1}^{n-1} \frac{(u-1)^{k-1}}{k!} \right) + u^2 \left( \frac{1}{1-u} - \sum_{k=1}^{n-2} \frac{(u-1)^{k-1}}{k!}\right)\right)$$ que los rendimientos de $$n! \, [u^n] \left( u \frac{1}{1-u} + u^2 \frac{1}{1-u} \right)= 2n!,$$ que iba a ser mostrado.

La belleza de este método es que es algorítmica, y puede ser implementado en sistemas de álgebra computacional como en el paquete mencionado anteriormente. En realidad, es posible tener un programa de calcular todas las funciones de generación que hemos visto usando sólo la especificación de la combinatoria de la clase.

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