¿Existe una fórmula para calcular el número de arreglos de un conjunto de N elementos agrupados en K grupos?

Question

Ej .: N=3 , K=2

Habrá dos grupos en cada solución. Necesitamos calcular el número de tales soluciones posibles. Considere el conjunto S={1,2,3} . Las posibles soluciones son:

 {1} {2,3}
{1} {3,2}
{2} {1,3}
{2} {3,1}
{3} {1,2}
{3} {2,1}
{1,2} {3}
{2,1} {3}
{1,3} {2}
{3,1} {2}
{2,3} {1}
{3,2} {1}
 

El resultado para este ejemplo es: 12 .

Ej .: N=4, K=3

 {1} {2} {3,4}
{1} {2} {4,3}
{1} {2,3} {4}
{1} {3,2} {4}
....
 

¿Podemos generalizar esta fórmula?

Answer 1

Suponemos que el ejemplo de $N=3$, $K=2$ es correcto, lo que significa que el orden interno de los elementos en los distintos grupos de materias.

Hay $N!$ maneras de alinear nuestra $N$ objetos. Que produce $N-1$ interobject "vacíos". Nos elija $K-1$ de ellos para poner un separador en.

Que se puede hacer en $\binom{N-1}{K-1}$ formas, para un total de $N!\binom{N-1}{K-1}$.

Observación: Si el orden interno dentro de los grupos, no importa, la solución es bastante diferente, y utiliza los números de Stirling del segundo tipo.

Answer 2

Considere la posibilidad de un arreglo de un conjunto $S = \{ a_1, a_2, a_3, \dots, a_n\}$.

Necesitamos partición de este set en $K$ grupos de tal manera que cada grupo contiene más de un elemento tal que el orden relativo de los elementos siguen siendo los mismos. Por ejemplo, para $S = \{1,2,3\}$, la partición de $\{1\},\{2,3\}$ será válida sino $\{2\},\{1,3\}$ no será válido.

Deje $x_i$ el número de elementos en $i^{th}$ partición, así que tenemos $$x_1 + x_2 + x_3 + \dots + x_k = n$$

donde cada una de las $x_i \ge 1$. Este es un problema clásico y sabemos que el número de maneras para el problema anterior es $$P = \binom{n-1}{k-1}$$

Hay $n!$ conjuntos, S son posibles por lo que el número de acuerdos será igual a $n!*P$.