I was going though a course on edx.org and there the instructor counted $5$ different instances like
- $1 2 3$ _ _ _ _$ = 10^4$
- _ $1 2 3 $_ _ _ $= 9\times10^3$
- _ _ $1 2 3 $_ _ $= 9\times10^3$
- _ _ _ $1 2 3$ _$ = 9\times10^3 - 10$
- _ _ _ _ $1 2 3 $ $= 9\times10^3 - 10 - 9$
And add all of them. I understood what the instructor did here. But what she did was manually count the exceptions.
Would I also do it manually in case the number of digits are $10 $or $15 $or may be $20 ?$ I think it would be very tedious. There should some standard solution rather than manually revisiting what the exceptions are. What is the standard solution and also explain please?
You want to count the words on alphabet $\{0,1,\dots,9\}$ that do not start with $0$ and do contain the word $123$ at least once. We apply the principle of inclusion-exclusion.
The first term in inclusion-exclusion considers the placement of one $123$. If the $123$ appears first, there are $10^4$ completions. If the $123$ appears in one of the other $4$ positions, there are $9\cdot10^3$ completions. If we stop here, we have overcounted when $123$ appears more than once.
The second term in inclusion-exclusion corrects for this overcount by subtraction. There are three cases where $123$ appears (at least) twice:
The first two cases yield $10$ each, and the third case yields $9$.
Because $123$ cannot appear more than twice in a word of length $7$, we are done. Putting it all together, we have $$(10^4+4\cdot9\cdot10^3) - (2\cdot10+9) = 45971$$ such words, in agreement with the instructor's five cases.
This same approach works for larger numbers of digits, but there will still be some casework to account for the "cannot begin with $0$" rule.
OEIS entry A328916 gives recurrence $$a_n = 10 a_{n-1} + 9\cdot10^{n-4} - a_{n-3},$$ which you can derive by conditioning on whether or not the first $n-1$ digits contain $123$.