Following question:
How many sequences of the letters $ E, H, I, R, S , W $ are there where there are no subsequences $ WIR $ , $ IHR$ and $ SIE $
for example: $RSEWIH$ is valid, but $ RSWIHE$ is not valid since there is the subsequence $ SIE$
I guess I need to use the inclusion and exclusion principle. So having
$ |A| $- Number of words containing $IHR$
$|B|$- Number of words containing $WIR$
$ |C| $- Number of words containing $SIE$
$ |A \cap B |$ - $IHR $ & $ WIR$
$|A \cap C | $ - $IHR$ & $ SIE $
$ |B \cap C |$ - $WIR $ & $ SIE $
$ |A \cap B \cap C |$ - $ IHR $ & $ WIR $ &$ SIE$
so the total amount would be
$6! - (|A|+ |B|+|C|) + (|A \cap B | + |A \cap B | + |B \cap C |) - |A \cap B \cap C | $
I have trouble determining the amount of words which contain those subsequences.
I appreciate any help!
Given any arrangement we have six ways of repermuting the letters $W,I,R$ in it, only one of which will have the subsequence $WIR$; a similar argument applies for the other two words. Hence $|A|=|B|=|C|=6!/3!=120$.
There is only one length-$4$ word containing $WIR$ and $IHR$, which is $WIHR$. There are four length-$5$ words containing $WIR$ and $SIE$, and three length-$5$ words containing $IHR$ and $SIE$. There are six arrangements containing all three words (since we can add the $S$ before the $I$ in $WIHR$ in two positions, and $E$ after $I$ in three). Hence by similar logic as in the first cases $$|A\cap B|=1\cdot\frac{6!}{4!}=30$$ $$|A\cap C|=3\cdot\frac{6!}{5!}=18$$ $$|B\cap C|=4\cdot\frac{6!}{5!}=24$$ $$|A\cap B\cap C|=6$$ and $$|A\cup B\cup C|=720-3\cdot120+30+18+24-6=426$$