0
$\begingroup$

I've been struggling to find how many words of length $n \geq 3$ over alphabet S = $\{a, b, c, d, e, f, g, h\}$ contain at least one of each of the letters $\{a, b, c\}$.

My thought process involved counting the total number of possible strings which is $8^n$ and then using the inclusion exclusion principle to subtract the union of the following sets:

  1. Strings of length $n$ formed from $\{d,e,f,g,h\}$ denoted $A_1$
  2. Strings of length $n$ formed from $\{d,e,f,g,h,a\}$ denoted $A_2$
  3. Strings of length $n$ formed from $\{d,e,f,g,h,a,b\}$ denoted $A_3$
  4. Strings of length $n$ formed from $\{d,e,f,g,h,b\}$ denoted $A_4$
  5. Strings of length $n$ formed from $\{d,e,f,g,h,b,c\}$ denoted $A_5$
  6. Strings of length $n$ formed from $\{d,e,f,g,h,c\}$ denoted $A_6$
  7. Strings of length $n$ formed from $\{d,e,f,g,h,a,c\}$ denoted $A_7$

which would then yield $8^n - |A_1 \cup A_2 \cup A_3 \cup A_4 \cup A_5 \cup A_6 \cup A_7|$. Is this reasoning correct?

$\endgroup$
0
$\begingroup$

There are a total of $8^n$ words of length $n$. From these, we must subtract those words that do not contain $a$, $b$, and $c$. Therefore, we must subtract the number of words in which at least one of these letters is missing from the total.

Let $A$, $B$, and $C$ denote, respectively, the set of words that contain $a$, $b$, and $c$. Let $A'$, $B'$, and $C'$ denote, respectively, the complements of $A$, $B$, and $C$. Then the number of bad words is $$|A' \cup B' \cup C'|$$ where $$|A' \cup B' \cup C'| = |A'| + |B'| + |C'| - |A' \cap B'| - |A' \cap C | - |B' \cap C'| + |A' \cap B' \cap C'|$$ Can you take it from here?

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Shouldn't it be intersections in $|A′|+|B′|+|C′|−|A′∪B′|−|A′∪C|−|B′∪C′|+|A′∪B′∪C′|$? $\endgroup$ – William Oct 31 '17 at 15:20
  • $\begingroup$ @William Absolutely. At least one of us was awake. $\endgroup$ – N. F. Taussig Oct 31 '17 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.