combinatorics problem - permutations and e/i

Question

I am hoping that someone can please check my work and let me know if my logic is flawed. I have the string of characters "catvsdog". How many arrangements of this word are there so that "cat" OR "dog" do not appear?

My logic:

The number of permutations of the string with no restrictions is $8!$. Let $A$ be all permutations that do not contain the word "cat" so $|A| = 8!-6!$. Let $B$ be all permutations that do not contain the word "dog" so $|B| = 8!-6!$. Let $C$ be all permutations that do not contain both "cat" and "dog" so $|C| = 8!-4!$. Using the principle of exclusion and inclusion, $$|A\cup B| = |A| + |B| -|C| = (8!-6!) + (8!-6!) - (8!-4!).$$

Am I correct? Thank you all!

Answer 1

Check your calculation of $|C|$. You say $|C|$ is the number of permutations that simultaneously don't contain either of cat nor dog and calculated it as $8!-4!$.

It would seem your logic is that by calling cat all one letter and dog all one letter, we arrange CvsD in $4!$ ways and so the number of ways that we can arrange catvsdog without the word cat and without the word dog is $8!-4!$.

In actuality, this counts the number of arrangements without both cat and dog appearing, i.e. the number of arrangements with at least one of them missing, not the number of arrangements with both of them missing. You should actually have this ($8!-4!$) as the amount you were originally looking for and the amount you intended to calculate ($|C|$ where both are missing) is harder to find.

---

Using your notation that $A$ as the set of arrangements without cat and $B$ the set without dog:

$\begin{array}{c|c|c} A^c&\text{has a cat}&6!\\ A&\text{has no cat}&8!-6!\\ B&\text{has no dog}&8!-6!\\ A^c\cap B^c&\text{has a cat and has a dog}&4!\\ (A\cup B)^c&\text{complement of has no cat or has no dog}&4!\\ A\cup B&\text{has no cat or has no dog}&8!-4!\\ A\cap B&\text{has no cat and has no dog}&(8!-6!)+(8!-6!)-(8!-4!)\\ \end{array}$

The phrasing you used "How many arrangements of this word are there so that "cat" OR "dog" do not appear?" reads to me that you are looking for $A\cup B$, i.e. cat does not appear or dog does not appear.

Your answer was for the related but different question of "How many arrangements of this word are there so that "cat" AND "dog" do not appear?", i.e. neither cat nor dog appear, i.e. $A\cap B$.

Answer 2

Your work seem perfectly good to me.

Answer 3

The word cat could be in $6$ possible places \begin{eqnarray*} cat \underbrace{*****}_{5!} \end{eqnarray*} so there are $6!$ permutations with the word cat & similarly for dog.

There are $6$ ways to have cat followed by dog \begin{eqnarray*} catdog \underbrace{**}_{2!} \end{eqnarray*} and $2!$ ways to arrange the last two characters (times this by $2$ for dog followed by cat) $24$.

Now inclusion exclusion gives $8!- 2 \times 6! + 24$. So your logic is sound.