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.
Best Answer
Yes, $9!/5!$ is reasonably simple.
There are $9!$ ways to arrange nine distinct symbols. Â However, five of the symbols are not distinct. Â This means you can sort those arrangements into groups of $5!$ each of which are in fact identical. Â So we divide and calculate: $$\frac{9!}{5!} = 9\cdot 8\cdot 7\cdot 6 \qquad\text{distinct arrangements}$$
Alternatively: this result can be obtained by counting ways to assign places to the digits
1,2,3,4
and place the $5$ in the remaining positions. Â $9$ places for1
which leave $8$ places for2
, and so on. Â Thus: $9\cdot 8\cdot 7\cdot 6$ distinct arrangements.A simpler example to show how this works is counting ways to arrange $1,2,3,3$.
There are $4!$, that is $24$, arrangements of these four letters; but they can be sorted into groups of $2!$ each which differ only in the placement of the identical threes (although here they are colour coded for convenience*): $$12\color{red}3\color{blue}3, 12\color{blue}3\color{red}3, \; 1\color{red}32\color{blue}3, 1\color{blue}32\color{red}3, \; 1\color{red}3\color{blue}32, 1\color{blue}3\color{red}32,\; \color{red}312\color{blue}3, \color{blue}312\color{red}3,\; \color{red}31\color{blue}32, \color{blue}31\color{red}32,\; \color{red}3\color{blue}312, \color{blue}3\color{red}312, \\21\color{red}3\color{blue}3, 21\color{blue}3\color{red}3, \; 2\color{red}31\color{blue}3, 2\color{blue}31\color{red}3, \; 2\color{red}3\color{blue}31, 2\color{blue}3\color{red}31,\; \color{red}321\color{blue}3, \color{blue}321\color{red}3,\; \color{red}32\color{blue}31, \color{blue}32\color{red}31,\; \color{red}3\color{blue}321, \color{blue}3\color{red}321 $$
This question should be an introduction to the topic of multisets and the multinomial coefficient. Â In general when you have a collection of elements, $a_k$, each with $r_k$ repetitions, it's called a multiset. $$\{(a_k, r_k)\}_n = \{(a_1,r_1), (a_2, r_2), ... (a_n, r_n)\}$$
The number of distinct permutations of this multiset is the multinomial coefficient: $$\dbinom{r_1+r_2+\cdots+r_n}{r_1,r_2,\cdots , r_n}=\frac{(r_1+r_2+\cdots+r_n)!}{r_1!\,r_2!\,\cdots\, r_n!}$$