Desarreglos

Junio 16, 2008

Una pregunta que tengo en la cabeza desde hace un tiempito (motivada por un ejercicio de la práctica de Complementos ara Físicos):

Un desarreglo es una permutación \sigma\in S_n que no deja ningun elemento de \{1,\dots,n\} fijo. No es difícil mostrar que si D_n\subset S_n es el conjunto de desarreglos, entonces

\frac{|D_n|}{|S_n|} = 1-\frac1{1!}+\frac1{2!}-\frac1{3!}+\cdots+(-1)^n\frac1{n!}.

Por otro lado, evaluando el determinante

\left| \begin{array}{cccccc} 0 & 1 & 1 & \cdots & 1 & 1 \\ 1 & 0 & 1 & \cdots & 1 & 1 \\ 1 & 1 & 0 & \cdots & 1 & 1 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 1 & 1 & 1 & \cdots & 0 & 1 \\ 1 & 1 & 1 & \cdots & 1 & 0 \end{array} \right|

de dos maneras distintas, uno puede ver que la cantidad de desarreglos pares e impares son, respectivamente,

|D_n^+| = \tfrac12\bigl(|D_n|-(-1)^n(n-1)\bigr)

y

|D_n^-| = \tfrac12\bigl(|D_n|+(-1)^n(n-1))\bigr).

Ahora bien… Si F es un cuerpo con q<\infty elementos, V es un F‍-‍espacio vectorial de dimensión n y D(V)\subset GL(V) es el conjunto de automorfismos de V que no tienen a 1 como autovalor, entonces

\frac{|D(V)|}{|GL(V)|} = 1-\frac1{(1)_q!}+\frac1{(2)_q!}-\frac1{(3)_q!}+\cdots+(-1)^{n}\frac1{(n)_q!},

donde (k)_q! = (n)_q(n-1)_q\cdots(1)_q y (k)_q=\frac{1-q^k}{1-q}. Notar la bonita analogía con la fórmula anterior para |D_n|/|S_n|…

¿A alguien se le ocurre una definición conveniente y natural de «elementos pares» D^+(V)\subset D(V) y de «elementos impares» D^-(V)\subset D(V) de manera que haya fórmulas similares a las dadas arriba para D^+_n y D^-_n? Hay puntos extra si la demostración de esas fórmulas es también similar a la indicada arriba!

(Hay más detalles (y pruebas) en estas notas)

EDIT: Como Pablo observó diligentemente, ambas fórmulas estaban mal escritas…

Deja un Comentario » | Uncategorized | Etiquetado: | Permalink
Escrito por Grin Without a Cat

Saber dónde estás parado

Noviembre 7, 2007

Queremos pintar el piso de blanco y negro de forma que con sólo mirar para abajo, uno pueda saber dónde está:

dados m,n \in \mathbb N con n < m y dada A \in M_m(\mathbb Z_2)
sea
p:\mathbb Z_m \times \mathbb Z_m \longrightarrow M_n(\mathbb Z_2) dada por

(x,y)\longmapsto (A_{i+x,j+y})_{i,j}
El problema consiste en (dado n) encontrar el máximo m y una A, talque p sea inyectiva.

Deja un Comentario » | Uncategorized | Etiquetado: , | Permalink
Escrito por julianhaddad

El grafo tenía un papelito que decía “pintame”

Octubre 5, 2007

Cuando decimos “pintar un grafo” nos referimos a asignar a cada vértice un color, de forma que dos vértices unidos por una arista tengan colores distintos.

Demostrar que un grafo puede pintarse con k colores distintos si y sólo si cada subgrafo finito puede pintarse con k colores distintos.

1 comentario | Uncategorized | Etiquetado: , | Permalink
Escrito por Marlowe, PI

Si su nombre empieza con “C” y termina con “arlos” no postee aqui

Julio 26, 2007

Se tiene un conjunto de 2n+k elementos y se quiere pintar cada uno de sus subconjuntos de n elementos de forma que dos conjuntos del mismo color no sean disjuntos. Probar que esto siempre se puede hacer con k+2 colores y no con k+1.

Deja un Comentario » | Uncategorized | Etiquetado: | Permalink
Escrito por maxicampo