How many numbers up to 10^10 have a certain number a substring How do I calculate how many numbers up to 10^10 have 234 as a substring?
For example, 12341 has 234 as a substring. So does 234 and 2342341.
 A: For $n \geq 0$ let $v_{n} \in \mathbb{Z}^4$ count four categories of $n$-digit numbers (allowing leading zeroes):


*

*$v_{n,1}$ is the amount not containing the sequence $234$ and not ending in $2$ or $23$.

*$v_{n,2}$ is the amount not containing the sequence $234$ and ending in $2$.

*$v_{n,3}$ is the amount not containing the sequence $234$ and ending in $23$.

*$v_{n,4}$ is the amount containing the sequence $234$.


Then $v_0 = (1,0,0,0)$. Let $M$ be the $4 \times 4$ matrix given by
$$M = \begin{pmatrix}
9 & 8 & 8 & 0 \\
1 & 1 & 1 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 10
\end{pmatrix}$$ then the vectors $v_n$ satisfy the recursion $$v_{n+1} = M v_n.$$  The amount $a_n$ of $n$-digit numbers (allowing leading zeroes) containing $234$ is therefore $$ a_n = \begin{pmatrix}0 & 0 & 0 & 1 \end{pmatrix} \, M^n \, \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix}.$$ Now $M$ satisfies (according to its characteristic polynomial) $$ M^4 - 20 M^3 + 100 M^2 + M - 10$$ and therefore the sequence $a_n$ satisfies the linear recurrence $$ a_{n+4} = 20 a_{n+3} - 100 a_{n+2} - a_{n+1} + 10 a_n.$$  This results in the sequence (starting at $a_0$) $$0, 0, 0, 1, 20, 300, 3999, 49970, 599400, 6990001, 79850040.$$  So the amount of $10$-digit numbers containing the sequence $234$ is $79850040$.
A: Short answer: there are 8 places for the '234', and $10^7$ ways to fill the other digits.
Longer answer: that counted those with two '234's twice.  Place two '234's in the ten spaces, and fill the four remaining digits.  Subtract this from the first answer.
Even longer answer: those with three '234's were counted three times, then deleted three times.  Add them back in.
