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.

  • $\begingroup$ Arghhh, my tables show up fine in the preview, but are broken, not showing correctly in the public version. Ideas- what would cause that and how do I fix it? $\endgroup$
    – nickalh
    Nov 8, 2022 at 22:51
  • $\begingroup$ You can use an array. See this MathJax tutorial. $\endgroup$ Nov 8, 2022 at 23:29
  • $\begingroup$ The way I read part (e) is that all the $a$s in a word must precede all the $c$s in a word, so $baabacbc$ is permissible but $acbbacbb$ is not. $\endgroup$ Nov 8, 2022 at 23:52
  • $\begingroup$ @N.F.Taussig Awww, nuts, I think you're right. My interpretation would be more "Each c is preceded by an a." Great catch, unfortunately, I spent too much time typing the answers and don't know an effective or quick answer (e) now. $\endgroup$
    – nickalh
    Nov 9, 2022 at 0:19

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

  • $\begingroup$ On Part B, "Hence, there are $3(2^8−2)$ words that use exactly one letter." makes no sense and contradicts "There are three words which use only one letter." which is correct. Perhaps your first sentence should be "Hence, there are $3(2^8−2)$ words that use exactly two letters." I agree with your ultimate conclusion. $3*(2^8 -2) $ $\endgroup$
    – nickalh
    Nov 10, 2022 at 1:22
  • $\begingroup$ Thank you for correcting the error. $\endgroup$ Nov 10, 2022 at 2:26
  • $\begingroup$ Why did you delete my section headers? I had significant difficulty finding the correct section, with lots of scrolling back and forth. $\endgroup$
    – nickalh
    Nov 11, 2022 at 19:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .