Posibles combinaciones de elementos en un determinado número de conjuntos

Question

¿Cuántas formas hay de organizar n elementos en k conjuntos dado que todos los elementos deben ser utilizados en cada arreglo? Ningún conjunto puede estar vacío y el orden no importa (es decir, { a , b , c } es lo mismo que { c , b , a }). Así, por ejemplo, digamos n es 5 y k es tres, habría los siguientes conjuntos:

{a b c d e}

Set 1    Set 2    Set 3
-----    -----    -----
{abc}    {d}      {e}
{ab}     {cd}     {e}
{ab}     {c}      {de}
{a}      {bcd}    {e}
{a}      {bc}     {de}
{a}      {b}      {cde}

etc. El orden de los conjuntos tampoco importa. Así, por ejemplo, los siguientes son equivalentes:

({ab}, {cd}) = ({cd}, {ab})

Otro ejemplo:

({abc}, {d}, {e}) = ({d}, {e}, {abc})

Estoy buscando algún tipo de fórmula para calcular este número. Intenté resolverlo generando los conjuntos manualmente y viendo si podía llegar a una fórmula. Así que cuando n es 3 y k es 2, el número de conjuntos posibles:

({ab}, {c}), ({ac}, {b}) and ({cb}, {a}) 

es sólo

$$\binom{n}{k} = \binom{3}{2} = 3 $$

Aumentar n a 4 (con k todavía como 2) pensé que daría

$$ \binom{n}{k} + \binom{n}{k-1}$$

posibles combinaciones. Pero sé que con sólo escribir todas las posibilidades hay más que eso. Cualquier ayuda será muy apreciada. Gracias.

Answer 1

La respuesta a su pregunta viene dada por $S(n,k)$ El Números Stirling del segundo tipo.

No existe una forma cerrada agradable. Sin embargo, los números de Stirling del segundo tipo satisfacen la agradable recurrencia $$S(n+1,k)=kS(n,k)+S(n,k-1).$$

Answer 2

Dejemos que $S(n,k)$ sea el número de formas de organizar $n$ objetos en $k$ conjuntos donde ningún conjunto está vacío y el orden no es importante. Sea $\{x_j\}_{j=1}^n$ sean los objetos.

Calcule el número de acuerdos en los que $x_n$ está en un conjunto por sí mismo: ese sería el número de formas de ordenar los otros $n-1$ elementos en $k-1$ conjuntos: $S(n-1,k-1)$ .

Calcule el número de acuerdos en los que $x_n$ está en un conjunto con otros elementos: ese sería el número de formas de ordenar los otros $n-1$ elementos en $k$ juegos, tiempos $k$ para cualquiera de los $k$ conjuntos en los que $x_n$ está colocado: $k\,S(n-1,k)$ .

Así, obtenemos $$ S(n,k)=S(n-1,k-1)+kS(n-1,k)\tag{1} $$ Si además observamos que $S(n,n)=1$ y $S(n,1)=1$ entonces podemos calcular $S(n,k)$ para cualquier $n\ge k\ge1$ utilizando $(1)$ .

Como menciona André Nicolas, estos son los Números de Stirling del segundo tipo .