Ways to Arrange 7 things given restrictions

Question

Let's say you have three $z$'s, two $x$'s, and two $y$'s. How many ways are there to arrange those $7$ variables given that $x$ and $y$ cannot be together?

Ex: $zxzxzyy$ and $xxzzzyy$ are valid while $zyxzyzx$ and $xyzzyxz$ are not.

I tried approaching this problem by finding the total number of ways of arranging the $7$ variables (without any restrictions) which was $\frac{7!}{{3!}\cdot{2}\cdot{2}}$ which is ${7}\cdot{6}\cdot{5}$, or $210$.

Then I could subtract the number of impossible combinations, and I did that by grouping one $x$ and one $y$ together to make a O. Then I just calculated the number of ways to arrange O, one $x$, one $y$, and three $z$'s. That was $\frac{6!}{3!}$, which is $120$. Then I multiplied the product by $2$ because O could either be $xy$ or $yx$ to get $240$ total combinations. Since $240$ is greater than $210$, I knew at once that I had over counted. To account for the over counting, I tried to use P.I.E. But at this point I had totally confused myself and now I have no idea what's the right path to take. (Maybe I should have divided the product $120$ by $4$ to account for the duplicate $x$ and $y$ in O?)

Answer 1

We may select three of the seven positions for the $z$'s, two of the remaining four positions for the $x$'s, and fill the remaining two positions with the two $y$'s in $$\binom{7}{3}\binom{4}{2}\binom{2}{2} = \binom{7}{3}\binom{4}{2}$$ ways. From these, we must subtract the number of arrangements in which an $x$ and $y$ are adjacent.

A pair in which $x$ and $y$ are adjacent: Place the $x$ and $y$ in a box. We then have six objects to arrange: $x, y, z, z, z$ and the box containing an $x$ and a $y$. Choose three of the six positions for the $z$'s. Arrange the remaining three distinct objects in the remaining three positions. Arrange the $x$ and $y$ within the box. There are $$\binom{6}{3}3!2!$$ such arrangements.

Two pairs in which an $x$ and $y$ are adjacent: The pairs could be overlapping, meaning that we have $xyx$ or $yxy$, or they could be disjoint.

Overlapping pairs: Consider the case in which two $x$'s are adjacent to a $y$. Then we have five objects to arrange: $xyx, y, z, z, z$. Choose three of the five positions for the $z$'s. Arrange the remaining two distinct objects in the remaining two positions. This can be done in $$\binom{5}{3}2!$$ ways.

By symmetry, there are also $$\binom{5}{3}2!$$ arrangements in which two $y$'s are adjacent to an $x$.

Two disjoint pairs: We have five objects to arrange, three $z$'s and two boxes containing an $x$ and a $y$. Choose three of the five positions for the $z$'s. Fill the remaining two positions with the boxes. Within each box, arrange the $x$ and $y$. This can be done in $$\binom{5}{3}2!2!$$ ways.

Three pairs in which an $x$ and $y$ are adjacent: For this to occur, the string must contain either have $xyxy$ or $yxyx$.

Suppose the string contains $xyxy$. Then we have four objects to arrange: $xyxy, z, z, z$. Choose three of the four positions for the $z$'s. The block $xyxy$ must fill the remaining positions. There are $$\binom{4}{3}$$ such arrangements.

By symmetry, there are also $$\binom{4}{3}$$ arrangements containing the string $yxyx$.

By the Inclusion-Exclusion Principle, the number of arrangements of the seven letters $x, x, y, y, z, z, z$ in which no $x$ and $y$ are adjacent is $$\binom{7}{3}\binom{4}{2} - \binom{6}{3}3!2! + \binom{2}{1}\binom{5}{3}2! + \binom{5}{3}2!2! - \binom{2}{1}\binom{4}{3}$$

Answer 2

The example is small enough to allow another way to count: case analysis by how the $x,x,y,y$ are arranged.

• For $xyxy$, there are $3$ "violations" so to speak, and the three $z$'s must be used to fill the violations, i.e. $xzyzxzy$. This contributes $1$ valid string.

• For $xyyx$, there are $2$ violations which must be filled with $z$'s, i.e. $xzyyzx$. After this, the last $z$ can be placed in any of the $5$ segments separated by $x$ or $y$ (including before the first $x$ and after the last $x$). This contributes $5$ valid strings.

• For $xxyy$, there is $1$ violation which must be filled with $z$, i.e. $xxzyy$. After this, the remaining two $z$'s can be placed in any of the $5$ segments. There are two subcases:

  • the two $z$'s can be placed in separate segments in ${5 \choose 2} = 10$ ways, and

  • the two $z$'s can be placed in the same segment in $5$ ways,

  • which together contribute $15$ valid strings.

• The $yxyx, yxxy, yyxx$ cases are symmetric to the above, respectively.

Total number of valid strings $= (1+5+15) \times 2 = 42 =$ same answer as @NFTaussig