Combinatorics - Fixing my logic for "Strings of length n"

Question

I can find the answers to similar questions online, but what I'm trying to do is develop my own intuition so I can find the answers. I am quite sure I am wrong, so could you look over my reasoning?

If $X = (1,2,3,4,5,6,7,8)$,

1. How many strings over X of length 5?

Reasoning: Each character of the string is a choice of a selection from the string, so $8^5$.

2. How many strings over X with length 5 don't contain $1$?

Reasoning: This is equivalent to strings of length 5 of an alphabet not containing $1$, so $7^5$.

3. How many strings over X with length 5 contain $1$?

Reasoning: First get the strings for length 4 ($8^4$). Then select a position to insert a 1 ($5$). Compounded: $5\times 8^4$.

At this point I saw $8^5 \ne 7^4 + 5 \times 8^4$ and lost motivation. I am more sure 1 and 2 are correct than 3 so perhaps the simplest solution would be just $8^5-7^5$, but my logic for 3 "feels" sound. I am frustrated because I have never had these kinds of difficulties before. I look at solutions and though they too "feel" correct, I'd not have come up with them.

I apologize for the irregular question form, and understand if this isn't the site for this.

Answer 1

The problem with the third argument is that it counts some valid strings twice (or more).

For example the string 12341 is counted as [1][2341] and [1234][1].

The other way (subtracting the number of strings without '1's from the number of total strings) is correct, and it's indeed the simplest way.

Elsewhere, you could correct the overcounting by inclusion-exclusion :

$$ \binom51 8^4 - \binom52 8^3 + \binom53 8^2 - \binom54 8^1 + 1 = 15961 $$

Alternatively, you could count all the strings with exactly $1,2 \cdots 5$ ones, as in @drhab's answer.

BTW: you say

At this point I saw $8^5 \ne 7^4 + 5 \times 8^4$ and lost motivation.

You definitely shouldn't. On the contrary, to fall into that "trap" (and to realize there's something is wrong, and learn why) is rather the point of this problem.

Answer 2

What you call simplest solution is a correct one (and by far the most simple and elegant one).

If you still insist to go the other direction then your answer must be:$$\binom51\times7^4+\binom52\times7^3+\binom53\times7^2+\binom54\times7^1+\binom55\times7^0=15961$$

Here $\binom5{k}$ is the number of ways to choose $k$ ones among $5$ candidates.