Deje $g_{n}$ no. de alteraciones con $n$ elementos y $f_{n}$ el no. de permutaciones con un punto fijo. Mostrar que $|g_{n}-f_{n}|=1$

Question

Este es un problema de Loren Larson "resolución de problemas a través de problemas", 2.5.13, página 78.

Vamos $S_{n}=${$1,2,...,n$}. Una alteración de $S_{n}$ es una permutación sin puntos fijos. Deje $g_{n}$ el número de alteraciones, y $f_{n}$ el número de permutaciones de $S_{n}$ con exactamente un punto fijo. Mostrar que $|f_{n}-g_{n}|=1$

He demostrado que los $g_{n}=(n-1)(g_{n-1}+g_{n-2})$, y al analizar el número de permutaciones de $S_{3}$ e $S_{4}$ he conjeturado que $g_{2n}=f_{2n}+1$, e $g_{2n+1}=f_{2n+1}-1$, aunque no sé cómo demostrarlo. También me pareció que $f_{n+1}=(n+1)g_{n}$.

Answer 1

Deje $D_n$ el número de alteraciones en $S_n$. Obviamente el número de permutaciones con exactamente un punto fijo dado por $n D_{n-1}$, así que sólo tenemos que probar que para cada $n$, $$ A_n = D_n-nD_{n-1}\in\{-1,1\}.$$ Deje $\sigma$ ser una alteración en $S_n$ y deje $m=\sigma^{-1}(n)$. Si tenemos en cuenta: $$ \tau = \sigma\, (n m) $$ es decir, la permutación obtenemos mediante el intercambio de imágenes de $n$ e $m$, es obvio que tenemos $\tau(n)=n$. Entonces, hay dos casos: si $\tau(m)=m$, $\tau$ tiene exactamente dos puntos fijos, de lo contrario $n$ es el único punto fijo. Que lleva (ver también esta pregunta) a: $$ D_n = (n-1)\left(D_{n-1}+D_{n-2}\right) $$ que puede ser escrito como $A_n = -A_{n-1}$. Desde $A_2=1$, la demanda sigue por inducción.

Answer 2

SUGERENCIA: Deje $\pi$ ser una permutación de $S_n$ con exactamente un punto fijo. Deje $k$ ser el punto fijo; a continuación, $\pi\upharpoonright(S_n\setminus\{k\})$ es una alteración de $S_n\setminus\{k\}$. Vamos

$$s:S_n\setminus\{k\}\a S_{n-1}:\ell\mapsto\begin{cases} \ell,&\text{if }\ell<k\\ \ell-1,&\text{if }\ell>k\;; \end{casos}\etiqueta{1}$$

$s$ es un bijection, y $s\circ\big(\pi\upharpoonright(S_n\setminus\{k\})\big)\circ s^{-1}$ es una alteración de $S_{n-1}$. Por el contrario, si $\pi$ es una alteración de $S_{n-1}$, $k\in S_n$, y $s$ está definido por $(1)$,, a continuación, $s^{-1}\circ\pi\circ s$ es una permutación de $S_n$ tiene exactamente un punto fijo, $k$. Por lo tanto, $f_n=ng_{n-1}$. Si se combina esto con su recurrencia para $g_n$, usted debería ser capaz de terminar la prueba (y, de paso, demostrar su observación acerca de las par/impar subíndices), pero siéntase libre de dejar una pregunta si te quedas atascado.

Answer 3

La generación de la función de las alteraciones es $$\exp(-z) \frac{1}{1-z}.$$

Esto es debido a que las especies que aquí se $$\mathfrak{P}(\mathfrak{C}_{=2}(\mathcal{Z}) + \mathfrak{C}_{=3}(\mathcal{Z}) + \mathfrak{C}_{=4}(\mathcal{Z}) + \cdots)$$

lo que da $$\exp\left(\frac{z^2}{2}+\frac{z^3}{3} +\frac{z^4}{4}+\cdots\right).$$

Por lo tanto, tenemos el número de alteraciones $$n! [z^n] \exp(-z) \frac{1}{1-z}$$

La generación de la función de permutaciones con puntos fijos marcados es

$$\exp\left(uz - z +\log\frac{1}{1-z}\right)$$ que es $$\exp(uz-z)\frac{1}{1-z}$$

Esto es debido a que las especies que aquí se $$\mathfrak{P}(\mathcal{U}\mathfrak{C}_{=1}(\mathcal{Z}) + \mathfrak{C}_{=2}(\mathcal{Z}) + \mathfrak{C}_{=3}(\mathcal{Z}) + \mathfrak{C}_{=4}(\mathcal{Z}) + \cdots)$$

lo que da $$\exp\left(uz + \frac{z^2}{2}+\frac{z^3}{3} +\frac{z^4}{4}+\cdots\right).$$

Por lo tanto, tenemos para el número de permutaciones con un punto fijo $$n! [z^n] [u] \exp(uz-z)\frac{1}{1-z}$$ que es $$n! [z^n] z \exp(-z)\frac{1}{1-z}.$$

La diferencia es $$n! [z^n] (1-z) \exp(-z) \frac{1}{1-z} = n! [z^n] \exp(-z) = (-1)^n$$ lo que demuestra la demanda.