My daughter came home from school yesterday with a math quiz that we couldn't work out:
How many 9-digit phone numbers can we compose from digits 1, 2, 3, 4, 5, 5, 5, 5, 5 ?
I tried the basic permutations and combinations rules but am confused by the fact that the 5's are repeated in the set (no repetition for 1 ~ 4). I guess it must have a reasonably simple answer as it was in Sixth grade advanced math quiz.
Any help would be appreciated :)
$\endgroup$ 13 Answers
$\begingroup$I tried the basic permutations and combinations rules but am confused by the fact that the 5's are repeated in the set (no repetition for 1 ~ 4). I guess it must have a reasonably simple answer as it was in Sixth grade advanced math quiz.
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 for 1 which leave $8$ places for 2, 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 $$
- unless you are red-blue colour-blind
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!}$$
$\endgroup$ $\begingroup$$1$ through $4$ can be placed in $9*8*7*6$ ways,
the remaining spots automatically go to the $5's$
Suppose that all given digits are distinct.
So we have $9!$ different types of numbers.
Since 5 is repeated five times , it makes the same permutation $5!$ times.
So you get $\frac{9!}{5!}=3024 $ distinct phone numbers.
$\endgroup$
