# Number of permutations of a string with consequtive repetitions disallowed

Q: How many permutations of a string $AAABBCCDD$ exist such that consequtive characters $AAA$, $BB$, $CC$ and $DD$ don't appear in it. Note that $AA$ on its own is OK.

A: The total number of ways in which we can arrange the sequence $AAABBCCDD$ is $n(\Omega)=\frac{9!}{3!2!2!2!}=7560$. Then we find all permutations which contain sequences of consequtive letters, $AAA$, $BB$ and so on. Let's define some auxilary variables to make the notation shorter: \begin{align*} &a = AAA \\ &b = BB \\ &c = CC \\ &d = DD \\ &R = \{b, c, d\} \\ &L = \{a, b, c, d\} \end{align*} Whenever $x, y, z$ and $w$ appear in the formulae below they are assumed to be all distinct.

We count in stages: first we find all permutations of the string containing $AAA$ or duplicated characters. Some of these permuations will also intersect with each other, thus, we want to subtract duplicates such as $AAA \cup BB$, but now we subtracted some of the duplicates twice, so we need to add them back. Those which we counted twice are those containing three subsequences, and so on.

\begin{align*} &{1\choose 1}7! &\{\langle a \rangle \} \\ +&{1\choose 3}8! &\{\langle x \rangle | x \in R\} \\ -&{2\choose 4}6! &\{\langle a, x \rangle | x \in R\} \cup \{\langle a, x \rangle | x \in R\} \\ -&{2\choose 3}7! &\{\langle x, y \rangle | x, y \in R\} \\ +&{3\choose 4}5! &\{\langle a, x, y \rangle | x, y \in R\} \cup \{\langle x, a, y \rangle | x, y \in R\} \cup \{\langle x, y, a \rangle | x, y \in R\} \\ +&{3\choose 3}6! &\{\langle x, y, z \rangle | x, y, z \in R\} \\ -&{4\choose 4}4! &\{\langle x, y, z, w \rangle | x, y, z, w \in L\} \end{align*}

Problem: The above gives: 107736. So I hoped that $\frac{9!-107736}{3!2!2!2!}=5315.5$ would give the correct answer, but apparently, I'm wrong. I'm sure it must be at least a whole number!

I know the correct answer to be 3414, which I obtained by writing some code to calculate that (the program which does this is really trivial).

The idea of using the inclusion-exclusion principle is fine, but you’re not taking into account the fact that most of the terms have non-trivial denominators analogous to the $3!2!^3$ in the denominator of the expression giving the total number of distinguishable permutations of the string. (You also have your binomial coefficients upside down.) I get the following expression:
\begin{align*} \frac{9!}{3!2!^3}&-\left(\frac{7!}{2!^3}+3\cdot\frac{8!}{3!2!^2}\right)+\left(3\cdot\frac{6!}{2!^2}+3\cdot\frac{7!}{3!2!}\right)-\left(3\cdot\frac{5!}{2!}+\frac{6!}{3!}\right)+4!\\ &=7560-(630+5040)+(540+1260)-(180+120)+24\\ &=3414\;. \end{align*}
Here the first term is of course the total number of distinguishable permutations. The first parenthesis subtracts those in which $AAA$ appears, and those in which one of $BB$, $CC$, and $DD$ appears. For example, if $BB$ appears, I treat it as a single letter, so I have $8$ letters altogether, but $3$ of them are $A$, $2$ are $C$, and $2$ are $D$, so I have to divide the $8!$ by $3!2!^2$. The next parenthesis takes care of the cases in which two of the unwanted strings appear; the first term covers $AAA$ and any one of $BB$, $CC$, and $DD$, and the second term covers any two of the doublets. The last parenthesis takes care of the case of three unwanted strings; the first term covers the triplet and any two doublets, and the second term covers the three doublets. Finally, the $4!$ covers the case in which all four unwanted strings appear.
• Oh, thanks! I see now, I was even closer to this solution than you can see in the one I posted. Where I went wrong by assuming I need to count the "internal arrangements" of $AAA$ when I'm counting all strings containing $AAA$, not the "remaining doubles". – wvxvw May 15 '15 at 22:18