# Counting travails

How many 7 digit numbers are there (no leading zero) in which the digits 6 & 9 occur together as 69 at least once. I am having difficulty in eliminating overcounting.

-

The string $69$ can occur starting in position $1,2,3,4,5$, or $6$. If the number has $69$ starting in position $1$, the remaining $5$ digits are completely arbitrary, so there are $10^5$ such numbers. If the $69$ starts in any of the other five possible positions, the leading digit cannot be $0$, so there are $9\cdot 10^4$ numbers for each of these five cases.

Of course some numbers, like $6906912$, have been counted more than once. What double counting is actually possible? A number can have $69$ twice if the starting positions are $\{1,3\},\{1,4\},\{1,5\},\{1,6\},\{2,4\},\{2,5\},\{2,6\},\{3,5\},\{3,6\}$, or $\{4,6\}$. Each of the first four of these possibilities includes $10^3$ numbers; each of the other six includes only $9\cdot 10^2$, since the leading digit cannot be $0$.

Finally, triple counting is possible if the three instances of $69$ start in positions $\{1,3,5\}$, $\{1,3,6\},\{1,4,6\}$, or $\{2,4,6\}$. Each of the first three of these cases includes $10$ numbers, and the last includes $9$.

Now just do the usual inclusion-exclusion calculation: we have

\begin{align*} (100000&+5\cdot 90000)-(4\cdot 1000+6\cdot 900)+(3\cdot 10+9)\\ &=550000-9400+39\\ &=540,639\;. \end{align*}

-
@Kanna: Thanks; fixed. – Brian M. Scott Mar 29 '12 at 4:24

This is probably a good candidate for inclusion-exclusion (at least, I can't think of another way that won't be about the same amount of work, but I'm sure someone else will come around and give one).

First: how many have at least one instance of $69$? There are six locations where it can be placed (positions one through six); in one of them (position one) there are $10^5$ ways to fill the remaining places, and in the other five there are $9\times 10^4$ ways of filling the remaining spaces; so $$10^5 + 5\times9\times 10^4.$$

But this overcounts those that have $69$ more than once; how many have at least two occurrences? There are ten ways to put at least two $69$s: four locations for the first copy; and then $4+3+2+1$ for the second depending where the first one is, for a total of $10$ places. In six of them, you have $9\times 10^3$ ways of filling the remaining slots, in four of them you have $10^4$ ways of filling the rest, so $$6\times 9\times 10^3 + 4\times 10^4.$$

But this removes too many times the few sequences were $69$ appears three times; if you have three copies of $69$, there are four locations where you can put the remaining digit (after all three, between the first two and the third, between first and the last two, or before all three); in three of the locations you have 10 possibilities, and on one you have nine possibilities. So there are $9+10+10+10$ ways for this to occur.

So the total is $$\Bigl( 10^5 + 45\times 10^4\Bigr) - \Bigl(54\times 10^3 + 4\times 10^4\Bigr) + \Bigl(39\Bigr).$$

-
@AndréNicolas: Oops; quite right; those are disjoint cases to be added. Thanks. – Arturo Magidin Mar 29 '12 at 4:24

Imagine $7$ boxes. If $69$ is to occur atleast once together as a pair, we have, $6$ ways of having it.

If you chose to put it into the $1$st and $2$nd box, then, the rest of the $5$ boxes have $10$ candidates for them. So, this leaves us with $10^5$ possibilities in this case.

In any other set up, we will have a first box, where there are $9$ possible candidates and the other boxes have $10$ candidates for them. So, $9 \times 10^4$ possiblities in each set up.

$$\text{Total numbers}=10^5+(5\times9\times10^4)=55\times 10^4$$

But we have over counted those that have two 69's in them. So, let's subtract them from this count.

If we had two 69's coming in, it must arise out of the following cases: For $i<j$, let's use $(i,j)$ to denote that $i^{th}$ place and $i+1^{th}$ places are filled by $6$ and $9$ respectively. And, similarly for $j$. Note that $j−1>1$.

$$\begin{array}{|c|c|}\hline (1,3); (1,4); (1,5); (1,6) & 4 \times 10^3\\ (2,4); (2,5); (2,6) & 3 \times 9 \times 10^2\\ (3,5); (3,6) & 2 \times 9 \times 10^2 \\ (4,6) & 9 \times 10^2\\ \hline \end{array}$$

So, $$\text{Total number we have to exclude}=9400$$

But, in this process, we subtracted those with three copies of $69$ in them. Again, let's use the notation of the previous kind:

$$\begin{array}{|c|c|}\hline (1,3,5); (1,3,6) ; (1,4,6) & 3 \times 10\\ (2,4,6) & 9 \\ \hline \end{array}$$

The $$\text{Total numbers you will include}= 39$$

So, the total numbers:

$$\text{Total Numbers with the property}=550000-9400+39=\boxed{540639}$$

-