MAD: Desarreglos y particiones

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$.
This entry was written by admin , posted on viernes mayo 25 2018at 09:05 am , filed under Matemática Discreta . Bookmark the permalink . Post a comment below or leave a trackback: Trackback URL.

Deja un comentario

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>