Dado R bolas rojas, B bolas de color azul y G bolas verdes, de cuántas maneras existen para disponer en una línea recta tal que no hay dos bolas del mismo color uno al lado del otro?
En esencia, mi pregunta es una generalización de esta pregunta.
En el post anterior, la aceptó responder enumera todos los casos en que hay una violación de la restricción. Como tal, puede no ser tan fácil de calcular si la cantidad de cada bola es grande (por ejemplo, 100 de cada bola) tenemos que calcular cada caso de forma manual.
Quiero preguntar si hay una generalización de la fórmula o expresión que puede responder a la misma pregunta para R bolas rojas, B bolas de color azul y G bolas verdes (no importa incluso si la expresión no es en forma cerrada porque quiero calcular esta en un equipo).
Podría alguien por favor que me aconsejan?
Respuestas
¿Demasiados anuncios?
Puede echar un vistazo aquí para una serie de enfoques.
Elige el que más te convenga.
Respuesta
Si $t=R+G+B$, entonces el número de acuerdo con ninguna adyacentes idéntico color de las bolas es
$$\sum_{k=0}^{t}(-1)^{k}\sum_{k_R+k_B+k_G=k}\binom{R-1}{k_R}\binom{B-1}{k_B}\binom{G-1}{k_G}\frac{(t-k)!}{(R-k_R)!(B-k_B)!(G-k_G)!}$$
Explicación
Para el conjunto de las bolas de color rojo $\{r_1,r_2\ldots,r_R\}$, azul de bolas $\{b_1,b_2\ldots,b_B\}$, y el verde de bolas $\{g_1,g_2\ldots,g_G\}$ llamar un "adyacencia" de la disposición de las bolas de una sola ocurrencia de igual color de las bolas adyacentes. Entonces, si $A_k$ es la suma de la intersección de los conjuntos de los acuerdos con al menos $k$ adyacencias, a continuación, por medio de la inclusión-exclusión se requiere contar es
$$\sum_{k=0}^{t}(-1)^k|A_k|\, .\tag{1}$$
Así que sigue siendo simplemente para mostrar que $|A_k|$ es el interior de la suma en la respuesta.
Considere la posibilidad de que, para cualquier conjunto $S$ de idéntica bolas de colores, hay
$$\binom{|S|-1}{k_{|S|}}\frac{|S|!}{(|S|-k_{|S|})!}\tag{2}$$
formas de colocar los elementos en $|S|-k_{|S|}$ bloques de desordenada de elementos con $k_{|S|}$ adyacencias: elementos Adyacentes dentro de los bloques de contribuir a una adyacencia pero los elementos adyacentes en neigbouring bloques no por ejemplo, $(r_1,r_2,r_3)(r_4,r_5)$ ha adyacencia $r_1,r_2$ pero no $r_3,r_4$, y es diferente de$(r_2,r_1,r_3)(r_4,r_5)$, pero el mismo como $(r_4,r_5)(r_1,r_2,r_3)$. Los elementos adyacentes dentro de los bloques de contribuir exactamente $1$ adyacencia, por lo que los ejemplos que aquí cada uno tiene $3$ adyacencias.
A ver $(2)$, aviso hay $\binom{|S|-1}{k_{|S|}}$ maneras de poner $|S|$ idénticos bolas en $|S|-k_{|S|}$ bloque con cada bloque que contiene al menos $1$ pelota. Luego hay $|S|!$ formas de etiquetado de los balones. Pero debemos dividir la repite, que es simplemente el número de maneras de organizar $|S|-k_{|S|}$ bloques decir, dividir por $(|S|-k_{|S|})!$, por lo tanto $(2)$.
Para $k=k_R+k_B+k_G$ adyacencias hay $\binom{R-1}{k_R}\frac{R!}{(R-k_R)!}$ formas de constitución de $R-k_R$ rojo bloques de con $k_R$ adyacencias, $\binom{B-1}{k_B}\frac{B!}{(B-k_B)!}$ formas de constitución de $B-k_B$ azul bloques de con $k_B$ adyacencias y $\binom{G-1}{k_G}\frac{G!}{(G-k_G)!}$ formas de constitución de $G-k_G$ verde bloques de con $k_G$ adyacencias. Hay, a continuación, $(R+G+B-(k_R+k_B+k_G))!=(t-k)!$ formas de organización de todos los $t-k$ bloques, dando
$$\binom{R-1}{k_R}\binom{B-1}{k_B}\binom{G-1}{k_G}\frac{R!B!G!(t-k)!}{(R-k_R)!(B-k_B)!(G-k_G)!}$$
total de acuerdos con al menos $k$ adyacencias, y al menos $k_R$ rojo contribuciones, al menos $k_B$ azul contribuciones y, al menos, $k_G$ verde contribuciones.
Para cada una de las $k$ esta debe ser resumida sobre los posibles valores de $k_R,k_B$$k_G$. Así, el número total de acuerdos de los conjuntos sin igual color adyacencias es, por $(1)$
$$\sum_{k=0}^{t}(-1)^{k}\sum_{k_R+k_B+k_G=k}\binom{R-1}{k_R}\binom{B-1}{k_B}\binom{G-1}{k_G}\frac{R!B!G!(t-k)!}{(R-k_R)!(B-k_B)!(G-k_G)!}\, ,$$
pero si queremos tratar a las bolas de color rojo como idénticos, las bolas de color azul como idénticos y bolas verdes como idénticas, debemos dividir los arreglos de los $R!B!G!$ darle nuestra respuesta en la parte superior.
Por lo tanto, vamos a usar el ejemplo de $R=B=G=3$ entonces tenemos:
$$\begin{multline}\frac{9!}{3!^3}-3\binom{2}{1}\binom{2}{0}^2\frac{8!}{2!3!^2}+\left(3\binom{2}{2}\binom{2}{0}^2\frac{7!}{1!3!^2}+3\binom{2}{1}^2\binom{2}{0}\frac{7!}{3!2!^2}\right)\\-\left(6\binom{2}{2}\binom{2}{1}\binom{2}{0}\frac{6!}{1!2!3!}+\binom{2}{1}^3\frac{6!}{2!^3}\right)+\left(3\binom{2}{1}^2\binom{2}{2}\frac{5!}{2!^21!}+3\binom{2}{2}^2\binom{2}{0}\frac{5!}{1!^23!}\right)\\-3\binom{2}{2}^2\binom{2}{1}\frac{4!}{1!^22!}+\binom{2}{2}^3\frac{3!}{1!^3}=174\end{multline}$$
Tenga en cuenta que este método es en realidad sólo el Polinomio de Laguerre método en el disfraz, pero pensé que podría ser instructivo para presentar de esta manera como se arroja un poco de luz sobre el subyacente de la combinatoria.
