Counting words from 3 letter alphabet based on various conditions.

Question

Please let me know if you can find any mistakes and explain corrections to my work.

This exercise is verbatim a Discrete Math professor's assignment.
Let $$W= \lbrace w \in \lbrace a, b, c \rbrace ^∗: |w| = 8 \rbrace $$ Find the number of words $w \in W$ with the following properties. You response should include a boxed numerical answer (use a calculator if needed) and justification for how you computed it. [ He then elaborates on what quality answers look like, mostly asking to explain your reasoning.]

(a) No two adjacent characters in w are the same.
(b) w contains at most 2 different characters.
(c) w contains at least 5 b's.
(d) w matches the regular expression $a^∗b^∗c^∗$.
(e) Every a in w is to the left of every c in w.
(f) w contains the subword “cab” (in consecutive positions).

My answers follow.
A. Number of choices for each position $3 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 = 3 \cdot 2^7$

B. Consider the alphabet $\lbrace d,e\rbrace$. Count of 8 letter permutations from this alphabet is $2^8$ There are $_{3}C_{2}$ combinations from a,b,c to d, e. So $2^8\cdot \space_{3}C_{2} = 768$

C. Let n = count of b's, $n \geq 5$ Most 2's below are from a choice of a or c.

n	Elaboration	Count
5	(Count of locations for a,c) $\cdot 2^{8-n}$ See ** below.	$\space_{8}P_{5} \cdot 2^{8-5} $
6, 7, 8	Similar, but use n	$\space_{8}P_{n} \cdot 2^{8-n} $

** This count is
(8 choices for 1st a or c) $\cdot$ (7 choices for 2nd a or c) $\cdot$ (6 choices for 3rd a or c)
$\cdot 2^{8-n}$ $\space_{8}P_{n} \cdot 2^{8-n} $ The sum is $$\sum_{i=5}^8 \space_{8}P_{i} \cdot 2^{8-i} = 2929$$

D. Essentially this is, where do we put the $a \to b$ transition, then where to put the $b \to c$ transition? I'll name the transition locations, $0.5, 1.5, \dots 8.5$ because they fall between letter positions, 1 to 8.

$$ \begin{array}{c c} a \to b & \text{count of $b \to c$ choices}\\ \hline 0.5 & 9\\ 1.5 & 8\\ 2.5 & 7\\ \vdots & \vdots\\ 8.5 & 1 \end{array} $$

$$\sum_{i=1}^9 i =45$$ I realize this can also be done with a stars and bars approach, but I'll study that more thoroughly later.

E. Essentially the alphabet is {ac, b} Let n = count of ac's.

$$ \begin{array}{c c c} n & \text{letters in the word} & \text{count}\\ \hline 4 & ac, ac, ac, ac & 1\\ 3 & ac, ac, ac, b, b & \dfrac{5!}{3!2!}\\ 2 & ac, ac, b, b, b, b & \dfrac{6!}{4!2!}\\ 1 & ac, b, b, b, b, b, b & \dfrac{7!}{6!1!}\\ 0 & b^8 & 1 \end{array} $$

The sum is $34$.

F. Consider one "cab", for example cab_ ____, with 6 choices for where to put cab and $3^5$ choices for the other letters.

However, this includes duplicates of cab as in "cab cab _ _".

$$ \begin{array}{c c} \text{first cab} & \text{first cab} \cdot \text{choices for second cab} \cdot \text{other letters} & \text{count}\\ cab \text{_____} & 1 \cdot 3 \cdot 3^2 & 27\\ \text{_} cab \text{___} & 1 \cdot 2 \cdot 3^2 & 18\\ \text{__} cab cab & 1 \cdot 1 \cdot 3^2 & 9 \end{array} $$

Count of words with two "cab"'s = $27 + 18 + 9 = 54$

[corrected previous $3^6$] (Count of one cab) minus (count of two cabs) is $3^5 \cdot 6- 54 = 1404$

Thankfully, there are at most two "cab"'s in an 8 letter word. Imagine the same question, but using "cac" instead of cab". This "cac", can overlap, as in "cacacac_" which has 3 "cac"'s.

Answer 1

Let $$W= \lbrace w \in \lbrace a, b, c \rbrace ^∗: |w| = 8 \rbrace $$ Find the number of words $w \in W$ with the property that no two adjacent letters are the same.

Your answer is correct.

Find the number of words in $w$ that contain at most two different characters.

Your answer is incorrect since you have counted each word with only one letter twice, once for each pair of letters in which that letter appears.

There are three words which use only one letter.

There are three ways to exclude one of the letters. There are $2^8$ words that can be formed using the remaining two letters, of which $2$ use only one letter. Hence, there are $3(2^8 - 2)$ words that use exactly two letters.

Hence, there are $3 + 3(2^8 - 2) = 3 \cdot 2^8 - 3$ words which use at most two letters.

Find the number of words that contain at least $5$ $b$s.

Your answer is incorrect since the $b$s are indistinguishable.

There are $\binom{8}{k}$ ways to select exactly $k$ positions for the $b$s and $2^{8 - k}$ to fill the remaining $8 - k$ positions with $a$s or $c$s. Hence, the number of words with at least $5$ $b$s is $$\sum_{k = 5}^{8} \binom{8}{k}2^{8 - k} = \binom{8}{5}2^3 + \binom{8}{6}2^2 + \binom{8}{7}2^1 + \binom{8}{8}2^0$$

Find the number of words that match the regular expression $a^*b^*c^*$.

It is my understanding that the regular expression must include zero or more occurrences of $a$ followed by zero or more occurrences of $b$ followed by zero or more occurrences of $c$, in which case your answer is correct.

Alternatively, such a word is completely determined by how many $a$s, $b$s, and $c$s occur since the letters must appear in alphabetical order. Let $x_i$ denote the number of times the $i$th letter in the alphabet appear. Then we want to find the number of solutions of the equation $$x_1 + x_2 + x_3 = 8$$ in the nonnegative integers.

A particular solution of that equation corresponds to the placement of two addition signs in a row of eight ones. For instance, $$1 1 + 1 1 1 1 1 + 1$$ corresponds to the solution $x_1 = 2, x_2 = 5, x_3 = 1$, while $$1 1 1 1 1 + 1 1 1 +$$ corresponds to the solution $x_1 = 5, x_2 = 3, x_3 = 0$. The number of such solutions is the number of ways we can place two addition signs in a row of eight ones, which is $$\binom{8 + 3 - 1}{3 - 1} = \binom{10}{2} = 45$$

Find the number of words in which every $a \in W$ appears before every $c \in W$.

You have misinterpreted the question. All the $a$s must appear before all the $c$s. Thus, a word such as $abaacbcb$ is acceptable, while a word such as $acbacbac$ is not.

I suggest that you tackle the problem by considering cases depending on the number of $b$s that appear in the word, then using your strategy in part (d) to count the number of ways you can make a transition from $a$s to $c$s in the remaining positions. Keep in mind that in a word with no $c$s, all the $a$s appear before all the $c$s. Likewise, in a word with no $a$s, all the $a$s appear before all the $c$s.

Find the number of words in which $w$ contains the subword $cab$.

Your now revised work is correct.