Discrete math [Counting]

Question

How many passwords of exactly $8$ upper case letters contain:(a) the letter $X$? (b) the letters $X$ and $Y$?

For the first one the answer I have written is $26^7$ as one spot is occupied by $X$ but I am still not sure of it. Help would be appreciated!

Answer 1

There are altogether $26^8$ passwords of $8$ letters. Of these, $25^8$ contain no X. So $26^8-25^8$ do contain X. (You might find it instructive to check that this agrees with the sum obtained by Paul Childs in his answer.)

To count the passwords that contain both X and Y, start with all $26^8$ passwords as above; subtract off $25^8$ that don't contain X and another $25^8$ that don't contain Y; realize that words that contain neither X nor Y have been subtracted off twice; so add those $24^8$ words back on. So you get $26^8-(2\times 25^8)+24^8$.

Answer 2

For a

With X in position 1 there are 26^7 possibilities.

With X in position 2 and not X in position 1 there are 25 * 26^6 possibilities.

Sum = 26^7 + 25*26^6 + 25^2 * 26^5 + ... + 25^7

Answer 3

There are several ways to approach this problem. You can do it directly, as Paul did in his answer. You can look at the complement of each set (i.e. passwords that don't contain the letter $X$ and those that don't contain $X$ and $Y$). You can use inclusion-exclusion (look at how many strings contain at least $k$ of the letter $X$ and sieve to get the number containing exactly $k$).

The problem with $26^7$ as an answer is that it doesn't account for where the $X$ is in the string. Note that we have $8$ different sets of size $26^7$:

• Strings of the form $X*******$
• Strings of the form $*X******$
• Strings of the form $**X*****$
• etc.

But there are overlaps. For example, the string $XABCXDEF$ is in both the first and fourth set.

You can account for this using inclusion-exclusion or you can be careful making sure that your second set doesn't overlap the first and the third doesn't overlap the first two, etc.

However, take note that these methods of counting become more complicated when you're looking at both $X$ and $Y$. The second method I mentioned (looking at complements) makes both problems easy. But you should keep all methods in mind to build up a good toolbox for solving counting problems.