Factorial fun

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.