Me encontré con este resultado haciendo un poco de teoría de la representación de la permutación grupo $S_n$ $$ \sum\limits_{\sigma \in S_n} (\mbox{number of fixed points of } \sigma)^2 = 2 n!$$
Esto se puede probar muy fácilmente mediante la permutación de la representación de $S_n$. ¿Alguien sabe de una forma directa y más elemental forma de probar esto sin el uso de cualquier teoría de la representación?
Usted puede utilizar Burnside del lexema. $\text{Fix}(\pi)^2$ es el número de elementos fijos por $\pi$ actuando en $[n]^2$ donde $[n] = \{ 1, 2, ... n \}$, por lo que Burnside del lexema le dice que
$$\frac{1}{n!} \sum_{\pi \in S_n} \text{Fix}(\pi)^2$$
es el número de órbitas de $S_n$ actuando en $[n]^2$. Pero hay, por inspección, dos órbitas: los pares ordenados $(a, b)$ donde $a \neq b$, y los pares ordenados $(a, a)$.
(Ejercicio: generalizar este argumento para averiguar $\displaystyle \frac{1}{n!} \sum_{\pi \in S_n} \text{Fix}(\pi)^k$.)
Podemos utilizar básicos de la teoría de la probabilidad. Tomar una muestra aleatoria de permutación. Deje $X_i=1$ si $i$ es un punto fijo de la permutación, y deje $X_i=0$ lo contrario. A continuación, el número de puntos fijos es $X_1+\cdots+X_n$. Square. Tenemos $$\sum_i X_i^2+\sum_{(i,j), i\ne j} X_iX_j.$$ Ahora, por la linealidad de la expectativa, $$E((X_1+\cdots +X_n)^2)=\sum_iE(X_i^2)+\sum_{(i,j), i\ne j}E(X_iX_j).\tag{1}$$ Tenemos $\Pr(Xi=1)=\frac{1}{n}$$\Pr(X_iX_j=1)=\frac{1}{n(n-1)}$.
De ello se desprende que $E((X_1+\cdots+X_n)^2)=2$. Para nuestros suma, se multiplica por el número de $n!$ de las permutaciones.
Comentario: Otro ejemplo de un medio de prueba.
Aquí hay una respuesta mediante Alteraciones. Puramente combinatoric.
Para cualquier conjunto de $k$ elementos hay $\mathcal{D}(n-k)$ permutaciones que arreglar los $k$ elementos y volver loca a la de los demás. Hay $\binom{n}{k}$ formas de elegir el $k$ elementos. De modo que la suma de los cuadrados del número de puntos fijos es $$ \begin{align} \sum_{k=0}^nk^2\binom{n}{k}\mathcal{D}(n-k) &=\sum_{k=0}^nk(k-1)\binom{n}{k}\mathcal{D}(n-k)\\ &+\sum_{k=0}^nk\binom{n}{k}\mathcal{D}(n-k)\\ &=\sum_{k=0}^nn(n-1)\binom{n-2}{k-2}\mathcal{D}((n-2)-(k-2))\\ &+\sum_{k=0}^nn\binom{n-1}{k-1}\mathcal{D}((n-1)-(k-1))\\[6pt] &=n(n-1)(n-2)!\\[12pt] &+n(n-1)!\\[12pt] &=2n!\tag{1} \end{align} $$ para $n\ge2$. Hemos utilizado la fórmula de $(2)$ a partir de la citada respuesta: $$ n!=\sum_{k=0}^n\binom{n}{k}\mathcal{D}(n-k)\etiqueta{2} $$ Para $n=1$, $n(n-1)(n-2)!+n(n-1)!=1$ y para $n=0$, la suma es $0$.
La generalización de
Qiaochu una pregunta que en realidad yo había pensado, pero había perdido un punto fino: ¿Cómo esta generalizar para sumar los otros poderes del número de puntos fijos? Para esto, vamos a utilizar los Números de Stirling del Segundo Tipo (cuya definición de ecuación es inferior en rojo) y la ecuación de $(2)$ por encima. $$ \newcommand{\stirtwo}[2]{\left\{{#1}\cima{#2}\right\}} \begin{align} \sum_{k=0}^n\color{#C00000}{k^p}\binom{n}{k}\mathcal{D}(n-k) &=\sum_{k=0}^n\color{#C00000}{\sum_{j=0}^p\stirtwo{p}{j}\binom{k}{j}j!}\binom{n}{k}\mathcal{D}(n-k)\\ &=\color{#00A000}{\sum_{k=0}^n}\sum_{j=0}^p\stirtwo{p}{j}\binom{n}{j}j!\color{#00A000}{\binom{n-j}{k-j}\mathcal{D}((n-j)-(k-j))}\\ &=\sum_{j=0}^p\stirtwo{p}{j}\binom{n}{j}j!\color{#00A000}{(n-j)!}\\ &=\sum_{j=0}^n\stirtwo{p}{j}n!\tag{3} \end{align} $$ Para $n\ge p$, $(3)$ puede ser simplificado a $$ \sum_{j=0}^n\stirtwo{p}{j}n!=\mathrm{B}_pn!\la etiqueta{4} $$ donde $\mathrm{B}_p=\displaystyle\sum_{j=0}^p\stirtwo{p}{j}$ son de la Campana de los Números.
El etiquetado de las especies de $\mathcal{Q}$ de permutaciones con puntos fijos marcados con las que estamos trabajando aquí es $$\mathfrak{P}\left(\mathcal{UZ} + \mathfrak{C}_2(\mathcal{Z}) + \mathfrak{C}_3(\mathcal{Z}) + \mathfrak{C}dimm_4(\mathcal{Z})+\cdots\right).$$
Por lo tanto, la bivariante de generación de función correspondiente a $\mathcal{Q}$ está dado por $$G(z, u) = \exp\left(uz-z+\log\frac{1}{1-z}\right) = \frac{e^{-z}}{1-z} e^{uz}.$$ Queremos cambiar los términos de tener la forma de $q\times u^k z^n/n!$ a $q\times k^2 z^n/n!$, por lo que se diferencian con respecto a $u$ para obtener $$\frac{d}{du} G(z,u) = \frac{e^{-z}}{1-z} z e^{uz}$$ y multiplicar por $u$ $$\left(u\frac{d}{du}\right) G(z,u) = \frac{e^{-z}}{1-z} uz e^{uz}.$$ Diferenciar con respecto a $u$ una vez más para obtener $$\frac{d}{du}\left(u\frac{d}{du}\right) G(z, u) =\frac{e^{-z}}{1-z} \left(z e^{uz} + uz^2 e^{uz}\right)$$ y finalmente poner el $u=1$ para el resultado final $$\left.\frac{d}{du}\left(u\frac{d}{du}\right) G(z, u) \right|_{u=1} = \frac{e^{-z}}{1-z} \left(z e^{z} + z^2 e^{z}\right) = \frac{z+z^2}{1-z}.$$ Ahora para $n\ge 2$ hemos $$n! [z^n] \frac{z+z^2}{1-z}= 2\times n!,$$ hecho (el valor en $n=1$ es correcto también). La recolección de pruebas en esta página y su diversidad es notable. Una especie estrechamente relacionada es estudiado en este reciente MSE enlace.
Adenda. Aquí es una prueba de la generalización por @robjohn. Observar que $$\left.\left(\frac{d}{du}\right)^k G(z, u)\right|_{u=1}$$ es la generación de la función de los factoriales de los momentos de la RV $F$ que representan los puntos fijos, por ejemplo, $$\left.\left(\frac{d}{du}\right)^3 G(z, u)\right|_{u=1} = \sum_{n\ge 0} \mathrm{E}[F_n(F_n-1)(F_n-2)] z^n.$$ Ahora recuerdo que $$x^q = \sum_{k=0}^q {q\brace k} x^{\underline{k}}.$$ Esto implica inmediatamente que $$\mathrm{E}[F_n^q] = [z^n] \sum_{k=0}^p {q\llave k} \left.\left(\frac{d}{du}\right)^k G(z, u)\right|_{u=1} = [z^n] \sum_{k=0}^p {q\llave k}\left. \frac{e^{-z}}{1-z} z^k e^{uz}\right|_{u=1} \\ = [z^n] \sum_{k=0}^p {q\llave k} \frac{z^k}{1-z}.$$ Esto significa que para $n\ge q$ hemos $$\mathrm{E}[F_n^q] = \sum_{k=0}^q {q\brace k} = B_q$$ como se reivindica.
Aquí hay una respuesta utilizando . Puramente combinatoric.
Para cualquier conjunto de $k$ elementos hay $\mathcal{D}(n-k)$ permutaciones que arreglar los $k$ elementos y volver loca a la de los demás. Hay $\binom{n}{k}$ formas de elegir el $k$ elementos. De modo que la suma de los cuadrados del número de puntos fijos es $$ \begin{align} \sum_{k=0}^nk^2\binom{n}{k}\mathcal{D}(n-k) &=\sum_{k=0}^nk(k-1)\binom{n}{k}\mathcal{D}(n-k)\\ &+\sum_{k=0}^nk\binom{n}{k}\mathcal{D}(n-k)\\ &=\sum_{k=0}^nn(n-1)\binom{n-2}{k-2}\mathcal{D}((n-2)-(k-2))\\ &+\sum_{k=0}^nn\binom{n-1}{k-1}\mathcal{D}((n-1)-(k-1))\\[6pt] &=n(n-1)(n-2)!\\[12pt] &+n(n-1)!\\[12pt] &=2n!\tag{1} \end{align} $$ para $n\ge2$. Hemos utilizado la fórmula de $(2)$ desde el $$ n!=\sum_{k=0}^n\binom{n}{k}\mathcal{D}(n-k)\etiqueta{2} $$ Para $n=1$, $n(n-1)(n-2)!+n(n-1)!=1$ y para $n=0$, la suma es $0$.
La generalización de
Qiaochu una pregunta que en realidad yo había pensado, pero había perdido un punto fino: ¿Cómo esta generalizar para sumar los otros poderes del número de puntos fijos? Para esto, vamos a utilizar (cuya definición de ecuación es inferior en rojo) y la ecuación de $(2)$ por encima. $$ \newcommand{\stirtwo}[2]{\left\{{#1}\cima{#2}\right\}} \begin{align} \sum_{k=0}^n\color{#C00000}{k^p}\binom{n}{k}\mathcal{D}(n-k) &=\sum_{k=0}^n\color{#C00000}{\sum_{j=0}^p\stirtwo{p}{j}\binom{k}{j}j!}\binom{n}{k}\mathcal{D}(n-k)\\ &=\color{#00A000}{\sum_{k=0}^n}\sum_{j=0}^p\stirtwo{p}{j}\binom{n}{j}j!\color{#00A000}{\binom{n-j}{k-j}\mathcal{D}((n-j)-(k-j))}\\ &=\sum_{j=0}^p\stirtwo{p}{j}\binom{n}{j}j!\color{#00A000}{(n-j)!}\\ &=\sum_{j=0}^n\stirtwo{p}{j}n!\tag{3} \end{align} $$ Para $n\ge p$, $(3)$ puede ser simplificado a $$ \sum_{j=0}^n\stirtwo{p}{j}n!=\mathrm{B}_pn!\la etiqueta{4} $$ donde $\mathrm{B}_p=\displaystyle\sum_{j=0}^p\stirtwo{p}{j}$ son Aquí hay una respuesta utilizando . Puramente combinatoric.
Para cualquier conjunto de $k$ elementos hay $\mathcal{D}(n-k)$ permutaciones que arreglar los $k$ elementos y volver loca a la de los demás. Hay $\binom{n}{k}$ formas de elegir el $k$ elementos. De modo que la suma de los cuadrados del número de puntos fijos es $$ \begin{align} \sum_{k=0}^nk^2\binom{n}{k}\mathcal{D}(n-k) &=\sum_{k=0}^nk(k-1)\binom{n}{k}\mathcal{D}(n-k)\\ &+\sum_{k=0}^nk\binom{n}{k}\mathcal{D}(n-k)\\ &=\sum_{k=0}^nn(n-1)\binom{n-2}{k-2}\mathcal{D}((n-2)-(k-2))\\ &+\sum_{k=0}^nn\binom{n-1}{k-1}\mathcal{D}((n-1)-(k-1))\\[6pt] &=n(n-1)(n-2)!\\[12pt] &+n(n-1)!\\[12pt] &=2n!\tag{1} \end{align} $$ para $n\ge2$. Hemos utilizado la fórmula de $(2)$ desde el $$ n!=\sum_{k=0}^n\binom{n}{k}\mathcal{D}(n-k)\etiqueta{2} $$ Para $n=1$, $n(n-1)(n-2)!+n(n-1)!=1$ y para $n=0$, la suma es $0$.
La generalización de
Qiaochu una pregunta que en realidad yo había pensado, pero había perdido un punto fino: ¿Cómo esta generalizar para sumar los otros poderes del número de puntos fijos? Para esto, vamos a utilizar los Números de Stirling del Segundo Tipo (cuya definición de ecuación es inferior en rojo) y la ecuación de $(2)$ por encima. $$ \newcommand{\stirtwo}[2]{\left\{{#1}\cima{#2}\right\}} \begin{align} \sum_{k=0}^n\color{#C00000}{k^p}\binom{n}{k}\mathcal{D}(n-k) &=\sum_{k=0}^n\color{#C00000}{\sum_{j=0}^p\stirtwo{p}{j}\binom{k}{j}j!}\binom{n}{k}\mathcal{D}(n-k)\\ &=\color{#00A000}{\sum_{k=0}^n}\sum_{j=0}^p\stirtwo{p}{j}\binom{n}{j}j!\color{#00A000}{\binom{n-j}{k-j}\mathcal{D}((n-j)-(k-j))}\\ &=\sum_{j=0}^p\stirtwo{p}{j}\binom{n}{j}j!\color{#00A000}{(n-j)!}\\ &=\sum_{j=0}^n\stirtwo{p}{j}n!\tag{3} \end{align} $$ Para $n\ge p$, $(3)$ puede ser simplificado a $$ \sum_{j=0}^n\stirtwo{p}{j}n!=\mathrm{B}_pn!\la etiqueta{4} $$ donde $\mathrm{B}_p=\displaystyle\sum_{j=0}^p\stirtwo{p}{j}$ son
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
