Inclusion and Exclusion how many n-strings with a,b,c and d

Question

There are n different characters namely a, b, c, d. Use them to compose n-length string. Count the number of different n-length strings which at least contain one a, one b and one c.

My previous idea is like: Set A contains strings with at least one a. Similarly we have set B and C. So |A| = |B| = |C| = n * 4^(n-1). Firstly, choose one place of n (n possibilities) to set it to character a. Then n-1 places left with 4^(n-1) possibilities.

But some guys say this is not right. He suggests that the right answer should be |A| = |B| = |C| = 4^n - 3^n. Could you guys explain why it does not work?

---

EDIT 1:
I think there is a rule out there that I should follow when counting this kind of permutations. I need to find it out. Otherwise, I would make similar mistake next time without consciousness. It is essential to summarize the tip when and how I avoid this kind mistake.

Could someone figure the rule out?

---

EDIT 2
I think there is rule somehow:
When counting elements with property P, we cannot split the counting process into pieces. That is to say we cannot split property P into P = P1 + P2 + ... + Pk. This usually repeats one element several times.

For the above problem, I split the number of at least 1 a of a n-length string into two sub-properties as 1 a and 0 and/or more a's. This will repeatedly count some strings with more than 1 a. Like n = 5, abcaa will be counted 3 times since it has 3 a's.

Answer 1

Suppose that $n=5$, and consider the string $aaabc$. You count this once as $\underline{a}aabc$, once as $a\underline{a}abc$, and yet a third time as $aa\underline{a}bc$, where in each case the underlined $a$ is the one that you chose first, and the other four characters were chosen as one of the $4^{5-1}$ possibilities for. Thus, you’ve counted the same string three times in your figure of $n\cdot4^{n-1}$. In general you’ll find that if a string has $k$ copies of the letter $a$, it gets counted $k$ times in your figure of $n\cdot4^{k-1}$. Thus, you are badly overcounting the number of strings containing at least one $a$.

There are $4^n$ strings of length $n$ altogether, and there are $3^n$ strings of length $n$ containing no $a$, so there are actually $4^n-3^n$ strings of length $n$ containing at least one $a$.

Answer 2

You will be double counting many strings. For example, suppose that (out the $n$ ways to place character a), you decide to put it at the first position. The remaining positions don't matter, so you could, for example, make the entire string all a's. That's one string. But according to your strategy, you could also have placed the initial character a at, say, the second position. Since the remaining positions don't matter, it is possible to again make the entire string all a's. Thus, you have double counted.

Answer 3

So $n=4$ and there are $4^4=256$ strings. You can either have a permutation of $abcd$, of which there are $4!=24$ or you can have two of one and one each of the others. For that, you have $3$ ways to select the duplicated letter, ${4 \choose 2}=6$ ways to choose the positions for that letter, and $2$ ways to place the other two. So we have $24+3\cdot 6 \cdot 2=60$ successes.