0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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". $\endgroup$ – wvxvw May 15 '15 at 22:18
  • $\begingroup$ @wvxvw: You're welcome! $\endgroup$ – Brian M. Scott May 16 '15 at 0:01

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.