Número de relaciones de equivalencia posibles en un conjunto finito

Una relación de equivalencia es Reflexiva, Simétrica y Transitiva. Antes de contar el número de posibles relaciones de equivalencia en un conjunto |A|=n, veamos un ejemplo de una relación de equivalencia e identifiquemos Clases de Equivalencia en ella.

Sean A = {1, 2, 3, 4} un conjunto y R = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), ( 3, 4), (4, 3), (4, 4)} sea una relación de equivalencia sobre A. Vemos aquí que la relación total T = {(1, 1), (1, 2), (1, 3 ), (1, 4)} sobre el conjunto C1 = {1, 2} que es el subconjunto de A está presente en R, es decir subconjunto de R. Y tampoco existe tal relación total T’>=T sobre el conjunto C1 ‘>=C1 que está presente en R, es decir, subconjunto de R. Por lo tanto, encontramos una clase de equivalencia E1 = {1, 2} sobre la relación R.

De manera similar, hay otra clase de equivalencia E2 = {3, 4} sobre R. Y no hay más clases de equivalencia presentes en R. Observe aquí que E1 y E2 son conjuntos disjuntos y esto siempre es cierto porque {E1, E2} es decir, {{ 1, 2}, {3, 4}} es una de las posibles particiones del conjunto A.

Por lo tanto, la relación de equivalencia anterior R corresponde a la partición {{1, 2}, {3, 4}} del conjunto A. De manera similar, todas y cada una de las relaciones de equivalencia en A corresponden a una de las particiones de A. De hecho, este mapeo es biyectivo .

Ahora llegamos a nuestra cuestión de encontrar el número de posibles relaciones de equivalencia en un conjunto finito que es igual al número de particiones de A. Los Números de Bell cuentan lo mismo. Comenzando con B0 = B1 = 1, los primeros números de Bell son:

1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958545, 10480142147, 82864869804, 682076680657, 58332742424242424242424242424242424242424242424242424242424242424242424242424242424242424242424242424242424 ¿MUY

Aquí están las primeras cinco filas del triángulo construido:

 1
 1   2
 2   3   5
 5   7  10  15
15  20  27  37  52

Los números de Bell aparecen en los lados izquierdo y derecho del triángulo.

Ejemplo: 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 colocar 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 (42)/2=6/2=3(42)/2=6/2=3 maneras. 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 (42)=6(42)=6 maneras.
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}{1, 2, 3, 4}, y por lo tanto 15 relaciones de equivalencia.

Nota: este tipo de argumento de conteo puede ser bastante complicado, o al menos poco elegante, especialmente para conjuntos grandes. No existe una fórmula directa para hacerlo.