No 13 in the sequence

Question

There are "n" boxes, inside each box we can place the digits 0-9... the only restriction is that the substring "13" cannot occur at any place in sequence.

For example, take n = 3; and so total possibilities is 10*10*10 = 1000. Now I need to remove possibilities with "13" so,

1. Fixing the first two boxes to "13", there are 10 possibilities for the third box.
2. Fixing the second and third boxes to 1 and 3 in that order also gives 10 possibilities.

So there are 10+10 = 20 numbers containing "13", and 1000-20=980 numbers without it.

And my problem is for n = 4 i got 9700, but the answer is wrong ): . Where did I do something wrong? Or are there any other approaches you can suggest?

Answer 1

Your solution with n=4 is almost correct, but it removes the number "1313" twice: once in when you fix the first two digits, and the second time when you fix the last two. This is the only string with this property, so adding it back in the correct answer for n=4 will be 9,701.

In general, you'll need to use some kind of inclusion-exclusion principle to account for such numbers. For example, with n=5, you have

1. +100000 initial numbers (inclusion)
2. -1000 for numbers starting with 13 (exclusion)
3. -1000 numbers with "13" starting at the second digit (exclusion)
4. -1000 numbers with "13" starting at the third digit (exclusion)
5. -1000 numbers with "13" starting at the fourth digit (exclusion)
6. +10 numbers starting with 1313 (inclusion)
7. +10 numbers ending with 1313 (inclusion)
8. +10 numbers of the form 13?13, where ? is any digit (inclusion)

Which totals 96,030. For n=6, you'll need another round of exclusions to account for "131313".