# How many numbers between 1 and 10,000,000 don't have the sequence 12? Inclusion-exclusion problem

I got the following question:

How many numbers between 1 and 10,000,000 don't have the sequence 12? This is an inclusion-exclusion problem. Sadly I didn't fully understand its concept, so I tried solving it logically. I would like to know if my solution is correct, and if possible, how to solve it using the inclusion-exclusion principle.

Thanks!

So I said lets first find the numbers that do include the sequence 12, and divided it into cases:

Between 1 and 99: $1\cdot 1=1$

Between 100 and 999: $1\cdot 1 \cdot 10$ + $9\cdot 1 \cdot 1=19$

Between 1000 and 9999: $1 \cdot 1 \cdot 10 \cdot 10 + 2\cdot 9 \cdot 10 \cdot 1 \cdot 1 = 280$

Between 10000 and 99999: $1 \cdot 1 \cdot 10 \cdot 10 \cdot 10 + 3\cdot 9 \cdot 10 \cdot 10\cdot 1\cdot 1=3700$

Between 100000 and 999999: $1 \cdot 1 \cdot 10 \cdot 10 \cdot 10\cdot 10 + 4\cdot 9 \cdot 10 \cdot 10\cdot 10\cdot 1\cdot 1=46000$

Between 1000000 and 9999999: $1 \cdot 1 \cdot 10 \cdot 10 \cdot 10\cdot 10\cdot 10 + 5\cdot 9 \cdot 10 \cdot 10\cdot 10\cdot 10 \cdot 1\cdot 1=550000$

So the total of numbers that don't include the number 12 is: 10000000-550000-46000-3700-280-19=9400001

I don't havea final answer so I don't know if that correct. Obviousy this solution lacks elegance, so I would like to know how solve this problem using the inclusion-exclusion principle.

-
Not sure if I know how to solve it efficiently or completely correctly, but as advice, take the between 1000-9999 range. I see what you did there: 1-2-X-X + X-1-2-X + X-X-1-2 = 1*1*10*10 + 9*1*1*10 + 9*10*1*1 = 280. But what if you had a number like 1212? That number overlaps in the first case and the third case, and you can only count it once, so that actually leaves you with 280-1 = 279, I hope that helps. –  mathguy May 11 '13 at 15:29
Yes I see now. Thank you! –  ohad May 11 '13 at 15:37
+1 for a well posed question and for showing your work –  JavaMan May 11 '13 at 16:40

So you have at most a 7-digit number (since 10,000,000 isn't a possibility): X-X-X-X-X-X-X, and the 12 can be in 6 different positions, so you have 1-2-X-X-X-X-X, X-1-2-X....,X-X-X-X-X-1-2. That is a total of $6*10^5 = 600,000$ different numbers. Now the hard part like I said above is finding the overlaps.

Suppose 12 were to appear twice, that means that we have 3 open spaces otherwise. How many ways can we reorder the two 12's and the extra 3 spots? That would be ${5\choose2} = 10$. Since the open spots can be $10^3$ different numbers, we end up with $10*10^3 =10,000$ overlaps.

Suppose 12 were to appear three times, that means we have 1 open space otherwise. How many ways can we reorder the three 12's and the extra spot? ${4\choose1} = 4$. Since the open spots can be 10 different numbers, we end up with $4*10 = 40$ overlaps.

However, if 12 were to appear three times, that means 12 also appears 2 times, and so instead of have $10,000$ overlaps (from the first overlap case), we actually have $10,000 - 40 = 9960$ total overlaps.

With $10,000,000$ different numbers, we end up with (total numbers - total overlaps) = $10,000,000 - (600,000-9960) = 9,409,960$ which I verified with Java.

-
I see. Thank you! Very nice solution. –  ohad May 11 '13 at 16:03
Regarding the number of different numbers that include 12. –  ohad May 11 '13 at 16:05
@mathguy good one. –  Uma kant May 11 '13 at 16:08

All right you are at the first step of the inclusion-exclusion principle. You have just counted those numbers in which 12 appears at least once but in the process have overcounted. Your solution counts $1212$ twice, $121212$ thrice and so on.

By inclusion-exclusion principle, No. of numbers w/o $12$ = Total no. of numbers - No. of numbers with $1$2 at least once + No. of numbers with $12$ twice - No. of numbers with $12$ thrice + No. of numbers with $12$ four times and so on.

Total no: $10,000,000$

• $12$ at least once: $6*10^5$
• $12$ at least twice: $(4+3+2+1)*10^3$
• $12$ at least thrice: $((2+1)+(1))*10^1$
• $12$ four times and so on $=0$
• so ans= $10000000-600000+10000-40=9409960$
-
Welcome to MSE! It really helps to format questions/answers using MathJax (see FAQ). Regards –  Amzoti May 11 '13 at 16:36

Keep track of the amount of $n$-digit numbers ending in $1$ and not ending in $1$, starting with $n=1$

$$v_1 = \begin{pmatrix} 1 \\ 8 \end{pmatrix}$$

so $1+8 = 9$ numbers in total. The vector for $(n+1)$-digit numbers ending in $1$ and not ending in $1$ that do not contain the sequence "$12$" can be obtained by a recursion:

$$v_{n+1} = \begin{pmatrix} 1 & 1 \\ 8 & 9 \end{pmatrix} v_n.$$

If $M$ is the matrix in the recursion above then there are $$\begin{pmatrix} 1 & 1 \end{pmatrix}(M^{n-1} + M^{n-2} + \dotsc + 1) \begin{pmatrix} 1 \\ 8 \end{pmatrix}$$ numbers of at most $n$ digits that do not contain the sequence "$12$". For $n=7$ this becomes

$$\begin{pmatrix} 1 & 1 \end{pmatrix}\begin{pmatrix}96031 & 106821 \\ 854568 & 950599 \end{pmatrix} \begin{pmatrix} 1 \\ 8 \end{pmatrix} = 9409959$$ and including the number $10^7$ the final answer is $9409960$. Based on the above one can find a simpler linear recursion for the amount $a_n$ of numbers of at most $n$ digits that do not contain the sequence "$12$", namely

$$a_0 = 0, a_1=9 \textrm{ and } a_{n+2} = 10 a_{n+1} - a_n + 8.$$

This produces the sequence

$$0, 9, 98, 979, 9700, 96029, 950598, 9409959, 93149000, 922080049, \dotsc$$

-