¿Podemos contar bien a impar e incluso a derangos sin tomar un determinante?

Question

No es difícil ver que $$\det \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}$$ es igual a

#(derivaciones pares en 3 elementos) - #(derivaciones Impares en 3 elementos)

y de forma similar para los más grandes n . No es difícil calcular este determinante por varios métodos, y junto con la expresión conocida para el número total de derivaciones en n esto da lugar a expresiones explícitas para el número de Impares y derivaciones pares en n elementos.

Pregunta: ¿Existe alguna forma agradable y fundamentalmente diferente de llegar a las cifras de impar an derangements?

Mi motivación es que esto proporcionaría un método alternativo para calcular el determinante. Ver:

La matriz con ceros en la diagonal y unos en otros lugares es invertible

que es la motivación original, repasa algunas formas sencillas de calcular el determinante, e incluye una explicación completa de la identidad que afirmo arriba.

Answer 1

¿Has pensado en utilizar la función generadora de índices de ciclos? Se define como $$ Z(x_1,\cdots,x_n,\cdots)=\sum_{w\in S_n} \prod_{i=1}^{\infty}x_i^{\#\text{cycles of } w \text{ of length } i}$$

Ahora bien, se sabe (por ejemplo, por el teorema fundamental de las funciones generadoras exponenciales (egf) como se describe aquí ) que $$\sum_{n=0}^{\infty} Z(x_1,\cdots,x_n,\cdots)\frac{t^n}{n!}=\operatorname{exp}(\frac{tx_1}{1}+\frac{t^2x_2}{2}+\cdots)$$

Esta fórmula es especialmente útil para enumerar clases de permutaciones que pueden ser caracterizadas en términos de su estructura de ciclo. En este caso, por ejemplo, al establecer $x_1=0$ y $x_i=1$ enumeraría todas las permutaciones sin ciclo de longitud uno, es decir, sin puntos fijos, es decir, todas las derivaciones. Si queremos tener en cuenta el signo, basta con poner $x_i=(-)^{i-1}$ ya que un ciclo de longitud $i$ puede escribirse como un producto de $i-1$ transposiciones.

Por lo tanto, la función generadora exponencial para las derangemias pares - Impares es $$\sum Z_n(0,-1,1,-1,1,\cdots)\frac{t^n}{n!}=\operatorname{exp}(-\frac{-t^2}{2}+\frac{t^3}{3}+\frac{-t^4}{4}+\cdots)$$

El lado derecho se escribe entonces como $$\operatorname{exp}(-t+\operatorname{log}(1+t))=\frac{1+t}{e^t}$$ y extraer el coeficiente de $t^n$ de eso nos da exactamente $$\#\text{even}-\text{odd derrangements}= (-1)^{n-1}(n-1)$$

Answer 2

Demasiado largo para un comentario (he votado la primera respuesta). Me gustaría señalar que no necesitamos los índices de los ciclos del grupo simétrico aquí ya que estamos trabajando en un universo etiquetado donde sólo cuenta el orden de el grupo cuenta en lugar de la estructura de ciclos de sus elementos .

Obtenemos la siguiente ecuación de especie para las derivaciones con una variable que marca la suma de las longitudes de los ciclos menos uno, dando el signo. $$\mathfrak{P}(\mathcal{U}\mathfrak{C}_{=2}(\mathcal{Z}) + \mathcal{U}^2\mathfrak{C}_{=3}(\mathcal{Z}) + \mathcal{U}^3\mathfrak{C}_{=4}(\mathcal{Z}) + \mathcal{U}^4\mathfrak{C}_{=5}(\mathcal{Z}) +\cdots).$$

Esto da inmediatamente la función generadora $$G(z,u) =\exp\left(\sum_{q\ge 2} u^{q-1} \frac{z^q}{q}\right) = \exp\left(\frac{1}{u}\sum_{q\ge 2} u^{q} \frac{z^q}{q}\right) = \exp\left(-z +\frac{1}{u}\sum_{q\ge 1} u^{q} \frac{z^q}{q}\right) \\ = \exp\left(-z +\frac{1}{u}\log\frac{1}{1-uz}\right).$$

Ahora las derivaciones pares tienen función generadora $$\frac{1}{2} (G(z,1)+G(z,-1))$$ y los de impar $$\frac{1}{2} (G(z,1)-G(z,-1))$$ siendo la diferencia $$G(z,-1)$$ que es $$\exp\left(-z -\log\frac{1}{1+z}\right) = (1+z)\exp(-z).$$

Extrayendo los coeficientes tenemos $$n! [z^n] G(z, -1) = n! \frac{(-1)^n}{n!} + n! \frac{(-1)^{n-1}}{(n-1)!} \\= (-1)^n + (-1)^{n-1} n = (-1)^{n-1} (n-1).$$

Answer 3

Daniel McLaury indicó en su comentario que es sobre todo interesante para las pruebas biyectivas. Por esta razón he decidido publicar en esta respuesta las dos referencias que he mencionado en mis comentarios anteriores. Creo que la respuesta que recoge las referencias para las pruebas combinatorias sobre este hecho puede ser útil para otros usuarios también. He hecho esta respuesta CW, siéntete libre de añadir más referencias

Referencias

Pruebas biyectivas

• Robin Chapman: Una involución sobre las derivaciones , doi: 10.1016/S0012-365X(00)00310-1 .
  Resumen: "Damos una prueba biyectiva de que el número de pares e impar derangos en $S_n$ difiere en $n-1$ ."
  Este documento también es citado en la 2ª edición de Bona: Combinatoria de Permutación . Por lo tanto, vale la pena consultar estas dos fuentes.
• " Recuento de las probabilidades de un desquiciamiento uniforme de Benjamin, Bennett y Newberger ( Revista de matemáticas 78(5) 2005, pp. 387-390), jstor .
  Este documento fue mencionado en la respuesta de Mike Spivey aquí: Determinante de una matriz circulante específica, $A_n$ .

Pruebas con funciones generadoras

• Ejemplo 11.13 en Fundamentos de Combinatoria con Aplicaciones por Edward A. Bender y S. Gill Williamson. El libro está disponible en sitio web del autor .

Answer 4

Tal vez no sea esto lo que buscas, pero podemos simplificar el cálculo del determinante a un $1\times1$ determinante, que es lo más parecido a un no-determinante.

En esta respuesta se demuestra que $$ \det(\lambda I_n-AB)=\lambda^{n-m}\det(\lambda I_m-BA) $$ Utilizando $\lambda=1$ , $m=1$ , $A=\left.\begin{bmatrix}1\\1\\1\\\vdots\\1\end{bmatrix}\right\}$${\scriptsize n\text{ tall}}$, and $B=\underbrace{\begin{bmatrix}1&1&1&\cdots&1\end{bmatrix}} El texto de la ley es el mismo que el de la ley. $n$ ancho}}$,
obtenemos $$ (-1)^n\det\underbrace{\begin{bmatrix} 0&1&1&\cdots&1\\ 1&0&1&\cdots&1\\ 1&1&0&\cdots&1\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&1&1&\cdots&0 \end{bmatrix}}_{n\times n} =\det(I_n-AB)=\det\underbrace{(1-BA)}_{1\times1}=1-n $$ Por lo tanto, $$ \det\underbrace{\begin{bmatrix} 0&1&1&\cdots&1\\ 1&0&1&\cdots&1\\ 1&1&0&\cdots&1\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&1&1&\cdots&0 \end{bmatrix}}_{n\times n} =(-1)^{n-1}(n-1) $$