Diario de clases

Partición

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\)

Ejercicio: En una asignatura de programación hay 8 estudiantes: \(\mathcal{A}=\{a,b,c,d,e,f,g,h\}\). El profesor quiere dividirlos en 3 equipos de trabajo, de manera que:

• un equipo tenga 4 estudiantes,
• y los otros dos equipos tengan 2 estudiantes cada uno.

Los equipos no tienen nombre (es decir, no importa el orden de los grupos).

Solución:

Ejercicio: Un sistema distribuido debe repartir 10 procesos distintos entre varios servidores.
El conjunto de procesos es:
\[
P={p_1,p_2,\dots,p_{10}}
\]
Se desea realizar una partición de (P) en:

• 2 subconjuntos de tamaño 3,
• y 1 subconjunto de tamaño 4.

Los subconjuntos representan servidores diferentes.

1. Consideremos que los servidores indistinguibles, ¿cuántas particiones distintas existen?
2. ¿Qué cambia si ahora los servidores están etiquetados como: Servidor A, Servidor B y Servidor C?

Solución:

Parecido con las permutaciones con repetición

Observar que el ejercicio de los 8 estudiantes:
\[
|\{A_1,A_2,A_3\}|,\qquad |A|=8,\qquad \{|A_1|,|A_2|,|A_3|\}={4,2,2}
\]

El número de particiones se podría contar como
\[
\frac{8!}{4!2!2!}\cdot \frac{1}{2!}=210
\]

El factor \(2!\) del denominador aparece porque hay dos bloques del mismo tamaño 2.

Si nos fijamos la primera parte es similar a las permutaciones con repetición de 3 objetos donde un se repite 4 veces, y los otros dos 2 veces cada uno.

Aunque las fórmulas utilizadas en las particiones de conjuntos y en las permutaciones con repetición son algebraicamente muy parecidas, ambos problemas responden a ideas combinatorias completamente distintas. En las permutaciones con repetición se cuentan ordenaciones lineales de objetos donde algunos elementos son indistinguibles; es decir, el orden importa. Por ejemplo, al ordenar las letras de una palabra, dos disposiciones distintas representan resultados diferentes. En cambio, en una partición de un conjunto no se ordenan los elementos, sino que se divide el conjunto en subconjuntos disjuntos cuya unión es el conjunto original. Tampoco importa el orden de los bloques obtenidos. La similitud entre las fórmulas aparece porque, en ambos contextos, se utilizan coeficientes multinomiales para corregir sobreconteos producidos por indistinguibilidades. Sin embargo, en las particiones aparece además un nuevo factor corrector asociado a los bloques que tienen el mismo tamaño, ya que intercambiar dichos bloques no produce una nueva partición. Así, si un conjunto de \(n\) elementos se particiona en bloques de tamaños

\[
\lambda_1,\lambda_2,\dots,\lambda_k,
\]

donde algunos tamaños pueden repetirse, entonces el número de particiones distintas viene dado por la siguiente proposición.

Proposición: El número de particiones de un conjunto de \(n\) elementos en bloques de tamaños \(\lambda_1,\lambda_2,\dots,\lambda_k,\) es
\[\frac{n!}
{\lambda_1!\lambda_2!\cdots\lambda_k!}
\cdot
\frac{1}{m_1!m_2!\cdots m_n!}
\]
donde \(m_i\) representa el número de bloques de tamaño \(i\) (\(m_i=|j:\lambda_j=i|\)).

En la proposición, \(m_i\) cuenta cuántas veces aparece el tamaño \(i\) entre \(\lambda_1,\lambda_2,\dots,\lambda_k\).

Por ejemplo, si los tamaños son: 4, 4, 2 y 2, entonces:

\[
m_2=2,\qquad m_4=2
\]

y los demás \(m_i\) valen \(0\) que, siendo \(0!=1\), no afectan al producto.

Ejercicio: Una empresa dispone de un conjunto de 12 programadores:
\(P=\{p_1,p_2,\dots,p_{12}\}\). Se desea dividirlos en equipos de trabajo de la siguiente forma: 4, 4, 2 y 2; es decir, dos equipos de 4 programadores y dos equipos de 2 programadores. Los equipos no tienen nombre, por lo que el orden de los equipos no importa. ¿Cuántas particiones distintas pueden formarse?

Solución:

Número de particiones de un conjunto finito

El número de particiones posibles para un conjunto finito solo depende de su cardinal \(n\), y se llama el número de Bell, \(B_n\). Los primeros números de Bell son B₀ = 1, B₁ = 1, B₂ = 2, B₃ = 5, B₄ = 15, B₅ = 52, B₆ = 203, …

Ejercicio: Un proyecto informático está formado por 5 módulos distintos \(M=\{m_1,m_2,m_3,m_4,m_5\}\). El jefe de proyecto quiere agrupar estos módulos en paquetes de trabajo. No se fija cuántos paquetes habrá: puede haber 1 paquete, 2 paquetes, 3 paquetes, 4 paquetes o 5 paquetes. Cada módulo debe estar en exactamente un paquete, y los paquetes no tienen nombre. ¿Cuántas formas distintas hay de particionar el conjunto \(M\)?

Solución:

Los números de Bell cumplen una relación de recurrencia:

Proposición:\[B_n=\sum_{k=0}^{n-1}B_k\binom{n-1}{k}\]

Ejercicio: Determinar \(B_5\).

Solución:

Ejercicio: Una aplicación está formada por 6 microservicios distintos:

\[
M=\{m_1,m_2,m_3,m_4,m_5,m_6\}
\]

El equipo de arquitectura quiere agruparlos en módulos de despliegue. No se fija de antemano cuántos módulos habrá, pero se impone la siguiente condición:

\[
m_1 \text{ y } m_2 \text{ deben estar en el mismo módulo.}
\]

Cada microservicio debe pertenecer exactamente a un módulo, y los módulos no tienen nombre. ¿Cuántas particiones distintas cumplen esta condición?

Solución:

Números de Stirling de segunda especie

Un caso particular de contar particiones 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.\]

Los números de Stirling de segunda especie \(S(n,k)\) cuentan el número de maneras que existen de hacer una partición de un conjunto de \(n\) elementos en \(k\) subconjuntos.

Observar que los números de Stirling de segunda especie cuentan particiones de un conjunto de \(n\) elementos en \(k\) subconjuntos no vacíos, sin fijar sus tamaños; sin embargo, en los ejercicios de particiones sí fijamos los tamaños de los bloques, por ejemplo 4,2,2 o 4,3,3. Por tanto, no usamos directamente un único S(n,k), sino una versión refinada: particiones con tamaños prescritos.

Ejercicio: En una clase hay 8 estudiantes: \(A=\{a,b,c,d,e,f,g,h\}\), queremos dividirlos en 3 equipos no vacíos, sin importar el orden de los equipos. ¿Cuántas particiones distintas existen?

Solución:

Procedimiento recursivo

Otra notación para los números de Stirling de segunda especie es: \[\left\{{\begin{matrix}n\\k\end{matrix}}\right\}:=S(n,k),\]

que nos permite la siguiente relación de recurrencia

\[ \left\{{\begin{matrix}n\\k\end{matrix}}\right\}=\left\{{\begin{matrix}n-1\\k-1\end{matrix}}\right\}+k\left\{{\begin{matrix}n-1\\k\end{matrix}}\right\}\]

con \[\left\{{\begin{matrix}0\\0\end{matrix}}\right\}=1,\quad \left\{{\begin{matrix}n\\0\end{matrix}}\right\}=0,\quad \left\{{\begin{matrix}n\\1\end{matrix}}\right\}=\left\{{\begin{matrix}n\\n\end{matrix}}\right\}=1,\quad {\mbox{ y }}\quad \left\{{\begin{matrix}n\\k\end{matrix}}\right\}=0,\ \forall k>n.\]

Ejercicio: ¿Cuál es el valor de \(\left\{{\begin{matrix}10\\2\end{matrix}}\right\}\)?

Solución:

Ejercicio: ¿Cuál es el valor de \(\left\{{\begin{matrix}4\\2\end{matrix}}\right\}+\left\{{\begin{matrix}5\\2\end{matrix}}\right\}\)?

Solución:

Este proceso nos permite dar una tabla de valores para los Números de Stirling de segunda especie:

Ejercicio: Construir un algoritmo con máxima que nos devuelva \(\left\{{\begin{matrix}n\\k\end{matrix}}\right\}\).

Proposición:\[B_{n}=\sum _{k=1}^{n}S(n,k).\]

Ejercicio: Determinar \(B_6\)

Solución:

Otra aplicación interesante es el que nos da pie a contar las aplicaciones suprayectivas 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).\]

El problema de encuentros

En combinatoria, el problema de encuentros busca determinar cuántas permutaciones de un conjunto de $n$ elementos tienen exactamente $k$ «encuentros» o puntos fijos.

Un encuentro ocurre cuando un elemento aparece en su posición original. Por ejemplo, si tienes 3 sobres dirigidos a 3 personas y los metes al azar, un «encuentro» sucede si el sobre de «Ana» termina en las manos de «Ana».

Para calcular el número de formas en que exactamente $k$ elementos de un conjunto de $n$ están en su lugar original, utilizamos la notación $T(n,k)$.

Con los valores iniciales (casos base):

• \(T(0,0) = 1 \).
• \(T(1,0) = 0 \).

Para $ n \geq 2 $:
$$ T(n, 0) = (n-1) \left( T(n-1, 0) + T(n-2, 0) \right) $$

Para $ n \geq 1 $ y $ k \geq 1 $:$$ T(n, k) = \frac{n}{k} T(n-1, k-1) $$

Solución:

Números binomiales Definición: Llamaremos número binomial, o coeficiente binomial, a la expresión \(\binom{n}{k}\), dada por la fórmula: \[{\displaystyle {n \choose k}={\frac {n!}{k!(n-k)!}}}\] Teorema (Fórmula de Stiefel): Sea \({n\choose 0}={n\choose n}=1,\ \forall n\in\mathbb{Z}^+,\)…

Grafos Eulerianos Un camino euleriano es un camino que pasa por cada arista una y solo una vez. Un ciclo o circuito euleriano es un camino cerrado que recorre cada arista exactamente…

1. Definición y Caracterización Un árbol es un grafo simple G = (V, E) que cumple cualquiera de las siguientes condiciones equivalentes: Conectividad y Ciclos: Es un grafo conexo y no contiene…

Subgrafos y Operaciones Elementales Un grafo $G’ = (V’, E’)$ es un subgrafo de $G = (V, E)$ si $V’ \subseteq V$ y $E’ \subseteq E$. Subgrafo Inducido: Es aquel que, al…