Number of permutations of $D,D,D,O,O,O,G,G,G$ such that no two $D$ are adjacent and no two $G$ are adjacent

Question

I have the following problem. I already solved it but I am not happy with my solution. I hope for a more slick solution and maybe somebody can help with it. Is there a way to solve this problem with just the stars/bars method?

Compute the number of ways to permute all letters from $D,D,D,O,O,O,G,G,G$ such that no two $D$ are adjacent and no two $G$ are adjacent.

My attempt.

For $k=2,3$, let $\Delta_k$ denote the set of permutations s.t. only $k$ of $D$ are adjacent, and let $\Gamma_k$ denote the set of permutations s.t. only $k$ of $G$ are adjacent. Let $U$ be the set of all permutations without any conditions.

Then $$|U|=\frac{(3+3+3)!}{3!3!3!}=1680.$$ We have $$|\Delta_3|=\frac{(1+3+3)!}{1!3!3!}=140$$ (as $\Delta_3$ is the set of permutations of $DDD,O,O,O,G,G,G$), and $$|\Delta_2|+2|\Delta_3|=\frac{(1+1+3+3)!}{1!1!3!3!}=1120$$ since this number counts the permutations of $DD,D,O,O,O,G,G,G$. Therefore $$|\Delta_2|=1120-2(140)=840.$$ Similarly $|\Gamma_3|=140$ and $|\Gamma_2|=840$.

We want to find $|\Delta_i\cap\Gamma_j|$. Since $\Delta_3\cap\Gamma_3$ is the set of permutations of $DDD,O,O,O,GGG$, $$|\Delta_3\cap\Gamma_3|=\frac{(1+3+1)!}{1!3!1!}=20.$$ Since $|\Delta_2\cap\Gamma_3|+2|\Delta_3\cap\Gamma_3|$ counts the permutations of $DD,D,O,O,O,GGG$, we have $$|\Delta_2\cap\Gamma_3|+2|\Delta_3\cap\Gamma_3|=\frac{(1+1+3+1)!}{1!1!3!1!}=120$$ so $$|\Delta_2\cap\Gamma_3|=120-2(20)=80.$$ Similarly $|\Delta_3\cap\Gamma_2|=80$.

We now want to find $|\Delta_2\cap\Gamma_2|$. Since $|\Delta_2\cap\Gamma_2|+2|\Delta_3\cap\Gamma_2|+2|\Delta_2\cap\Gamma_3|+4|\Delta_2\cap\Gamma_3|$ counts the number of permutations of $DD,D,O,O,O,GG,G$, we get $$|\Delta_2\cap\Gamma_2|+2|\Delta_3\cap\Gamma_2|+2|\Delta_2\cap\Gamma_3|+4|\Delta_2\cap\Gamma_3|=\frac{(1+1+3+1+1)!}{1!1!3!1!1!}=840.$$ Hence $$|\Delta_2\cap\Gamma_2|=840-2(80)-2(80)-4(20)=440.$$

By inclusion-exclusion principle we have $$|\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3|=\sum_{k=2}^3|\Delta_k|+\sum_{k=2}^3|\Gamma_k|-\sum_{i=2}^3\sum_{j=2}^3|\Delta_i\cap \Gamma_j|.$$ Therefore $$|\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3|=2(840)+2(140)-(440+80+80+20)=1340.$$ The question asks for the size of $U\setminus(\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3)$, which is $$|U|-|\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3|=1680-1340=340.$$

Answer 1

I don't know if there is a slicker way to do this but it can be simpler, even using your approach.

Permutations of "DD D G G G O O O" cover all cases of adjacent D's and adjacent G's except where G's are adjacent but D's are not.

$i)$ Permutations of "DD D G G G O O O" $= \dfrac{8!}{3!3!} - \dfrac{7!}{3!3!} = 980$

[The subtraction is to take care of adjacent DD D and D DD considered different. So DDD permutations are counted twice and need to be taken out once.]

$ $

$ii)$ Permutations of "GG G O O O" and placing $3$ D's in $3$ of the non-adjacent $6$ places

$$= \dfrac{5!}{3!}.{^6}C_3 - \dfrac{4!}{3!}.{^5}C_3 = 360$$

[The subtraction is to take care of adjacent GG G and G GG considered different. So GGG permutations and placing D in $3$ out of $5$ places have been counted twice and need to be counted out once.]

$ $

That gives you the desired arrangements $= 1680 - 980 - 360 = 340$

Answer 2

I start by restating and modifying the problem slightly, then solve it under this new form; the passage to the initial problem is canonical.

Problem. Consider the set $S=S(d+4)=\{x_1, x_2, x_3, y_1, y_2, y_3, z_1, \ldots, z_{d-2}\}$. A permutation of $S$ is called $x,y$-adjacent free (and later of type $(1,1)$) if no two $x$'s and no two $y$'s are adjacent. Determine the number of $x,y$-adjacent free permutations.

1. Note that the elements $x_1$, $x_2$, and $x_3$ are seen as distinct elements (and the same for the $y$'s).

2. The passage from Problem to the initial question is given by the obvious formula $$ \frac{\text{number of $x,y$-adjacent free permutations of $S$}} {3!\, 3!\, (d-2)!} $$ in which we take $d=3$.

The solution leans towards recursive algebraic computations (the model being Pascal's triangle). On the positive side, we might be happy with recursive formulas (generalizations, computations of other similar numbers...). On the negative side, there will be cumbersome flying indices in all directions.

Notation and description of the solution. Let $S^{a,b}\subset S$ be the subset $$ S^{a,b} = \{ x_1,\ldots,x_a, y_1, \ldots, y_b, z_1, \ldots, z_{d-2}\} \subset S $$ with $1\leq a,b\leq3$. It has $d+a+b-2$ elements. Denote by $P_{(i,j)}^{a,b}$, with $i\leq a$ and $j\leq b$, the set of permutations of $S^{a,b}$ with exactly $i$ adjacent $x$'s and $j$ adjacent $y$'s, called permutations of type $(i,j)$. Clearly the set of all permutations of $S^{a,b}$ is $$ \bigcup_{\substack{1\leq i\leq a\\1\leq j\leq b}} P_{(i,j)}^{a,b}. $$ We want to compute $N_{(1,1)}^{3,3}$, the cardinal of $P_{(1,1)}^{3,3}$. The idea is to do the computation recursively using the following filtration of $S^{3,3}$: $$ S^{1,1} \subset S^{2,1} \subset S^{3,1} \subset S^{3,2} \subset S^{3,3}. $$ Each $N_{(i,j)}^{a,b}$ corresponding to the subset $S^{a,b}$ in the filtration is expressed as a linear combination with integer coefficients of all the $N$'s of the previous subset. Once the coefficients are determined (using the combinatorics of the construction) for all these passages, the problem is solved.

Finding the coefficients. Let's start with what we are looking for: $$ N_{(1,1)}^{3,3} = d\,N_{(1,1)}^{3,2} + N_{(2,1)}^{3,2}. $$ The other coefficients are all zero in this case. The explanation is that a permutation of $S^{3,3}$ of type $(1,1)$ can only be issued from a permutation of $S^{3,2}$ which is either of type $(1,1)$ or of type $(2,1)$. For a permutation in the former case, there are exactly $d=d+4-4$ positions (out of $d+4$) where $y_3$ can be inserted (adjacent to neither $y_1$ nor $y_2$). In the latter case, $y_3$ must be inserted in-between the two adjacent $x$'s.

We pursue with the formulas for $N_{(1,1)}^{3,2}$ and $N_{(2,1)}^{3,2}$ using the passage from $S^{3,1}$ to $S^{3,2}$ in our filtration. The formula for $N_{(1,1)}^{3,2}$ is almost the same as the previous one: $$ N_{(1,1)}^{3,2} = (d+3-2)\,N_{(1,1)}^{3,1} + N_{(2,1)}^{3,1} = (d+1)\,N_{(1,1)}^{3,1} + N_{(2,1)}^{3,1}. $$ The formula for $N_{(2,1)}^{3,2}$ is trickier. It reads $$ N_{(2,1)}^{3,2} = 0\,N_{(1,1)}^{3,1} + (d+3-3)\,N_{(2,1)}^{3,1} + 2N_{(3,1)}^{3,1} \\ = d\,N_{(2,1)}^{3,1} + 2N_{(3,1)}^{3,1}. $$ The coefficient $d+3-3$ comes form the following observation: If a type $(2,1)$ permutation of $S^{3,2}$ is issued form a type $(2,1)$ permutation of $S^{3,1}$, then $y_2$ has exactly $d+3-3$ possible places to be inserted in: $d+3$ is the total number of places and $y_2$ can take neither the place in-between the adjacent $x$'s nor any of the two places adjacent to $y_1$.

Looking at the last two formulas, we note that from now on we need all the $N$'s corresponding to the remaining subsets of the filtration. But they are fewer and the formulas easier to figure out. We obtain successively:

• for $S^{2,1}\subset S^{3,1}$ $$ N_{(1,1)}^{3,1} = (d+2-4)\,N_{(1,1)}^{2,1} + 0\,N_{(2,1)}^{2,1} $$ $$ N_{(2,1)}^{3,1} = 4\,N_{(1,1)}^{2,1} + (d+2-3)\,N_{(2,1)}^{2,1} $$ $$ N_{(3,1)}^{3,1} = 0\,N_{(1,1)}^{2,1} + 3\,N_{(2,1)}^{2,1} $$

• for $S^{1,1}\subset S^{2,1}$ $$ N_{(1,1)}^{2,1} = (d+1-2)\,N_{(1,1)}^{1,1} \quad\text{and}\quad N_{(2,1)}^{2,1} = 2\,N_{(1,1)}^{1,1}. $$

The computations Now, to obtain $N_{(1,1)}^{3,3}$ it is sufficient to go backward starting with $N_{(1,1)}^{1,1}=d!$. Let's perform the computations by stressing their algorithmic character. I hope the notation below is self-explanatory.

1. For $S^{2,1}$: $$ \begin{array}{c||c|cr} & (1,1) && result/d! \\ \hline (1,1) & d-1 && (d-1) \\ (2,1) & 2 && 2 \end{array} $$

2. For $S^{3,1}$: $$ \begin{array}{c||c|c|cr} & (1,1) & (2,1) && result/d! \\ \hline (1,1) & d-2 & 0 && (d-2)(d-1) \\ (2,1) & 4 & d-1 && 6(d-1) \\ (3,1) & 0 & 3 && 6 \end{array} $$

3. For $S^{3,2}$ (partial table): $$ \begin{array}{c||c|c|c|cr} & (1,1) & (2,1) & (3,1) && result/d! \\ \hline (1,1) & d+1 & 1 & 0 && (d-1)(d^2-d+4) \\ (2,1) & 0 & d & 2 && 6(d^2-d+2) \end{array} $$

4. So $$ \begin{split} N_{(1,1)}^{3,3} &= d\,N_{(1,1)}^{3,2} + N_{(2,1)}^{3,2} \\ &= \big( (d^2-d)(d^2-d+4) + 6(d^2-d+2) \big)\,d! \\ &= \big( (d^2-d)^2 + 10(d^2-d) + 12 \big)\,d! \\ &= \big( (d^2-d+4)(d^2-d+6) - 12 \big)\,d!. \end{split} $$

In particular, the answer to the initial question is $$ \frac{(5^2-5+4)(5^2-5+6)-12}{3!\,3!}\,\frac{5!}{3!} = 20\,\frac{2\cdot26-1}{3} = 340. $$