Copyright © University of Cambridge. All rights reserved.
Luke of Madras College and Ling Xiang
Ning, Raffles Institution, Singapore, sent us answers to the
question "How many divisors does $n!$ have?"
Ling Xiang Ning said: To find the
number of factors of factorial $n$, first I tried small values of
$n$, for factorial $2$, then $3, 4, 5, 6, 7, 8,$ and $9$. I found a
generalisation for all values of $n$.
First find the prime factorisation of $n!$
\[ n! = p_1^a p_2^b p_3^c ... \]
where $p_1, p_2, ...$ etc. are the prime factors of $n!$ and $a,
b,...$ etc are the powers of these prime factors.
Number of divisors of $n! = (a +
1)(b + 1)(c + 1) ... $
Luke gave more detail:
The highest power of $5$ which is a divisor of $20!$ is $5^4$ and
the highest power of $2$ is $2^{18}$.
If $n!$ is written as a product of its prime factors we may want to
find the powers of each factor. If $p$ is a prime where $p, 2p, 3p,
\dots kp \leq n$ then each of these terms contributes once to the
power of $p$ contained in $n!$ where $k$ is the integer part of
$n/p$ denoted by $k = [n/p]$. Now consider $p^2, 2p^2, 3p^2 ,
\dots$; here there are $[n/p^2]$ terms, each of which contributes
one more power of $p$. Then consider $p^3, 2p^3, 3p^3, \dots$; here
there are $[n/p^3]$ terms, each of which contributes one more power
of $p$ when $n!$ is written as a product of its prime factors and
so on.
Let $p_1, p_2, p_3, \dots , p_k$ be a list of all primes less than
or equal to $n$.
Then define
$$a_i = \sum_{r=1}^{\infty} \left[\frac{n}{p_{i}^{r }}\right]
\qquad \qquad 1 \leq i \leq k$$
where the square brackets denote `the integer part of' so that
$a_i$ is clearly the highest power of $p_i$ dividing $n!$.
Then $n! = p_{1}^{a_{1}}.p_{2}^{a_{2}}\dots{p_{k}^{a_{k}}}$ so the
number of divisors of $n!$ is $(1 + a_1)(1 + a_2) \dots (1 +
a_k)$
Example
I take $9!$ as an example. Replacing $n$ with $9$, we have
$9=2^7.3^4.5.7$
The number of divisors of $9!$ is $(7+1)(4+1)(1+1)^2 = 8\times
5\times 4 = 160$ Therefore, $9!$ has $160$ divisors.
With $n = 20$ the $p_i$ are $2, 3, 5, 7, 11, 13, 17, 19$ and $20 !
= 2^a. 3^b. 5^c. 7^d. 11^e. 13^f. 17^g. 19^h$ and $e = f = g = h =
1$ and the number of divisors is
$(a+1)(b+1)(c+1)(d+1)(e+1)(f+1)(g+1)(h+1)$.
$a = (20/2) + (20/4) + (20/8) + (20/16) = 10 + 5 + 2 + 1 =
18$
$b = (20/3) + (20/9) = 6 + 2 = 8$
$c = (20/5) = 4$
$d = (20/7) = 2$
So the number of divisors is $19.9.5.3.2^4 = 41040$
To understand the reason for this, think
of each divisor being expressed as a product of prime factors. The
number of possible divisors is found by working out the number of
ways of choosing the prime factors of the divisor. The prime $p_1$
may not occur as a factor of the divisor, or it may occur to the
power 1 or 2 or 3 or any power up to at most $a$, hence there are
$(a+1)$ possibilities for a divisor to contain $p_1$ as a factor.
Similarly there are $(b+1)$ possibilities for a divisor to contain
$p_2$ as a factor and $(c+1)$ possibilities for a divisor to
contain $p_3$ as a factor and so on. We multiply these numbers of
possibilities to find the total number of possibilities.
The same problem exactly would arise if the
classes in a school were each named by a different prime number and
the number of students in class $p_1$ is $a$, and there are $b$
students in class $p_2, c$ students in class $p_3$ and so on. At
any time there may be no students from any of the classes in the
school building or any number from any of the classes. How many
different possibilities are there for the number of students in the
building? Can you see that this is the same as the Factorial Fact
problem? If not work out the answers in some simple cases, for
example imagine 2 classes with 3 children in one and 4 children in
the other.