What is the formula to calculate the number of divisors of $n!$

Question

I felt like trying to find the number of divisors of $n!$. I have found that taking the number of subsets of the first $n$ natural numbers ($n! = \sum\limits_{i = 1}^ni:i \in \mathbb{N}$), one can say that $n!$ has $\sum\limits_{i=1}^{n-1} {}^{n}C_i -\sum\limits_{j=1}^{n-2} {}^{n-1}C_j $ divisors (not sure; it can have errors as I had only tried with $n = 3,4,5$). Later when I tried it on $n=6$, it seemed to me that the powers of primes had not been counted.

How can I accommodate the forgotten numbers into the count? If I did it all the wrong way, would anybody please telling if there is really a formula to do the above calculation?

PS: I am not very much of an advanced mathematician (I had only started my 11th grade last week), so if you could, please explain to me in simpler ways. Also, I learnt about permutations (not the whole thing, just a bit on combinations) in an entrance coaching center.

Answer 1

I don't think you can do this in terms of $n$ alone without know more about what $n$ is, in particular what are the primes and distribution around it.

If $p_1, p_2, ...., p_k$ are the primes that are less than or equal to $n$ then $n! = \prod\limits_{m=1}^k p_m^{\sum_{e\in \mathbb N; p^e \le n} \lfloor \frac n{p^e}\rfloor}$

If that seems a little confusing consider for example $36!$.

$36! = 1*2*3 ... *36$. If we factor out a $2$ for every even term we get $36! = 2^{18}(1*1*3*2*5*3*7*4*..... *17*35*18)$ But we still have even numbers because some of the even numbers were divisible by $4$; not just $2$. There were $\frac{36}4 = 9$ numbers that were divisible by $4$ and after dividing by $4$ they are still even.

So

$36! = 2^{18 + 9} (1*1*3*1*5*3*7*2*9*5*11*3*....*31*8*33*17*35*9)$. But we still have the numbers that were divisible by $8$, and after that we will have the numbers that were divisible by $16$ and $32$. Taking those into account we get:

$36! = 2^{18 + 9 + 4 + 2 + 1} (\text{a bunch of odd numbers now that we have factored out all the possible powers of }2)$

Now we do the same thing for the factors of $3$. There are $\frac {36}3 = 12$ multiples of $3$ and $\frac {36}9 = 4$ multiples of $9$ and $\lfloor \frac {36}{27} \rfloor = 1$ multiple of $27$ (namely just $27$ itself).

So $36! = 2^{18+9 + 4+ 2+ 1}3^{12 +9 + 1}(\text{ a bunch of odd terms not divisible by }3)$.

Do the same for the rest of the primes.

$36! = 2^{18+9 + 4+ 2+ 1}3^{12 +9 + 1}5^{7 + 1}7^{5}11^313^217^219\cdot 23\cdot 29\cdot 31$

And that's it and that explains our formula: $n! = \prod\limits_{m=1}^k p_m^{\sum_{e\in \mathbb N; p^e \le n} \lfloor \frac n{p^e}\rfloor}$

Okay... now in general if a number $K$ has a prime factorization of $K = \prod p_i^{m_i}$ it will have $\prod (m_i + 1)$ factors.

Why?

Well, the factors of $ \prod p_i^{m_i}$ will be any number of the form $\prod p_i^{e_i}$ where $0 \le e_i \le m_i$. There are $m_i + 1$ option for each $e_i$ so there are $\prod(m_i + 1)$ ways to choose the factors of the form $\prod p_i^{e_i}$.

Maybe an example. $180 = 36\times 5 = 2^2\times 3^2 \times 5$.

A factor can only be divisible by $2,3$ or $5$ (or not). And it can be divisible by $1$ (but not $2$) or by $2$ (but not $4$) or by $4$. And it can be divisible by $1$ or $3$ or $9$. And it can be divisible by $5$ or not.

So the factors are

$\{1,2,4\} \times \{1,3,9\} \times \{1,5\}$ or

$1,2,4$

$3,6,12$ and $9,18, 36$ and

$5,10,20$ and $15,30,60$ and $45,90, 18$.

And we can see there are $3\times 3\times 2 = 18$ such factors

SO........

$n! = \prod\limits_{m=1}^k p_m^{\sum_{e\in \mathbb N; p^e \le n} \lfloor \frac n{p^e}\rfloor}$ will have

$\prod (1+ \sum_{e\in \mathbb N; p^e \le n} \lfloor \frac n{p^e}\rfloor)$ factors.

For example.

$7! = 1\cdot 2 \cdot 3\cdot 4\cdot 5\cdot 6\cdot 7 = $

$2^{3}(3\cdot 2\cdot 5\cdot 6\cdot 7) = $

$2^{3+2}(3\cdot 5\cdot 3\cdot 7) =$

$2^{5}3^2 \dot 5\cdot 7$ and thus the factors will be all number of the form $2^{0,1,2,3,4,5}\times 3^{0,1,2}\times 5^{0,1} \times 7^{0,1}$ so there will be $(5+1)\times (2+1) \times (1+1) \times (1+1) = 6\cdot 3\cdot 2\cdot 2 = 72$ factors.

Answer 2

If $p \leq n$ is prime then it has exponent $\lfloor \frac{n}{p} \rfloor+\lfloor \frac{n}{p^2}\rfloor +\cdots+\lfloor \frac{n}{p^\alpha}\rfloor$ in $n!$ where $\alpha$ is the largest integer $\geq 1$ such that $p^{\alpha} \leq n$.

$p^\alpha$ has $\alpha+1$ divisors

therefore $n!$ has $\prod_{p \leq n} \left( 1+\lfloor \frac{n}{p} \rfloor+\lfloor \frac{n}{p^2}\rfloor +\cdots+\lfloor \frac{n}{p^{\alpha_p}}\rfloor \right)=\prod_{p \leq n}\left(1+\sum_{k=1}^{+\infty}\lfloor \frac{n}{p^k}\rfloor\right)$ divisors.

I don't think there's a nicer formula for this...

Answer 3

To see why your formula works up to $n = 5$ but doesn't work for $n = 6$, consider the following. Any integer $n$ can be written via prime factorization as $$ n = 2^{p_2} 3^{p_3} 5^{p_5} \cdots. $$ Another integer which divides it will also be prime-factorizable as $$ m = 2^{q_2} 3^{q_3} 5^{q_5} \cdots, $$ where $0 \leq q_2 \leq p_2$, $0 \leq q_3 \leq p_3$, etc. It is not hard to see from this format that the number of integers that divide $n$ is $$ \sigma_0(n) = (p_2 + 1)(p_3 + 1)(p_5 + 1) \cdots; \tag{1} $$ each factor corresponds to the possible number of options for each prime power to appear in the factorization.

As noted above, your proposed equation reduces to $2^{n-1}$. Why does this form work for $n = 1, 2, 3, 4, 5$ but fails for $n = 6$?

• For $n = 1$, all of the $p_i$ exponents vanish. So all of the factors in (1) are 1, and $\sigma_0(n!) = 1$, as expected.
• For $n = 2$, we add a factor of 2 to the prime factorization of $n!$. This changes $p_2$ from 0 to 1, which means that the first factor in (1) goes from 1 to 2, i.e., it doubles. So $\sigma_0(n!) = 2$.
• For $n = 3$, we add a factor of 3 to the prime factorization of $n!$. This changes $p_3$ from 0 to 1, which means that the second factor in (1) goes from 1 to 2, i.e., it doubles. So $\sigma_0(n!) = 4$.
• For $n = 4$, we add a factor of $4 = 2^2$ to the prime factorization of $n!$. This changes $p_2$ from 1 to 3, which means that the first factor in (1) goes from 2 to 4, i.e., it doubles. So $\sigma_0(n!) = 8$.
• For $n = 5$, we add a factor of 5 to the prime factorization of $n!$. This changes $p_5$ from 0 to 1, which means that the third factor in (1) goes from 1 to 2, i.e., it doubles. So $\sigma_0(n!) = 16$.
• For $n = 6$, we add a factor of $6 = 2\cdot3$ to the prime factorization of $n!$. This changes $p_2$ from 3 to 4 and $p_3$ from 1 to 2, which means that the first factor in (1) increases by $\frac{5}{4}$ and the second factor increases by $\frac{3}{2}$. This is not a doubling, so $\sigma_0(n!) \neq 32$.

So it seems that you just got lucky. You can also use a similar technique to prove to yourself (try it!) that if $n$ is prime, $\sigma_0(n!) = 2 \sigma_0((n-1)!)$. But for non-prime $n$, this does not necessarily hold.