# Permutation with repetition and condition

Given an integer $N$, Find how many strings of length $N$ are possible, consisting only of characters A, B, C with each character occuring at least once.

Solution: Lets place A,B,C (at least once) in the first three places. They can be arranged in $3!=6$ ways. Now the remaining $N-3$ places can be arranged in $3^{N-3}$ ways [Since any of A,B,C can come in $N-3$ places]. Again, taking the first three places A,B,C as one, we can permute the string of length $N-2$ in $(N-2)!$ ways. So there would be a total of $$6 \times 3^{N-3} \times (N-2)!$$strings possible. What am I doing wrong here?

The third is a massive overcount in that you're permuting all the $N-3$ letters even though you've already counted all possible choices for them, and the permutations are generating all those choices over again.
A correct solution would be, using inclusion-exclusion: There are $3^N$ strings in all. From these we have to subtract $3\cdot2^N$ that contain only two of the letters ($3$ because there are $3$ pairs of letters). But now to properly count the $3\cdot1^N=3$ sequences that contain only one letter, which we've counted once and subtracted twice, we have to add them back in, for a total of $3^N-3\cdot2^N+3$.