Esta pregunta se puede abordar de variadas maneras, sin embargo te dejamos la resolución más completa en nuestra opinión.
Solución:
Este tipo de argumento de conteo puede ser bastante complicado, o al menos poco elegante, especialmente para conjuntos grandes. Aquí hay un enfoque:
Hay una biyección entre las relaciones de equivalencia en $S$ y el número de particiones en ese conjunto. Ya que $1,2,3,4$ tiene 4 elementos, solo falta saber cuantas particiones hay de 4.
Hay cinco particiones enteras de 4:
- $4$,
- $3+1$,
- $2+2$,
- $2+1+1$,
- $1+1+1+1$
Entonces, solo necesitamos calcular la cantidad de formas de colocar los cuatro elementos de nuestro conjunto en estos contenedores de tamaño.
4
Solo hay una forma de poner cuatro elementos en un contenedor de tamaño 4. Esto representa la situación en la que solo hay una clase de equivalencia (que contiene todo), de modo que la relación de equivalencia es la relación total: todo está relacionado con todo.
3+1
Hay cuatro formas de asignar los cuatro elementos en un contenedor de tamaño 3 y otro de tamaño 1. Las relaciones de equivalencia correspondientes son aquellas en las que un elemento se relaciona solo consigo mismo y los demás se relacionan entre sí. Hay claramente 4 formas de elegir ese elemento distinguido.
2+2
Hay $pmatriz4\2/2=6/2=3$ formas. Las relaciones de equivalencia que estamos viendo aquí son aquellas en las que dos de los elementos están relacionados entre sí y los otros dos están relacionados entre sí. Entonces, comience eligiendo un elemento, digamos 1. Luego, hay tres cosas con las que 1 podría estar relacionado. Una vez elegido ese elemento, la relación de equivalencia queda completamente determinada.
2+1+1
Hay $pmatriz4\2=6$ formas.
1+1+1+1
Solo de una manera. Esta es la relación de equivalencia de identidad.
Así, hay, en total 1+4+3+6+1=15 particiones en $1,2,3,4$y por lo tanto 15 relaciones de equivalencia.
Número total de relaciones de equivalencia en $1,2,3,4$=Número de particiones del conjunto $1,2,3,4$ en clases de equivalencia (subconjuntos no vacíos)
Número de particiones posibles de un conjunto $A$=Número de Bell, $B(m)$=$sum_n=1^m S(m,n)$,
donde $S(m,n)=frac1n!sum_k=0^n(-1)^k. ^nC_k(nk)^m$ son los números de Stirling de segunda clase.
$$ S(4,1)=frac11!sum_k=0^1(-1)^k. ^1C_k(1-k)^4=^1C_0.1^4-^1C_1.0=1\S(4,2)= frac12!sum_k=0^2(-1)^k. ^2C_k(2-k)^4=frac^2C_0.2^4-^2C_1.1^4+^2C_ 2.02=frac142=7\ S(4,3)=frac13!sum_k=0^3( -1)^k. ^3C_k(3-k)^4=frac^3C_0.3^4-^3C_1.2^4+^3C_2.1^4-^3 C_3.06=frac81-3(16)+36=frac366=6\ S(4,4)=1 $$
Número de particiones posibles del conjunto $1,2,3,4$, es decir, número de relaciones de equivalencia del conjunto, $$ B(4)=sum_n=1^4S(4, n)=S(4,1)+S(4,2)+S(4,3)+S(4,4)=1+7+6+1=15 $$
Aquí hay otro método: cuente las relaciones equivalentes por el número de clases de equivalencia y repita el tamaño del conjunto (comenzamos con el tamaño del conjunto 1 e ignoramos la relación de equivalencia del conjunto vacío).
Denotemos con $a_n,k$ el número de clases de equivalencia de un conjunto de elementos de $n$ que tienen clases de equivalencia de $k$. Para evitar casos especiales en las fórmulas, supongamos $a_0,k=a_n,0=0$.
Un conjunto de un elemento obviamente tiene solo una relación de equivalencia, con una clase de equivalencia. Es decir, $a_1,1=1$.
Las relaciones de equivalencia con $k$ clases de equivalencia de un conjunto con $n$ elementos se obtienen combinando los siguientes dos conjuntos disjuntos:
-
Todas las relaciones de equivalencia obtenidas sumando el elemento $n$-ésimo como clase de equivalencia separada a las relaciones con clases de equivalencia $k-1$ en los elementos $n-1$ restantes. Por ejemplo, de ${1,2,3$ obtienes $\1,2,3,4\$. Obviamente obtenemos una relación $(n,k)$ de cada relación $(n-1,k-1)$.
-
Todas las relaciones de equivalencia adjuntando el elemento $n$-ésimo a una de las clases de equivalencia de una relación con clases de equivalencia $k$ en los elementos $n-1$ restantes. Por ejemplo, de $\1,2,,3\$ obtienes $\1,4,2,3 \$, $\1,2,4,3\$ y $\1,2,3 ,4\$. Obviamente obtenemos relaciones $k$ $(n,k)$ de cada relación $/n-1,k)$
Así $a_n,k = a_n-1,k-1 + k a_n-1,k$.
Así que hagamos la recursividad:
-
$n=2$:
-
$a_2,1 = a_1,0 + 1 a_1,1 = 1$. De hecho, podemos ver fácilmente que $a_n,1$ siempre es $1$ para todos los $n$. Por lo tanto, de ahora en adelante se omitirá este cálculo.
-
$a_2,2 = a_1,1 + 2 a_1,2 = 1$. De nuevo, podemos ver fácilmente que $a_n,n$ siempre es $1$. Por lo tanto, de ahora en adelante también se omitirá este cálculo.
Entonces hay relaciones de equivalencia $1+1=2$ para $n=2$.
-
-
$n=3$:
- $a_3,2 = a_2,1 + 2 a_1,2 = 3$
Entonces hay relaciones de equivalencia $1+3+1=5$ para $n=3$.
-
$n=4$:
-
$a_4,2 = a_3,1 + 2 a_3,2 = 7$
-
$a_4,3 = a_3,2 + 3 a_3,3 = 6$
Entonces hay relaciones de equivalencia $1+7+6+1=15$ para $n=4$.
-
Esto se puede poner en un buen esquema que tiene cierta semejanza con el triángulo de Pascal:
nk 1 2 3 4 5 6
1 1 -> 1
2 1 1 -> 2
3 1 3 1 -> 5
4 1 7 6 1 -> 15
5 1 15 25 10 1 -> 52
6 1 31 90 65 15 1 -> 203
Cada número es el número de la columna multiplicado por el número de arriba más el número que queda de eso.