5 votos

Bolas de colores en cubos sin etiquetar

Estoy buscando una forma más genérica de aplicar esto, pero este es el problema en pocas palabras. Tengo una serie de bolas que se dividen en particiones. Por ejemplo, podría tener lo siguiente:

  • 5 bolas azules
  • 4 bolas verdes
  • 2 bolas amarillas
  • 1 bola roja
  • 1 bola negra

Intento ponerlos en un número de cubos, digamos 3 para este problema, aunque el número puede variar. Cada cubo debe tener una combinación única de bolas al final, es decir, no puede haber dos cubos con el mismo número de bolas del mismo tipo. Todas las bolas deben estar en un cubo para satisfacer las condiciones. Se permite un cubo vacío. ¿Cuántas combinaciones hay?

Para explicarlo un poco más, si dos cubos tuvieran cada uno 2 bolas azules y 1 verde, no sería aceptable. Sin embargo, si uno tuviera 2 bolas azules y 2 verdes, y el otro tuviera 2 bolas azules y 1 verde, está bien. Además, un cubo vacío está bien, ya que es distinto.

Para un ejemplo muy sencillo, imagine que 4 bolas azules, 2 rojas, van a 4 cubos. Hay 7 combinaciones, bbb|rr|b|0, bb|brr|b|0, b|bbrr|b|0, br|bbr|b|0, bbb|br|r|0, bbr|bb|r|0, y b|br|bb|r donde 0 es vacío, b es azul, r es rojo, y | es el divisor entre particiones.

Tenga en cuenta que quiero entender cómo funciona esto para aplicarlo a un problema más grande en el que estoy trabajando, pero si puedo entender esto, entonces hará que el problema más grande sea más fácil.

Debo añadir que sólo necesito el número exacto, no necesito mostrar todas las combinaciones que hay.

1voto

Michael D. Puntos 521

Se puede calcular el número de todos los arreglos, y luego restar el número de arreglos que rompen su regla (no hay dos cubos iguales).

El número de arreglos con cubos iguales se puede encontrar centrándose en el tercer cubo. Porque para cada colocación de bolas en el tercer cubo:

a) puede haber una (1) disposición que rompa la regla si las bolas del cubo que no están en el tercero son un número par para cada categoría de color - divídelas en partes iguales;

b) no puede haber un arreglo que rompa las reglas si la categoría de CUALQUIER color tiene un número impar de bolas que no sean del tercer cubo.

Entonces, ¿de cuántas maneras podemos poner las bolas en el tercer cubo, para que haya un resto par de bolas en cada categoría de color?

$3(blue) * 3 (green) * 2(yellow) * 1 (red) * 1(black)$

Así que del número total de disposiciones de bolas dadas en tres cubos indistintos resta 18.

q.e.d.

1voto

jwarzech Puntos 2769

Yo organizaría los recuentos de forma jerárquica, empezando por el color de las bolas que tienen el mayor número y trabajando hacia abajo. Expresado en términos de multiplicación matricial similar a esta pregunta y respuesta anterior se pueden afirmar los estados finales de dos cubos idénticos frente a los tres cubos diferentes:

$$ \begin{bmatrix} 3 & 2 \end{bmatrix} \begin{bmatrix} 3 & 6 \\ 0 & 15 \end{bmatrix} \begin{bmatrix} 2 & 2 \\ 0 & 6 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 0 & 3 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 0 & 3 \end{bmatrix} = \begin{bmatrix} 18 & 2826 \end{bmatrix} $$

El número máximo de estados a tener en cuenta para esto es el número de particiones de los tres cubos, es decir [3] , [2&1] , [1&1&1] . Obsérvese que el primero de estos estados desaparece con la distribución del primer $5$ bolas azules, ya que no se pueden colocar de manera uniforme. Si (como en el comentario publicado en la otra respuesta) hubiera diez cubos, tendríamos $42$ estados potenciales (el número de particiones enteras de $10$ ). De este modo, se amplían los tamaños de las matrices de transición que aparecen en la multiplicación de matrices.

A continuación se describe con palabras el presente cómputo de (sólo los tres) resultados distintos de los cubos.


Si las (en este caso) cinco bolas azules se distribuyen en los tres cubos (sin etiquetar), se obtendrán tres cubos distinguidos o un par de cubos iguales y un tercer cubo distinguido de los otros dos. Este es el resultado inevitable de cualquiera de las posibles distribuciones de cinco bolas en tres cubos:

 [1&1&1]    [2&1]    after placing blue balls
 -------   -------  

            5+0+0  
  4+1+0  
  3+2+0  
            3+1+1  
            2+2+1  

Tenga en cuenta que hay dos formas de obtener tres cubos distinguidos y tres formas de obtener un par de cubos idénticos más un tercer cubo que difiere.

A continuación, aplicamos los colores sucesivos de las bolas a las particiones de cubos previamente establecidas. Si un par de cubos se distinguen, seguirán siéndolo independientemente de cómo se distribuyan los colores posteriores, y finalmente sólo nos interesan los arreglos en los que todos los cubos se han diferenciado.

En los dos casos anteriores, en los que las cinco bolas azules ya distinguen los tres cubos, los colores restantes pueden distribuirse independientemente en estos tres cubos como si estuvieran etiquetados (como de hecho han sido etiquetados por la colocación de las bolas azules).

En otras palabras, la distribución de un nuevo color en tres cubos que se distinguen individualmente ya sigue el cómputo (relativamente) fácil de estrellas y barras, y dadas las dos formas de obtener tres cubos distinguidos, podemos terminar esos recuentos multiplicando (principio de elecciones independientes):

$$ 2 \times \binom{6}{2} \times \binom{4}{2} \times \binom{3}{2} \times \binom{3}{2} = 1620 $$

Mientras los dos cubos permanecen sin distinguirse (idénticos hasta ahora), tenemos que hacer una contabilidad adicional, para llevar la cuenta del momento en que se distinguen. En este caso, las cuatro bolas verdes pueden aplicarse de forma que se mantenga la igualdad de los dos cubos "gemelos" o que se distingan.

Para mantener su igualdad es necesario distribuir un número par de las bolas verdes en los cubos gemelos y repartir esas bolas a partes iguales entre ellos. Por lo tanto, si se reparte un número impar de bolas verdes entre los cubos gemelos, o si se reparte un número par entre ellos de forma desigual, llegamos a distinguir los tres cubos:

   For each twin bucket case [2&1] after placing blue balls:  

 [1&1&1]    [2&1]     after placing green balls  
 -------   ------

            0+0;4  
  1+0;3  
  2+0;2  
            1+1;2  
  3+0;1  
  2+1;1  
  4+0;0  
  3+1;0   
            2+2;0  

Como esto ilustra, el $3$ Los casos de cubos gemelos después de colocar las bolas azules se convierten en $3\times 6=18$ casos de tres cubos distinguidos y $3\times 3=9$ casos conservando los cubos gemelos idénticos después de colocar las bolas verdes.

Disponemos de los tres casos actuales de cubos distinguidos como antes, utilizando los cálculos de estrellas y barras + elección independiente:

$$ 18 \times \binom{4}{2} \times \binom{3}{2} \times \binom{3}{2} = 972 $$

Esto nos deja la siguiente tarea de colocar las bolas amarillas en los nueve casos en que se conservan los cubos gemelos.

    For each twin bucket case [2&1] after placing green balls  

 [1&1&1]    [2&1]    after placing yellow balls  
 -------   -------  

            0+0;2  
  1+0;1  
            1+1;0  
  2+0;0  

Por lo tanto, obtenemos $9\times 2 = 18$ casos en los que los tres cubos se han distinguido y $9\times 2 = 18$ casos en los que queda un par de cubos gemelos. El primero rinde eventualmente este número de arreglos, al colocar los dos colores finales:

$$ 18 \times \binom{3}{2} \times \binom{3}{2} = 162 $$

El $18$ Los casos en los que quedan cubos gemelos después de colocar las bolas amarillas resultan así cuando se coloca la bola roja:

    For each twin bucket case [2&1] after placing yellow balls  

 [1&1&1]    [2&1]    after placing red ball   
 -------   -------  

            0+0;1  
  1+0;0  

De este modo, obtenemos un $18$ casos en los que se distinguen los tres cubos, y también $18$ casos en los que persisten los cubos gemelos. El primero nos da eventualmente:

$$ 18 \times \binom{3}{2} = 54 $$

y el $18$ Los casos en los que los cubos gemelos persisten después de colocar la bola roja nos obligan a utilizar la colocación de la última bola negra para romper su simetría.

Eso añade un último $18$ resultados (con todos los recuentos de cubos diferentes).

Así que el número total de formas de colocar estas bolas de colores en los tres cubos de manera que no haya dos cubos iguales es:

$$ 1620 + 972 + 162 + 54 + 18 = 2826 $$

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X