La cantidad de maneras de separar un conjunto en subconjuntos no vacíos

3 11 2007

El otro día (miércoles 31 de Octubre.. Halloween) tenía que encontrar cuál era la cantidad de maneras que existen para separar un conjunto en conjuntos más chicos…
por ejemplo:
el conjunto {a,b,c} se puede separar en 4 maneras:
– {a} {b} {c}
– {a,b} {c}
– {a,c} {b}
– {a} {b,c}
y no hay más.
el conjunto {a,b} sólo puede separarse como {a} {b} y no hay más.

Estaba buscando esto para sacar la cantidad de splits complejos distintos que se pueden hacer en un nodo de un árbol de decisión, a partir de un atributo con n valores posibles..
QUÉ?
Es un ramo de Inteligencia Artificial, del cual yo soy profesor auxiliar, y el profe de cátedra les preguntó eso a los alumnos en clases, y yo quise responderles… En todo caso, los splits es lo que en otros lados se les llama “particiones”… y que sean complejos significa que pueda haber más de un valor del atributo por cada camino del split.

Entonces, resulta que estuve tratando de cachar harto tiempo cómo se hacía… porque sonaba algo como razonable….
Supuestamente la cantidad de permutaciones que se puede hacer con n elementos es n!, y la cantidad de subconjuntos que se pueden hacer a partir n elementos es 2^n (2 elevado a n)…
y si hablamos de los subconjuntos de k elementos, entonces son n sobre k posibilidades….

Entonces como que sonaba a algo posible de hacer así a mano….

en un momento llegué a una fórmula….

(n^n-1)/(n-1)pero sólo servía hasta n=3.

Resulta que… la cosa era más conocida en el mundo como “maneras de particionar un conjunto”..
Que suena bien razonable.. y harto más comprensible que “La cantidad de maneras de separar un conjunto en subconjuntos no vacíos”….
y resulta que gracias a un amigo persona que andaba por ahí, llegué a que los números de Stirling de segundo tipo ( S(n,k) ) son la cantidad de formas de particionar un conjunto de n elementos en k subconjuntos no vacíos….
y PAF! yo quería eso… pero para subconjuntos de cualquier número….
y PAF de nuevo! Wikipedia me llevó a los números de Bell, que son la sumatoria de esos números de Stirling, desde 1 a n, además de cumplir varias otras propiedades raras que se pueden ver ahí en Wikipedia…

El único detalle eso sí, es que yo no quería tomar en cuenta la partición que corresponde al conjunto entero así sin dividirlo, por lo tanto, lo que yo estaba buscando era Bn – 1… pero al final era lo mismo, no?..

Así que eso… por si alguien anda buscando lo mismo…

Ya que google no me ayudó demasiado en mi búsqueda… y creo que mi inglés técnico no estuvo muy bien, puse cosas como:
“how many ways are to divide a set”
y no salió nada…
y después descubrí que debería haber puesto algo más sofisticado como:
“number of ways to divide a set”
ahí sí salen cosas relevantes….

y bueno.. y esa es mi historia de Halloween…

y el miércoles anterior fui a ver a soda stereo….

aún estoy pensando cuál miércoles fue más emocionante….

Anuncios

Acciones

Information

One response

12 03 2014
bOOby

A marear la perdiz y a multiplicar los panes

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s




A %d blogueros les gusta esto: