particiones matemática discreta

¿Cu´antas relaciones de equivalencia distintas
pueden definirse sobre un conjunto?
Antonio M. Oller
Sabido es por todo el mundo que dar una relaci´on de equivalencia sobre
un conjunto esequivalente a dar una partici´on de dicho conjunto, donde cada subconjunto que forma parte de dicha partici´on es justamente una clase
de equivalencia. Esto ocurre b´asicamente por ser dichas clases deequivalencia
disjuntas y cubrir todo el conjunto. La demostraci´on es elemental y puede intantarse como ejercicio o bien consultarse en cualquier libro que hable de relaciones
sobre conjuntos.
As´ı puesnosotros nos centraremos en buscar el n´
umero de particiones que
se pueden efectuar en un conjunto finito. Si el cardinal de nuestro conjunto
es n, denotaremos por Pn al n´
umero de dichasparticiones. Convenimos, por
comodidad que P0 = 1.
Fijamos x0 un elemento cualquiera del conjunto considerado, que tiene cardinal n. Dada una partici´on del conjunto, x0 pertenece a uno y s´olo uno delos
subconjuntos que forman la partici´on. Para contarlas todas nos fijaremos en el
tama˜
no del subconjunto al que pertenece x0 .
Puede ocurrir, en primer lugar, que el subconjunto al que pertenecex0 sea
de tama˜
no n; es decir, que sea el total. En este caso la partici´on est´a formada
u
´nicamente por el conunto total y s´olo hay una. Por comodidad recordamos que
1=

n−1
P0
n−1En segundo lugar, x0 puede pertenecer a un subconjunto de n-1 elementos. En esta situaci´on la partici´on est´a formada s´olo por el subconjunto al que
pertenece x0 y por un subconjunto unipuntal.Adem´as para contar cu´antas de
estas particiones hay, basta con contar el n´
umero de subconjuntos de n-1 elementos a los que pertenece x0 y este es trivialmente n−1
n−2 que por comodidad
ponemos(pues P1 = 1) como:
n−1
P1
n−2
Ahora, si x0 pertenece a un subconjunto de tama˜
no k, la partici´on estar´a formada por el subconjunto alque pertenece x0 y otros subconjuntos que forman
una...