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

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

• What have you overcounted? How about the string 0 1 2 3 4 5 6? You counted it once when you noticed it had 0 1 2 3 4 in it, you counted it again when you noticed it had 1 2 3 4 5 in it, and again when you noticed it had 2 3 4 5 6 in it. Similarly so for any other string with more than 5 consecutive digits in a row. Sep 27, 2018 at 5:53
• This problem is a good setting to apply the Inclusion-Exclusion principle.
– Carl
Sep 27, 2018 at 5:58
• The standard way to correct the overcounting is called the inclusion-exclusion principle. Sep 27, 2018 at 6:01
• Can you please @Carl or Arthur show me how you would use inclusion exclusion principle ?
– user487078
Sep 27, 2018 at 6:07
• the question should be more defined(wording is not precise) as Compute the number of sequence that contain only a 5-digit consecutive substring or Compute the number of sequence that contain at least a 5-digit consecutive substring. here first one would restrict a 6 or 7 digit substring while the second question would allow those Sep 27, 2018 at 6:20

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) .$$

• @StackExangeLearner Is it clear now how to use PIE? Sep 28, 2018 at 12:47

You are counting some strings twice.

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