Hoy hemos recordado la definición del conjunto de las permutaciones $S_n$, donde un elemento será de la forma:
$$\displaystyle \left(\begin{array}{cccccccc}1 & 2 & 3 & 4 & 5 \cdots & n\\ \sigma_1 & \sigma_2 & \sigma_3 & \sigma_4 & \sigma_5 \cdots & \sigma_n \end{array}\right) .$$
Siendo $\sigma_i\in I=\{1,2,3,4,…,n\}$ y de modo que $\sigma_i\neq \sigma_j\forall i\neq j$.
Hemos visto que $S_n$ con la operación composición de permutaciones, $\circ$, le confiere una estructura de grupo; $(S_n,\circ)$ es un grupo.
Definimos un desarreglo como una permutación $\sigma\in S_n$ talque $\sigma_i\neq i\forall i\in I$. El propósito de la clase de hoy ha sido contar el número de desarreglos que podemos encontrar en el conjunto $S_n$.
Para vuestra ayuda consultar Derangement.
Terminamos los contenidos de la Teoría Combinatoria con la inclusión del estudios de las particiones.
Una partición del conjunto A es una familia P de subconjuntos no vacíos de A, disjuntos dos a dos, cuya unión es A. Es decir, $P= \{A_i: i\in I\}$, donde se cumple:
- Para cada $i\in I, A_i\subseteq A y A_i\neq\varnothing $
- Para cada par $i\neq j$, $A_i\cap A_j = \varnothing $
- $\cup_{i\in I} A_i = A$
El número de particiones posibles para un conjunto finito sólo depende de su cardinal $n$, y se llama el número de Bell, $B_n$. Los primeros números de Bell son B0 = 1, B1 = 1, B2 = 2, B3 = 5, B4 = 15, B5 = 52, B6 = 203, …
Los números de Bell cumplen una relación derecurrencia muy interesante:
$$B_n=\sum_{k=0}^{n-1}B_k\binom{n-1}{k}$$
Un caso particular de contar particones son los números de Stirling de segunda especie:
$$S(n,k)=\frac{1}{k!}\sum_{i=0}^k(-1)^i\binom{k}{i}(k-i)^n.$$
Este resultado nos da pie a contar las aplicaciones suprayecivas entre dos conjuntos finitos.
Teorema: Sean $A$ y $B$ dos conjuntos finitos de cardinal $n$ y $m$ respectivamente. El número de aplicaciones suprayectivas de $A$ en $B$ es de $$m!S(n,m).$$
| Ejercicio: Calcular el número de desarreglos de $S_5$. |