Calculating number of strings I am stuck on this problem I think I need to use the "Inclusion-Exclusion" principle to solve I am hoping that someone could give me some useful pointers.
I have a string of length 100 and each character of the string is a digit or a lower case letter. This string has 3 rules that it cannot start with qwe, and it cannot end with thl, and it cannot start with 5709.
So what I have done so far is:
All possible characters is 10 (digits) + 26 (lower case characters) = 36.
So first rule there are A: 36^97 possible combinations, second rule there are B: 36^97 cominations, and third rule there are C: 36^96 combinations.
Then using inclusion-exclusion rule I do
$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C|$
= 36^97 + 36^97 + 36^96 - (36^94) - (36^97) - (36^93)
This doesnt seem right to me
 A: It seems you have sets:
\begin{eqnarray*}
A &=& \text{"Strings starting with 'qwe'"} \\
B &=& \text{"Strings ending with 'thl'"} \\
C &=& \text{"Strings starting with '5709'".} \\
\end{eqnarray*}
You want the number of strings belonging to none of these sets, which is:
\begin{eqnarray*}
\left| A^c\cap B^c\cap C^c\right| &=& \left|\left( A\cup B\cup C\right)^c\right| \\
&=& |\Omega| - (|A|+|B|+|C|) + (|A\cap B| + |A\cap C| + |B\cap C|) - |A\cap B\cap C| \\
&&\qquad\text{by Inclusion-Exclusion} \\
&=& 36^{100} - (36^{97} + 36^{97} + 36^{96}) + (36^{94} + 0 + 36^{93}) - 0 \\
&=& 36^{100} - 2\times 36^{97} - 36^{96} + 36^{94} + 36^{93}.
\end{eqnarray*}
$$\\$$
Another approach to the problem is to break the $100$ characters into:


*

*the first $4$

*the next $93$

*the last $3$


and count the number of ways each component doesn't break any rule.


*

*"First $4$" can occur in $36^{4} - 36 - 1$ ways: $36$ break rule $A$ ('qwe*') and $1$ breaks rule $C$ ('5709').

*"Next $93$" can occur in $36^{93}$ ways.

*"Last $3$" can occur in $36^{3} - 1$ ways: 'thl' breaks rule $B$.
So the required number is the product of these three values:
$$(36^{4} - 37)(36^{93})(36^{3} - 1)$$
which equals the result above.
