4
$\begingroup$

The question is "How many strings of six lower case letters from the English alphabet contain the letters $a$ and $b$?"

Why doesn't $26^6 - 24^6$ work?

$26^6$ is all the possible permutations of $26$ letters MINUS all permutations without $a$ nor $b$.

$\endgroup$
9
$\begingroup$

You want to count the strings the contain $a$ AND $b$. What you should subtract is thus the number of strings that don’t contain both $a$ and $b$, meaning that they are allowed to contain $a$ but not $b$, and $b$ but not $a$.

$\endgroup$
2
$\begingroup$

For your mistake see the answer of Mankind.

This answer tells you how to do it correctly.


Let $A$ denote the collection of strings that do not contain letter $a$ and let $B$ denote the collection of strings that do not contain letter $b$.

Then the number of strings that contain letter $a$ and letter $b$ equals: $$|A^{\complement}\cap B^{\complement}|=26^6-|A\cup B|=26^6-|A|-|B|+|A\cap B|=26^6-2\cdot25^6+24^6$$

Further for completeness observe that: $$|A^{\complement}\cup B^{\complement}|=26^6-|A\cap B|=26^6-24^6$$counting the number of strings that contain letter $a$ or letter $b$ (where it is allowed to contain both).

$\endgroup$
  • $\begingroup$ Still waking up. Thanks. $\endgroup$ – N. F. Taussig Sep 17 at 8:28
1
$\begingroup$

When facing a problem like this solve it for small numbers.

Our alphabet is {a,b,c}. How many 2 character long strings? $3^2 = 9$. What are they?

aa
ab
ac
ba
bb
bc
ca
cb
cc

How many 2 character long strings with a or b? $1^3 = 1$. It is ccc.

How many 3 character long strings with both a and b?

ab
ba

2. Using your method, you would get 9-1=8. Now, that minus is actually taking a specific one way, so we can see what 8 we counted here:

aa
ab
ac
ba
bb
bc
ca
cb

we can see that we counted every string with either an a or a b, not string that have both.

Now we can count strings that do contain a single letter this way. If we take away the lines that don't contain a:

aa
ab
ac
ba
bb
bc
ca
cb
cc

minus:

bb
bc
cb
cc

We get $3^2 - (3-1)^2 = 5$:

aa
ab
ac
ba
ca

which is the right answer for the number of 2 character strings that contain a.

$\endgroup$

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.