2
$\begingroup$

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$
  • 2
    $\begingroup$ You just have to combine $$ d(n)=\prod_{p\mid n}\left(\nu_p(n)+1\right) $$ with $$ \nu_p(n!)=\sum_{k\geq 1}\left\lfloor \frac{n}{p^k}\right\rfloor$$ to get that the answer is $$ (5+2+1+1)(3+1+1)(2+1)(1+1)=270.$$ $\endgroup$ – Jack D'Aurizio Dec 11 '18 at 0:53
7
$\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$
  • $\begingroup$ Easy, after your hint it all became clear, thank you! $10! = 1 \cdot 2 \cdot3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8\cdot 9 \cdot 10= 2 \cdot 3 \cdot 2^2 \cdot 5 \cdot 2 \cdot 3 \cdot 7 \cdot 2^3 \cdot 3^2 \cdot 5 \cdot 2= 2^8 \cdot 3^4 \cdot 5^2 \cdot 7$ $\endgroup$ – Wesley Strik Dec 11 '18 at 0:23
  • 1
    $\begingroup$ You're very welcome. $\endgroup$ – user296602 Dec 11 '18 at 0:24
3
$\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$
  • $\begingroup$ Of course, unique prime factorisation. $\endgroup$ – Wesley Strik Dec 11 '18 at 0:20
0
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.