# How many 10 digit phone numbers have at least one of each odd digit?

How many 10 digit phone numbers have at least one of each odd digit?

$1,3,5,7,9 = 5!*10^5$

I hope this is right. Or did I double count?

-
I don't think you've counted enough. I believe $5! 10^5$ would give the number of 10 digit phone numbers whose first 5 digits correspond to $1,3,5,7,9$ (in some order) and whose final 5 digits are anything. This would miss numbers like $1111113579$. –  Bill Cook Feb 22 '12 at 19:14
Your procedure does not give the right answer for much smaller cases (like $3$-digit numbers, from digits $1$, $2$, $3$, at least one of each odd digit). –  André Nicolas Feb 22 '12 at 19:17
But of course, ten digit phone numbers as they appear in the US have more constraints, such as not beginning with 0 or 911 and a whole slew of similar restrictions (which may be getting fewer, as new area codes come into existence). But then we are of course out of the realm of mathematics … –  Harald Hanche-Olsen Feb 22 '12 at 21:38

Note that "$1,3,5,7,9 = 5!\times 10^5$" is nonsense as written. I don't know what the left hand side is supposed to be, but $5!\times 10^5$ is not equal to $9$, and is not equal to the sequence of the five odd numbers $1$, $3$, $5$, $7$, and $9$.

And the count is completely off, as many have mentioned.

One possibility is to use inclusion-exclusion: there are $10^{10}$ possible phone numbers; how many have no $9$s in it? $9^{10}$; same for numbers with no $7$s, no $5$s, no $3$'s, or no $1$s. So one first approximation is $$10^{10} - \binom{5}{1}9^{10}.$$

However, we are double counting the numbers that have no $9$s and no $7$s, the ones that have no $9$s and no $5$s, etc. There are $8^{10}$ of each of the $\binom{5}{2}=10$ pairs of odd digits. So we adjust by adding those back in, $$10^{10}-\binom{5}{1}9^{10} + \binom{5}{2}8^{10}.$$

But now we are off with those that are missing three of the odd numbers; we took them out three times with $\binom{5}{1}9^{10}$, but we then added them back three times with $\binom{5}{2}8^{10}$; we need to take them out again. So we get $$10^{10}-\binom{5}{1}9^{10} + \binom{5}{2}8^{10} - \binom{5}{3}7^{10}.$$

But now we are off with the numbers that are missing four of the odd numbers: we took them out four times with $\binom{5}{1}9^{10}$; we added them back in six (that is $\binom{4}{2}$) times with $\binom{5}{2}8^{10}$; then we took them out four times (that is, $\binom{4}{3}$) with $\binom{5}{3}7^{10}$. So we need to add them back in, with $\binom{5}{4}6^{10}$, so we get $$10^{10} - \binom{5}{1}9^{10} + \binom{5}{2}8^{10} - \binom{5}{3}7^{10} + \binom{5}{4}6^{10}.$$ But now, what about those numbers that fail to contain all of the odd digits? We counted them five times in the $\binom{5}{1}9^{10}$ summand, so we took them out five times; then we added them back in $\binom{5}{2}=10$ times in the summand $\binom{5}{2}8^{10}$; then we took them out $10$ times in $\binom{5}{3}7^{10}$; and then we added them back in five times with $\binom{5}{4}6^{10}$. In total, we've took them out zero times; we need them out, so we need to subtract $\binom{5}{5}5^{10}$. So, finally, we get $$10^{10} - \binom{5}{1}9^{10} + \binom{5}{2}8^{10} - \binom{5}{3}7^{10} + \binom{5}{4}6^{10} - \binom{5}{5}5^{10}$$ telephone numbers which contain each of $1$, $3$, $5$, $7$, and $9$ at least once.

-
Just for possible comparison with other methods, the final expression evaluates to $771\,309\,000$. –  Marc van Leeuwen Aug 20 '13 at 17:11