Counting permutations with inclusion-exclusion

Question

How many permutations are there of the letters XXXYYYZZZ if no more than two X’s can appear together and no more than two Y’s can appear together?

I get a vague idea that I should use PIE to solve this. However, I don't know how to apply it. How should I approach this?

Answer 1

Let $W$ be the set of all possible permutations of $\texttt{X}, \texttt{X}, \texttt{X}, \texttt{Y}, \texttt{Y}, \texttt{Y}, \texttt{Z}, \texttt{Z}, \texttt{Z}$. Also, let $X$ (resp., $Y$) be the set of all words in $W$ that contains the substring $\texttt{XXX}$ (resp., $\texttt{YYY}$). We want to compute the number of elements of the set $W \setminus (X \cup Y)$. PIE tells that

$$ |W\setminus(X \cup Y)| = |W| - |X| - |Y| + |X \cap Y|, $$

so it suffices to compute $|W|$, $|X|$, $|Y|$, and $|X\cap Y|$. The key idea is that each of these numbers can be systematically computed using the permutations:

• Clearly $|W| = \binom{9}{3,3,3} = 1680. $

• Any word in $X$ can be obtained by treating the substring $\texttt{XXX}$ as a single symbol. Then $X$ is the set of all permutations of $\texttt{XXX}, \texttt{Y}, \texttt{Y}, \texttt{Y}, \texttt{Z}, \texttt{Z}, \texttt{Z}$, and so, $|X| = \binom{7}{1,3,3} = 140$. By the same reasoning, we also have $|Y| = \binom{7}{1,3,3} = 140$.

• Any word in $X \cap Y$ can be obtained by treating each of $\texttt{XXX}$ and $\texttt{YYY}$ as a single symbol. Then $X$ is the set of all permutations of $\texttt{XXX}, \texttt{YYY}, \texttt{Z}, \texttt{Z}, \texttt{Z}$, so it follows that $|X \cap Y| = \binom{5}{1,1,3} = 20$.

Therefore,

\begin{align*} |W\setminus(X \cup Y)| = \binom{9}{3,3,3} - 2\binom{7}{1,3,3} + \binom{5}{1,1,3} = \bbox[color:navy;padding:5px;border:1px navy dotted;]{1420}. \end{align*}

Answer 2

• There are $$\binom{9}{3,3,3}=\frac{9!}{3!^3}=1680$$ permutations if you ignore the restrictions.
• Now consider the permutations that contain three consecutive Xs (XXX). The XXX can appear in $9-3+1=7$ starting positions, and then you can permute the Ys and Zs arbitrarily in the remaining $9-3=6$ positions, yielding $7\binom{6}{3}=140$ permutations. The count for YYY is the same.
• Now consider the permutations that contain both XXX and YYY. If you think of XXX as one symbol, YYY as one symbol, and the three Zs as three separate (but identical) symbols, you can see that there are $\frac{5!}{3!}=20$ such permutations.

Putting it all together, PIE yields a final count of

$$1680 - 2\cdot 140 + 20 = 1420.$$