# combinatorics problem - permutations and e/i

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!

• When you say "so that 'cat' OR 'dog' do not appear," do you mean "so that either 'cat' does not appear or 'dog' does not appear," or do you mean "so that neither 'cat' nor 'dot' appears"? – Y. Forman Jan 26 '18 at 20:01

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

• I think this is what the OP intended -- the quantity he is looking for is the number of arrangements in which neither "cat" nor "dog" appear. – Y. Forman Jan 26 '18 at 19:57
• @Y.Forman Quoted from the OP "How many arrangements of this word are there so that "cat" OR "dog" do not appear?" This is a different phrase than "How many arrangements... so that NEITHER "cat" NOR "dog" appear" The one is $A\cup B$ using his notation. The other is $A\cap B$. – JMoravitz Jan 26 '18 at 19:59
• I read "OR" as "nor." What OP wrote was also a different phrase than "...so that either "cat" does not appear, or "dog" does not appear." I think the OP should clarify. – Y. Forman Jan 26 '18 at 20:01
• I meant it as either cat does not appear or dog does not appear. – rachelhoward Jan 26 '18 at 20:54
• I will choose this as the answer to my post because it points out that my set C does contain dog or cat but not both. I had overlooked this. – rachelhoward Jan 26 '18 at 20:58

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.

Your work seem perfectly good to me.