Number of strings over a set $A$

Question

How can I calculate the number of strings of length $10$ over the set $A=\{a,b,c,d,e\}$ that begin with either $a$ or $c$ and have at least one $b$ ?

Is it accomplished through some sort of combinatorial logic coupled with discrete mathematics?

Answer 1

HINT

1. Compute the $N$ number of such strings that begin with a or c.
2. Compute the number of such strings that have no b.
3. Compute the $M$ number of such strings that have at least one b from (2)
4. Compute the $X$ number of such strings that have at least one b and begin with a or c.
5. By inclusion/exclusion principle, you need $N+M-X$.

Answer 2

Yes, you are correct. Use constructive counting. Begin by selecting the first letter in the string, which you said could be either $A$ or $C.$ There are $2$ ways to do this.

Now our problem becomes: construct a string of length $9$ with at least one $B.$ We count this with complementary counting - how many strings can we make without a single $B?$ We have $4$ choices for each letter, and we must select $9$ letters. There are a total of $5^{9}$ strings (without any restrictions). Therefore, the number of valid strings is $5^{9} - 4^{9}.$

Our final answer is $\boxed{2 \cdot \left(5^{9} - 4^{9}\right)}.$

Answer 3

$$(\text{Number of strings of length }9\text{ with at least one }b)\\ = (\text{Number of strings of length } 9)-(\text{Number of strings of length }9 \text{ without }b) \\ = 5^9-4^9$$

So that $$\text{Number of strings of length }10\text{ that begin with either }a\text{ or }c \text{ and have at least one }b \\= 2(5^9-4^9)$$