Desordenamientos (derangement)
Dentro de las aplicaciones del principio de inclusión-exclusión está el conteo de permutaciones con posiciones restringidas. Un caso especial de éstas son los desordenamientos, en los cuales se impone la restricción de que ningún elemento esté en su lugar original.
Recordemos que una permutación sobre $n$ elementos es una biyección $f:\{1,2,...,n\}\rightarrow\{1,2,...,n\}$. Un desordenamiento en combinatoria es una permutación en la cual ningún elemento está en su lugar. Formalmente, un desordenamiento es una biyección $f$ de un conjunto finito $S$ en sí mismo sin puntos fijos (para toda $s$ de $S, f(s)$ es diferente de $s$).
Ejemplo (Vilenkin): Si consideramos los números $1, 2, 3, 4, 5$ en su orden natural, y se toman todas las permutaciones posibles de ellos ¿en cuántas permutaciones no hay ningún número en su lugar?
Planteado en términos de desordenamientos, este problema se enunciaría así: ¿Cuántos desordenamientos de 5 elementos hay?
Sea $d(n)$ el número de desordenamientos de $n$ elementos. Vamos a aplicar el principio de inclusión-exclusión para calcular $d(n)$.
Para cada $i$ de $\{1,2,...,n\}$ sea $A_i$ el conjunto de permutaciones que fijan $i$ (es decir, $f(i)=i$). Entonces, como los desordenamientos son las permutaciones con ningún elemento en su lugar (ningún punto fijo), $d(n)=$ todas las permutaciones - las permutaciones que dejan al menos un punto fijo. Es decir, {desordenamientos de n elementos}=$S-A_1 \cup A_2 \cup \cdots \cup A_n$
De esta manera, $d(n)$ se puede calcular con el principio de inclusión-exclusión.
Es fácil darse cuenta que $ |A_i|=(n-1) ! $, que $ |A_{\{i , j\}}|=(n-2) ! $, etc. Y, en general, si los elementos que quedan fijos son los elementos de un subconjunto $I$ de $S$, entonces $|A_I|=(n-|I|) ! $ Y ya estamos listos para aplicar inclusión-exclusión:
\[d(n)= \sum_{i=0}^{n}(-1)^i C(n,i) (n-i) ! =n ! \sum_{i=0}^{n}\frac{(-1)^i}{ k ! } \]
Solución al ejemplo de Vilenkin:
Al número total de permutaciones de los números $1, 2, 3, 4, 5$, hay que quitarle las permutaciones que dejan un punto fijo (que dejan uno de los números en su lugar). Los posibles puntos fijos son 5 y, fijando uno en particular, las permutaciones correspondientes son $4! $. Por tanto a $5 ! $ hay que quitarle $C(5,1) 4! $.
Pero como entre las permutaciones que dejan un punto fijo hay permutaciones que dejan dos puntos fijos, habría que sumarle el número de permutaciones que dejan dos puntos fijos. Para elegir dos elementos (los que van a quedar fijos) hay $C(5,2)$ posibilidades y, como para cada dos elementos particulares que quedan fijos, hay $3 ! $ permutaciones, lo que hay que sumar es $C(5,2) 3! $, etc.
Entonces si son 5 elementos en $S$, el número de desordenamientos sobre 5 elementos es
\[d(5)=5 !-C(5,1)4 !+C(5,2)3 !-C(5,3)2 ! +C(5,4)1 ! -C(5,5)0 ! =\] \[120-5(24)+10(6)-5(1)-1(1)=44. \]
Es decir, en 44 permutaciones de 5 objetos ninguno de ellos está en su lugar.
Los saluda
jmd
Visiten el siguiente link para ver más sobre inclusión-exclusión [1]