6
$\begingroup$

Suppose that we have $5$ red, $5$ black and $3$ white books that are indistinguishable to place onto a) $1$ shelf, b) $3$ shelves, so that no adjacent books have the same colour. How many different ways are there to place the books?

Does my solution for the a) case include all possible ways?

We line up all red books: _R_R_R_R_R_ and now have $6$ free spots. We choose $5$ of them for black books. There are $2$ cases. There are either $2$ black books both at the leftmost and the rightmost spot, or only at $1$ of them.

First case looks like this: BR_R_R_R_RB. We choose $3$ more spots for blacks and put one of the white books in the remaining spot. Then we have something like this: BRWRBRBRBRB. For the remaining $2$ white books we have $10$ spots to choose from: _B_RWR_B_R_B_R_B_R_B_

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

As for the second case, we have $2$ ways to put the black books. Either BRBRBRBRBR or RBRBRBRBRB. We have then $11$ spots to choose from.

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

The answer I found thus is $180+330=510$

Is there a better or a generic method that I can use for such problems, i.e permuting repeated identical items such that no adjacent items are same?

And nevertheless, I still need help for the b) case if my solution were right.

$\endgroup$
  • $\begingroup$ Your solution for a is wrong, because you will miss out cases which have 2 B between 2 R like: RBWBRBRBRBWRW $\endgroup$ – Calvin Lin Feb 3 '14 at 23:02
  • $\begingroup$ You are right. @CalvinLin $\endgroup$ – Zafer Cesur Feb 3 '14 at 23:07
4
+50
$\begingroup$

For (a), let $R(i,j,k)$, $B(i,j,k)$ and $W(i,j,k)$ denote the number of permutations of $i$ red books, $j$ black books and $k$ white books with the restrictions (a) the first book is not red, black and white (respectively), and (b) no two books of the same color are adjacent.

Define $$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).$

We find the relationships: \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{cases} \\ B(i,j,k) &= \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{cases} \\ W(i,j,k) &= \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{cases} \end{align*} This allows us to compute the answer to (a) as $f(5,5,3)=1026$.

We can verify this computationally, e.g., in GAP via:

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]));;

when Size(T) returns 1026 (and, if we like, we can view all $1026$ permutations).

For (b), I'll assume the shelves are distinguishable. We can use the above formula, but e.g. split $i$ into $i_1,i_2,i_3$ as to how many red books go on shelves $1,2,3$, and so on. We can simplify by noting that $i_3=5-i_1-i_2$. Thus the number is

$$ \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) $$ If we run the numbers, we find $192216$ arrangements.

(I also checked this computationally, generating the $192216$ arrangements in GAP; my code is embarrassingly brute force, so I won't post it here.)

$\endgroup$
  • $\begingroup$ Thanks a lot! Even though these functions look grotesque, I'll try my best to understand it :D One more question, if we split an adjacent pair to different shelves, it becomes no more adjacent. I guess you overlooked that case, maybe? It doesn't matter since it has no nice answer, though. $\endgroup$ – Zafer Cesur Feb 6 '14 at 16:46
  • $\begingroup$ Nice work. BTW, your recurrence relations would be simplified significantly, if you just declared that the functions are zero when any arguments are negative. Then I think you only need the $(0, 0, 0)$ case and the general case (and the negative case), for each of your three functions. $\endgroup$ – ShreevatsaR Feb 6 '14 at 17:49
4
$\begingroup$

There is no nice non-messy way to do this, except to just compute it.

Let's define the number $N_s(r, b, w)$ to be the number of ways that $r$ red, $b$ black and $w$ white books can be arranged on a shelf, starting with a book of colour $s \in \{\text{red}, \text{black}, \text{white}\}$, and such that no books of the same colour are adjacent.

We can write down recurrence relations for the $N_s(r, b, w)$ (which turn out to be slightly simpler than those in Rebecca's answer) and calculate our answer as $$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)$, then the "expanding" bijection above gives: $$W(x, y, z) = S\left(\frac{x}{1-x}, \frac{y}{1-y}, \frac{z}{1-z}\right)$$ or, equivalently, as $u = \frac{x}{1-x}$ means $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^5y^5z^3$ in $S(x, y, z)$, and

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

respectively. A computer algebra system may be able to evaluate these coefficients. Of course, the generating function is more useful for asymptotic analysis.

$\endgroup$
  • $\begingroup$ Thanks. You don't need to elaborate as I'm probably going to not understand it anyway. :-D $\endgroup$ – Zafer Cesur Feb 6 '14 at 16:48
  • $\begingroup$ @ZaferCesur: Sure. But I wrote it anyway; might help some other reader. :-) Good luck, $\endgroup$ – ShreevatsaR Feb 6 '14 at 17:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.