Estantería libros idénticos

Question

Supongamos que tenemos $5$ rojo, $5$ negro y $3$ blancos libros que son indistinguibles a colocar en un) $1$ estante, b) $3$ estantes, de manera que no adyacentes, los libros tienen el mismo color. De cuántas maneras diferentes hay para colocar los libros?

¿Mi solución para el caso de incluir todas las formas posibles?

Nos alineamos todos los libros rojos: _R_R_R_R_R_ y ahora ha $6$ libre de manchas. Elegimos $5$ de ellos para libros negros. Hay $2$ de los casos. Hay o $2$ libros negros, tanto en la izquierda y por la derecha es irregular, o sólo en $1$ de ellos.

Primer caso se parece a esto: BR_R_R_R_RB. Elegimos $3$ más de puntos negros y poner uno de los blancos de los libros en el resto de la mancha. Entonces tenemos algo como esto: BRWRBRBRBRB. Para el resto de las $2$ blanco de libros $10$ spots para elegir: _B_RWR_B_R_B_R_B_R_B_

$$\binom43 \cdot \binom{10}2$$

Como para el segundo caso, tenemos $2$ maneras de poner los libros negros. Ya sea BRBRBRBRBR o RBRBRBRBRB. Tenemos entonces $11$ spots para elegir.

$$2 \cdot \binom{11}3$$

La respuesta que he encontrado así es $180+330=510$

Hay un mejor o un método genérico que puedo usar para este tipo de problemas, yo.e permuting repiten los mismos elementos, que no hay elementos adyacentes son iguales?

Y sin embargo, todavía necesito ayuda para el b) en caso de que si mi solución.

Answer 1

Para (un), vamos a $R(i,j,k)$, $B(i,j,k)$ y $W(i,j,k)$ denotar el número de permutaciones de $i$ rojo libros, $j$ libros negros y $k$ blancos libros con las restricciones (a) el primer libro no es rojo, negro y blanco (respectivamente), y (b) no hay dos libros del mismo color son adyacentes.

Definir $$f(i,j,k)=\begin{cases} 1 & \text{if } i=j=k=0 \\ \tfrac{1}{2}\big( R(i,j,k)+B(i,j,k)+W(i,j,k) \big) & \text{otherwise,} \end{cases}$$ so the number we seek is $f(5,5,3).$

Nos encontramos con las relaciones: \begin{align*} R(i,j,k) &= \begin{cases} B(i,j-1,k)+W(i,j,k-1) & \text{if } j \geq 1 \text{ and } k \geq 1 \\ W(i,0,k-1) & \text{if } j=0 \text{ and } k \geq 1 \\ B(i,j-1,0) & \text{if } j \geq 1 \text{ and } k=0 \\ 0 & \text{if } j=0 \text{ and } k=0 \text{ and } i \geq 1 \\ 1 & \text{if } j=0 \text{ and } k=0 \text{ and } i=0 \\ \end{casos} \\ B(i,j,k) y= \begin{cases} R(i-1,j,k)+W(i,j,k-1) & \text{if } i \geq 1 \text{ and } k \geq 1 \\ R(i-1,j,0) & \text{if } i \geq 1 \text{ and } k=0 \\ W(0,j,k-1) & \text{if } i=0 \text{ and } k \geq 1 \\ 0 & \text{if } i=0 \text{ and } k=0 \text{ and } j \geq 1 \\ 1 & \text{if } i=0 \text{ and } k=0 \text{ and } j=0 \\ \end{casos} \\ W(i,j,k) y= \begin{cases} R(i-1,j,k)+B(i,j-1,k) & \text{if } i \geq 1 \text{ and } j \geq 1 \\ R(i-1,0,k) & \text{if } i \geq 1 \text{ and } j =0 \\ B(0,j-1,k) & \text{if } i=0 \text{ and } j \geq 1 \\ 0 & \text{if } i=0 \text{ and } j=0 \text{ and } k \geq 1 \\ 1 & \text{if } i=0 \text{ and } j=0 \text{ and } k=0. \\ \end{casos} \end{align*} Esto nos permite calcular la respuesta a (a)$f(5,5,3)=1026$.

Podemos verificar esto computacionalmente, por ejemplo, en la BRECHA a través de:

S:=PermutationsList([1,1,1,1,1,2,2,2,2,2,3,3,3]);;
T:=Filtered(S,A->ForAll([1..Size(A)-1],i->A[i]<>A[i+1]));;

cuando Size(T) devuelve 1026 (y, si nos gusta, podemos ver todos los $1026$ permutaciones).

Para (b), voy a asumir los estantes son distinguibles. Podemos utilizar la fórmula anterior, pero, por ejemplo, split $i$ a $i_1,i_2,i_3$ cuántos libros rojos ir en los estantes $1,2,3$, y así sucesivamente. Podemos simplificar señalando que $i_3=5-i_1-i_2$. Por lo tanto el número es

$$ \sum_{i_1=0}^5 \sum_{i_2=0}^{5-i_1} \sum_{j_1=0}^5 \sum_{j_2=0}^{5-j_1} \sum_{k_1=0}^3 \sum_{k_2=0}^{3-k_1} f(i_1,j_1,k_1) \times f(i_2,j_2,k_2) \times f(5-i_1-i_2,5-j_1-j_2,3-k_1-k_2) $$ Si ejecutamos los números, nos encontramos con $192216$ arreglos.

(También he comprobado esta computacionalmente, la generación de la $192216$ arreglos en la BRECHA; mi código es vergonzosamente fuerza bruta, así que no voy a publicar aquí.)

Answer 2

No es agradable no se desordenado manera de hacer esto, excepto que acaba de calcular.

Vamos a definir el número de $N_s(r, b, w)$ a ser el número de maneras en que $r$ rojo, $b$ negro y $w$ blancos libros se pueden organizar en un estante, a partir de un libro de color $s \in \{\text{red}, \text{black}, \text{white}\}$, y de tal manera que no de los libros del mismo color son adyacentes.

Podemos escribir de relaciones de recurrencia de la $N_s(r, b, w)$ (que resultan ser ligeramente más sencillo que los de Rebecca la respuesta) y calcular nuestra respuesta como $$N_{\text{red}}(5, 5, 3) + N_{\text{black}}(5, 5, 3) + N_{\text{white}}(5, 5, 3).$$

To say precisely what these recurrence relations are, we might as well express them in code, as in the Haskell program below (where for convenience of notation I made $s$ the first argument to the function n, and also assigned the labels $0, 1, 2$ for red, black and white respectively):

n 0 1 0 0 = 1
n 1 0 1 0 = 1
n 2 0 0 1 = 1
n 0 r b w | r > 0 = n 1 (r-1) b w + n 2 (r-1) b w
n 1 r b w | b > 0 = n 0 r (b-1) w + n 2 r (b-1) w
n 2 r b w | w > 0 = n 0 r b (w-1) + n 1 r b (w-1)
n _ _ _ _ = 0

main = print (n 0 5 5 3 + n 1 5 5 3 + n 2 5 5 3)

Running this program gives the answer $1026$.

$ runhaskell mse-659036.hs
1026

---

For the three-shelf case, we have to sum these three answers $N_s$ over all triples $(r, b, w), (r', b', w'), (r", b", w")$ that add up to $(5, 5, 3)$.

---

More generally (though it's no help to you for this small case), words over a certain alphabet such that no letter appears twice consecutively (no two adjacent letters are equal) are called Smirnov words. It is possible to write down a (complicated) generating function for them, as follows.

Consider any arbitrary word over an alphabet of three letters. We can identify each "block" of equal consecutive letters and "collapse" them to a single occurrence of that letter, to get a Smirnov word. Conversely, the set of all words over the alphabet can be got by taking any Smirnov word, and replacing each letter in it by a (nonempty) sequence over that letter.

Thus, if $W(x, y, z)$ is the generating function for all words - note that is simply $W(x, y, z) = \dfrac{1}{1-(x+y+z)}$ - and the generating function for Smirnov words is $S(x, y, z)$, entonces la "expansión" bijection anterior nos da: $$W(x, y, z) = S\left(\frac{x}{1-x}, \frac{y}{1-y}, \frac{z}{1-z}\right)$$ o, de manera equivalente, como $u = \frac{x}{1-x}$$x = \frac{u}{1+u}$, $$\begin{align} S(x, y, z) &= W\left(\frac{x}{1+x}, \frac{y}{1+y} ,\frac{z}{1+z}\right) \\ &= \frac{1}{1-\left(\frac{x}{1+x} + \frac{y}{1+y} + \frac{z}{1+z}\right)}. \end{align}$$

So for your two problems, we can abstractly give an answer as

1. The coefficient of $x^5^5z^3$ in $S(x, y, z)$, y

2. El coeficiente de $x^5y^5z^3$ $S(x, y, z)^3$

respectivamente. Un sistema de álgebra computacional puede ser capaz de evaluar estos coeficientes. Por supuesto, la generación de la función es más útil para el análisis asintótico.