Compute the number of 7-digit sequences that contain a 5-digit consecutive substring

Question

Let say any 7-digit sequence, even 0000000 is a valid number. Compute the number of sequences that contain a 5-digit consecutive substring. For example “23456” and “12345”?

Approached it as (where X can be (0-9)) : Which gives me a total as 1800, however the answer is 1700. Can you please point out what I over-counted and share a wise way to approach similar question ?

 0 1 2 3 4 X X 
 1 2 3 4 5 X X
 2 3 4 5 6 X X
 3 4 5 6 7 X X
 4 5 6 7 8 X X
 5 6 7 8 9 X X 

 X 0 1 2 3 4 X  
 X 1 2 3 4 5 X 
 X 2 3 4 5 6 X 
 X 3 4 5 6 7 X 
 X 4 5 6 7 8 X 
 X 5 6 7 8 9 X

 X X 0 1 2 3 4  
 X X 1 2 3 4 5 
 X X 2 3 4 5 6 
 X X 3 4 5 6 7 
 X X 4 5 6 7 8 
 X X 5 6 7 8 9

Answer 1

Yes, you are overcounting the number of such strings: for example $0 1 2 3 4 5 6$ is counted three times: as a member of $0 1 2 3 4 X X$, of $X 1 2 3 4 5 X$, and of $X X 2 3 4 5 6$.

As explained by the comments the right tool to use is the inclusion-exclusion principle.

Hint. Let $S(01234)$ be the set of 7-digit sequences which contain a copy of the string $01234$ then, from your scheme, $$|S(01234)|=3\cdot 10\cdot 10=300.$$

By the inclusion-exclusion principle, the number of 7-digit sequences such that contain at least a 5-digit consecutive substring in increasing order is $$\begin{align}&|S(01234)|+|S(12345)|+\dots+|S(56789)|\\&- |S(012345)|-|S(123456)|-\dots-|S(456789)|\end{align}.$$ P.S. In order to apply the inclusion-exclusion principle you should consider the intersections of the sets $S(\cdot)$. Note that $$S(01234)\cap S(12345)=S(012345),\\ S(01234)\cap S(23456)=S(0123456),\\ S(01234)\cap S(34567)=\emptyset,\\ S(01234)\cap S(12345)\cap S(23456)=S(0123456) .$$

Answer 2

You are counting some strings twice.

For example, $$xx56789$$ and $$x45678x$$ both results in $$3456789$$