Números de Stirling de segunda especie

Contar la cantidad de formas en que pueden distribuirse n elementos en k cajas es bastante simple, una vez que descubrimos el truco de pensarlo como asignarle un número de caja a cada elemento. Claramente esto nos da k^n posibles formas. Si ignoramos el “etiquetado” de las cajas, claramente esto nos deja k^n/k! formas.
[Nota 22/7/13: este análisis es incorrecto, como indica Jon abajo. El análisis correcto de este se encuentra en una nueva página.]

Este problema se hace más difícil si agregamos la restricción de que ninguna caja puede permanecer vacía y, de hecho, recuerdo haber esquivado resolver este problema en más de una ocasión (y no soy el único 😀 ). Pero en Wikipedia encontré una solución elegante y, tal vez, lo suficientemente memorable para que la recuerde en caso de encontrarme nuevamente con este problema…

Denominemos

\left\{\begin{matrix} n \\ k \end{matrix}\right\}

al número de distintas formas en las que podemos distribuir n elementos en k cajas sin dejar ninguna vacía y sin distinguir entre cajas (o sea el número de distintas particiones de \{1,2,...,n\} en k subconjuntos). Entonces podemos dividir las formas de efectuar esta distribución en dos clases: las que ponen al elemento n solo en una caja y las que no lo hacen.

Una vez situado el elemento n en una caja, las distribuciones serán equivalentes a n-1 elementos en k-1 cajas. Por lo tanto, habrá

\left\{\begin{matrix} n-1 \\ k-1 \end{matrix}\right\}

formas de efectuar la distribución dejando solo al elemento n.

Por otro lado, si el elemento n no se encuentra solo, el problema es equivalente a distribuir n-1 elementos en k cajas sin dejar ninguna vacía y luego insertar el elemento n en alguna de ellas (distinguibles por tener distintos subconjuntos de los elementos). En consecuencia habrá

k \left\{\begin{matrix} n-1 \\ k \end{matrix}\right\}

formas de efectuar la distribución sin dejar al elemento n solo en una caja.

En conjunto eso nos deja la 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\}

para estas cantidades, denominadas números de Stirling de segunda especie.

Advertisements

3 thoughts on “Números de Stirling de segunda especie

  1. Jon says:

    “Si ignoramos el “etiquetado” de las cajas, claramente esto nos deja k^n/k! formas”.
    QUE PASA POR EJEMPLO SI QUIERES COLOCAR 3 ELEMENTOS EN 3 CAJAS IGNORANDO EL ETIQUETADO DE LA PAGINA
    (3**3)/3! SALEN DECIMALES!!!!!!!!!!

    • mchouza says:

      Tenés razón! Eso pasa por escribir rápido y asumir demasiado. En realidad el problema sin esa restricción no es más simple, como pensé originalmente…
      Gracias por el comentario!

  2. Jon says:

    buena explicación

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s