El número de ciclos de todas las permutaciones pares de$[n]$ y el número de ciclos de todas las permutaciones impares difieren en$(-1)^n (n-2)!$

Question

Estoy tratando de resolver la tarea 44 del primer capítulo de Stanleys la Combinatoria Enumerativa (se encuentra aquí).

Muestran que el número total de ciclos de todas las permutaciones de $[n]$ y el número total de ciclos de todas las permutaciones impares de $[n]$ difieren por $(−1)^n (n − 2)!$. Uso de funciones de generación.

Yo podría estar completamente fuera de la pista aquí, pero la manera en que yo pensaba de este problema es la siguiente. Una permutación se puede escribir como un producto de ciclos disjuntos, y una permutación es impar si hay un número impar de hasta-duración de los ciclos.

El conjunto de los ciclos de la partición de $[n]$ en discontinuo de las órbitas, y por lo tanto el número de ciclos de todas las permutaciones impares de $[n]$ debe ser igual al número de particiones de $[n]$ en partes iguales, con un número impar de dichas partes (y de manera similar para el permutaciones).

Esto es correcto o he entendido algo? También, no estoy muy seguro de cómo proceder a partir de aquí y cómo configurar las funciones de generación.

Encontré a esta pregunta, que podría ser de alguna utilidad, si mi interpretación de este problema es la correcta.

Sin embargo, yo no ver claramente cómo uno podría terminar con $(-1)^n (n-2)!$ a partir de eso.

Cualquier ayuda sería muy apreciada :)

Answer 1

Aquí es un argumento completamente diferente de joriki; es también una solución completa.

Un ciclo es una permutación impar iff su longitud es aún, por lo que una permutación escrito como un producto de ciclos disjuntos es incluso iff un número par de factores que son incluso ciclos. Deje $\pi=\sigma_1\dots\sigma_k$ ser una permutación de $[n]$ escrito como un producto de $k$ ciclos disjuntos. A continuación,$n=|\,\sigma_1|+\dots+|\,\sigma_k|$, por lo que la paridad de $n$ es el mismo que el de la paridad del número de ciclos de longitud impar. Por lo tanto, $\pi$ tiene un número de ciclos de longitud iff $n$ $k$ tienen la misma paridad, es decir, iff $(-1)^{n+k}=1$.

Deje $e_n$ el número total de ciclos en incluso permutaciones de $[n]$, vamos a $o_n$ el número total de ciclos impares permutaciones de $[n]$, y deje $d_n=e_n-o_n$. El número total de permutaciones de $[n]$ $k$ ciclos está dado por $\left[n\atop k\right]$, el unsigned número de Stirling de primera especie. Cada uno de estos $\left[n\atop k\right]$ permutaciones contribuye $k$ ciclos a $e_n$ si $(-1)^{n+k}=1$, e $o_n$ si $(-1)^{n+k}=(-1)$. Por lo tanto, cada uno contribuye $(-1)^{n-k}k$$d_n$, y de ello se sigue que

$$d_n=\sum_k(-1)^{n+k}k\left[n\atop k\right]\;.$$

Ahora $(-1)^{n+k}\left[n\atop k\right]=(-1)^{n-k}\left[n\atop k\right]$ es el firmado número de Stirling de primera especie, para los que tenemos la generación de la función $$\sum_k(-1)^{n+k}\left[n\atop k\right]x^k=x^{\underline{n}}\;.\tag{1}$$

(Aquí se $x^{\underline{n}}=x(x-1)(x-2)\cdots(x-n+1)$ es la caída de factorial, a veces escrito $(x)_n$.)

Diferenciar $(1)$ con respecto al $x$ obtener

$$\sum_k(-1)^{n+k}k\left[n\atop k\right]x^{k-1}=Dx^{\underline{n}}=(x-n+1)Dx^{\underline{n-1}}+x^{\underline{n-1}}\;,$$

donde el último paso es simplemente el producto de la regla, ya que $x^{\underline{n}}=x^{\underline{n-1}}(x-n+1)$. Pero $$Dx^{\underline{n-1}}=\sum_k(-1)^{n-1+k}k\left[{n-1}\atop k\right]x^{k-1}\;,$$ lo

$$\sum_k(-1)^{n+k}k\left[n\atop k\right]x^{k-1}=\sum_k(-1)^{n-1+k}k\left[{n-1}\atop k\right]x^{k-1}+x^{\underline{n-1}}\;.\tag{2}$$

Ahora evaluar $(2)$ $x=1$ para obtener $$d_n=(2-n)d_{n-1}+[n=1]\;,\tag{3}$$ where the last term is an Iverson bracket. If we set $d_0=0$, $(3)$ yields $d_1=[1=1]=1$, which by direct calculation is the correct value: the only permutation of $[1]$ is the identity, which is even and has one cycle. It's now a trivial induction to check that $d_n=(-1)^n(n-2)!$ for all $n\ge 1$: la inducción paso es

$$\begin{align*}d_{n+1}&=\Big(2-(n+1)\Big)d_n\\ &=(1-n)(-1)^n(n-2)!\\ &=(-1)^{n+1}(n-1)!\;. \end{align*}$$

Añadido: Se me ocurre que hay un lugar de fácil argumento de que hace no utilice funciones de generación. Deje $\sigma$ cualquier $k$ciclo de formado de los elementos de la $[n]$; a continuación, $\sigma$ es un factor en la $(n-k)!$ permutaciones de $[n]$. Por otra parte, exactamente la mitad de estas permutaciones son incluso menos $n-k$ $0$ o $1$. Por lo tanto, $\sigma$ contribuye a $d_n$ fib $k=n$ o $k=n-1$.

Hay $(n-1)!$ $n$-ciclos; son incluso permutaciones iff $n$ es impar, de modo que contribuyan $(-1)^{n-1}(n-1)!$$d_n$.

Hay $n(n-2)!$ $(n-1)$-ciclos: hay $n$ formas para elegir el elemento de $n$ que es no parte de la $(n-1)$-ciclo, y el otro $n-1$ elementos se pueden organizar en $(n-2)!$ diferentes $(n-1)$-ciclos. El resultado de permutación de $[n]$ es incluso iff $n-1$ es impar, es decir, iff $n$ es aún, de modo que contribuyan $(-1)^nn(n-2)!$$d_n$.

De ello se sigue que $$\begin{align*}d_n&=(-1)^nn(n-2)!+(-1)^{n-1}(n-1)!\\ &=(-1)^n\Big(n(n-2)!-(n-1)!\Big)\\ &=(-1)^n(n-2)!\Big(n-(n-1)\Big)\\ &=(-1)^n(n-2)!\;. \end{align*}$$

Answer 2

Advertencia: Esta es una solución completa; usted lo desea, puede leer sólo una parte de ella para conseguir en el camino correcto y, a continuación, ver si se puede completar.

El número de permutaciones de $[n]$$n!$, por lo que la exponencial de generación de función para el número de permutaciones es

$$\sum_{n=0}^\infty x^n=\frac1{1-x}\;.$$

El número de ciclos que contiene todos los elementos de a$[n]$$(n-1)!$, por lo que la exponencial de generación de función para el número de ciclos es

$$\sum_{n=1}^\infty \frac1nx^n=-\log(1-x)\;.$$

La exponencial de generación de función para el número de ordenadas tuplas de $k$ ciclos de conjunto que contiene todos los elementos de a $[n]$ por lo tanto $(-\log(1-x))^k$.

El número de permutaciones de $[n]$ $k$ ciclos es el número de desordenada tuplas de $k$ ciclos de conjunto que contiene todos los elementos de a $[n]$, por lo que tenemos que dividir por un factor de $k!$ para el número de permutaciones de los ciclos; por lo que la exponencial de generación de función para el número de permutaciones de $[n]$ $k$ ciclos es $(-\log(1-x))^k/k!$. Podemos comprobar este resultado al sumar más de $k$ recuperar

$$\sum_{k=0}^\infty\frac{(-\log(1-x))^k}{k!}=\mathrm e^{-\log(1-x)}=\frac1{1-x}\;.$$

Ahora sólo tenemos que incluir un signo de la paridad de las permutaciones. Una permutación de $[n]$ $k$ ciclos tiene paridad $(-1)^{k+n}$. Poner a prueba el enfoque, primero vamos a calcular el exceso de permutaciones sobre las permutaciones impares, sin contar los ciclos. Incluyendo el factor de $(-1)^k$ en los coeficientes de rendimientos

$$\sum_{k=0}^\infty(-1)^k\frac{(-\log(1-x))^k}{k!}=\mathrm e^{\log(1-x)}=1-x\;,$$

y, a continuación, teniendo en cuenta el factor de $(-1)^n$ se obtiene el resultado esperado, es decir, que el exceso de es $1$ $n=0$ $n=1$ $0$ lo contrario.

Ahora para contar el número total de ciclos sólo tenemos que incluir un factor de $k$ en la suma:

$$ \begin{eqnarray} \sum_{k=0}^\infty(-1)^kk\frac{(-\log(1-x))^k}{k! } &=& \sum_{k=1}^\infty(-1)^k\frac{(-\log(1-x))^k}{(k-1)!} \\ &=& (1-x)\log(1-x) \\ &=& -x+\sum_{n=2}^\infty\frac{x^n}{n(n-1)} \\ &=& -x+\sum_{n=2}(n-2)!\frac{x^n}{n!}\;, \end{eqnarray} $$

y, a continuación, teniendo en cuenta el factor de $(-1)^n$ a partir de la paridad se obtiene el resultado deseado para $n\ge2$.

P. S.: me acabo de dar cuenta que el factor de $(-1)^n$ podría haber sido tratado con un poco más de elegancia a través de su inclusión desde el inicio y escribir $1+x$ en todas partes en lugar de $1-x$.

Añadido: Brian más fácil la prueba sin generar funciones me pregunto si también hay una forma más fácil la prueba por inducción. Hay: Considerar el ciclo de las estructuras de todas las permutaciones de $[n]$, y agregar $n+1$ a cada uno de ellos de todas las maneras posibles. Para cada ciclo de estructura, no se $n$ formas de agregar $n+1$ a uno de los ciclos y de las $1$ manera de agregarlo como un ciclo de su propio.

Si queremos añadir un ciclo de su propio, la paridad es invariable. Puesto que hay el mismo número de permutaciones de ambas paridades, el nuevo ciclo no contribuye al resultado; los otros ciclos de contribuir con el mismo exceso como hicieron para $n$, es decir, $(-1)^n(n-2)!$ por la hipótesis de inducción.

Por otro lado, si añadimos $n+1$ a uno de los ciclos, la paridad de los cambios, mientras que el número de ciclos de estancias de la misma. Desde allí se $n$ maneras de hacer esto para cada ciclo, esto produce un aporte de $-n(-1)^n(n-2)!$. El total es, por tanto,$(1-n)(-1)^n(n-2)!=(-1)^{n+1}((n+1)-2)!$.

Answer 3

Aquí es una solución que tiene la ventaja de la brevedad. Empezar por la observación de que el signo de una permutación $\pi$ está dado por $$\sigma(\pi) = \prod_{c\in\pi} (-1)^{|c|-1}$ $ , donde el producto es durante todos los ciclos de $c$ $\pi.$

Recordemos que el no marcado de las especies de permutaciones por el número de ciclos está dada por $$\mathfrak{P}(\mathfrak{C}(\mathcal{Z})).$$

Si queremos incluir los signos de estas permutaciones necesitamos marcar ciclos con una variable $\mathcal{U}$ cuyo exponente indica el longitud de ciclo de menos uno. Esto le da a las especies modificadas

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

También queremos que el conteo de ciclo así que nos marca a todos los ciclos de la variable $\mathcal{V},$ llegando finalmente a la especie $$\mathfrak{P}(\mathcal{V}\mathfrak{C}_{=1}(\mathcal{Z}) + \mathcal{V}\mathcal{U}\mathfrak{C}_{=2}(\mathcal{Z}) + \mathcal{V}\mathcal{U}^2\mathfrak{C}_{=3}(\mathcal{Z}) + \mathcal{V}\mathcal{U}^3\mathfrak{C}_{=4}(\mathcal{Z}) + \cdots.)$$

El cambio a la generación de funciones se obtiene la generación de la función $G(z, u, v)$ donde $$G(z, u, v) = \exp\left( vz + vu\frac{z^2}{2} + vu^2\frac{z^3}{3} + vu^3\frac{z^4}{4} + vu^4\frac{z^5}{5} + \cdots \right).$$ Este es $$G(z, u, v) = \exp \left(\frac{v}{u}\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) \right)$$ que finalmente da $$G(z, u, v) = \exp \left( \frac{v}{u} \log \frac{1}{1-uz} \right).$$ Ahora para obtener el total del número de ciclo diferenciar por $v$ y establezca $v=1$ para obtener $$H(z, u) = \left.\frac{d}{dv} G(z, u, v)\right|_{v=1} = \left.\exp \left( \frac{v}{u} \log \frac{1}{1-uz} \right) \left( \frac{1}{u} \log \frac{1}{1-uz} \right)\right|_{v=1} \\ = \exp \left( \frac{1}{u} \log \frac{1}{1-uz} \right) \left( \frac{1}{u} \log \frac{1}{1-uz} \right).$$ Observar que $$\frac{1}{2} H(z, 1) + \frac{1}{2} H(z, -1)$$ da la contribución de, incluso, permutaciones y $$\frac{1}{2} H(z, 1) - \frac{1}{2} H(z, -1)$$ desde impar, de manera que $$H(z, -1)$$ de los rendimientos de la diferencia que queremos calcular. Establecimiento $u=-1$ obtenemos $$H(z -1) = \exp \left( - \log \frac{1}{1+z} \right) \left( - \log \frac{1}{1+z} \right) \\=\left( -\log \frac{1}{1+z} \right) \exp\left(\log(1+z)\right) = -(1+z)\log\frac{1}{1+z}.$$

A la conclusión se sigue para extraer los coeficientes de este exponencial la generación de la función, y obtenemos $$n! [z^n] H(z, -1) = - n! [z^n] (1+z)\log\frac{1}{1+z} = - n! \left(\frac{(-1)^n}{n} + \frac{(-1)^{n-1}}{n-1}\right) \\= - (-1)^n \times n! \times \left(\frac{1}{n}-\frac{1}{n-1}\right) = (-1)^{n+1} \times n! \times \frac{-1}{n(n-1)} \\= (-1)^n \times (n-2)!.$$

Buena página que tengo que decir.

Nota importante. Me di cuenta de que el de arriba es un duplicado. He resuelto el mismo problema un poco menos que hace un año utilizando el mismo método y el enlace se puede encontrar bajo "vinculados" en la barra lateral derecha.