Number of divisors of $10!$
Determine the amount of divisors of $10!$
This is a question in my combinatorics textbook, so I need to somehow reduce this to an elementary counting problem like combinations, permutations with or without repetition. I just don't see it. I can determine $10$ easy divisors, those are all the numbers $1$ through $10$ themselves. Then we can consider all possible products of these numbers, but then I get that a number can be either in the product , or not. I would get that it is $2^{10}=1024$ but the answer says it should be $270$.
What is going wrong here?
Note: $1$ and $10!$ are included
$\endgroup$ 13 Answers
$\begingroup$You've overcounted quite a bit, because integer factorization is not unique unless we're talking about primes. So for example, you've got $4 \cdot 10 = 40 = 5 \cdot 8$ counted twice.
So rather than thinking about numbers between $1$ and $10$, think of prime powers. A number is a divisor of $10!$ if and only if it is of the form
$$n = 2^a \cdot 3^b \cdot 5^c \cdot 7^d$$for appropriate ranges of $a, b, c, $ and $d$. I'll leave it to you to figure out why the values of $a, b, c, $ and $d$ range from $0$ to $8$, $4$, $2$ and $1$ respectively, giving
$$(8 + 1)(4 + 1)(2 + 1)(1 + 1) = 270$$
in total.
$\endgroup$ 2 $\begingroup$Hint$$10!=2^{??}\cdot 3^{??}\cdot5^{??}\cdot 7^{??}$$
Now, any divisor must have the same primes with different powers...
The issue with your approach is that you are double and triple counting some divisors.
For example, you counted $8$ as $8$ but then you also counted it as $2 \cdot 4$. Same way, most numbers divisible by $8$ are at least double counted.
You counted $24$ as the products $3 \cdot 8, 4 \cdot 6, 2 \cdot 3 \cdot 4$ and so on...
$\endgroup$ 1 $\begingroup$Hint for a smaller number: consider $2^3\cdot 3^2$ = 72. To make one of its factors, how many times do you want to use $2$?
$\endgroup$
