0
$\begingroup$

I have a doubt regarding trailing zeroes in binomial coefficients...

Question: How would you calculate the number of trailing zeroes in the binomial coefficient of ${n\choose r}$ upto values of $1000$? Is there any efficient method for doing so?

$\endgroup$
1
1
$\begingroup$

To find the number of trailing zeroes in ${n\choose r}$, we have to find the exponent of $10=(2\times 5)$ in the expression.
Since the exponent of $5$ will always be smaller than the exponent of $2$, we can just find the exponent of $5$ in it.
The exponent of any prime $p$ in $n!$ is given by this expression $$E_p(n!)=\left\lfloor\frac{n}{p}\right\rfloor+\left\lfloor\frac{n}{p^2}\right\rfloor+\left\lfloor\frac{n}{p^3}\right\rfloor+\cdots\infty$$ $$=\sum_{k=1}^{\infty} \left\lfloor\frac{n}{p^k}\right\rfloor$$ Since $${n\choose r}=\frac{n!}{r!(n-r)!}$$ We can define the exponent of $5$ in it as $$E_5(n!)-E_5(r!)-E_5((n-r)!)$$
The exponent of $5$ will simply be the exponent of $10$, and therefore the number of trailing zeroes. Even though it unnecessary, you can find the exponent of $2$ to confirm that it is, in fact, more than the exponent of $5$ in it.

$\endgroup$
9
  • $\begingroup$ I had thought about that before but wouldn't the number of trailing zeroes in the product of two factorials be more than the sum of trailing zeroes in both the factorials calculated independently? Thanks... $\endgroup$ – Manav Aggarwal Mar 1 '15 at 12:13
  • $\begingroup$ @ManavAggarwal I am not sure if I understand what you are asking, but the exponents are added in multiplication and subtracted in division. $\endgroup$ – AvZ Mar 1 '15 at 12:18
  • $\begingroup$ Suppose one number is 500 and other is 200. The number of trailing zeroes in their product is 5 but the if we add the number of trailing zeroes in both numbers, it would be 4. So acc. to your method the answer will be 4 but it is actually 5. Can you please explain this? $\endgroup$ – Manav Aggarwal Mar 1 '15 at 12:21
  • $\begingroup$ @ManavAggarwal Prime factorization $500$ is $2^2\cdot5^3$ and of $200$ is $2^3\cdot 5^2$. Now $500\cdot 200=2^2\cdot 5^3\times 2^3\cdot 5^2=2^5\cdot 5^5=10^5$ $\endgroup$ – AvZ Mar 1 '15 at 12:28
  • $\begingroup$ Or is it diff. for factorials? Will the sum of number of trailing zeroes for example- 20!(4) and 36!(8) = 4+8 = 12 be the same as the number of trailing zeroes in their product? So shud i consider factorizing every number? $\endgroup$ – Manav Aggarwal Mar 1 '15 at 12:32
0
$\begingroup$

I would just like to add to @AvZ 's answer that for binomial coefficients the exponent of $5$ can be larger than the exponent of $2$ in some cases (eg. for ${177\choose 113}$ $E_5=3$ but $E_2=1$)

Therefore, with the same symbols as before, $${n\choose r}=\frac{n!}{r!(n-r)!}$$ $$E_p(n!)=\left\lfloor\frac{n}{p}\right\rfloor+\left\lfloor\frac{n}{p^2}\right\rfloor+\left\lfloor\frac{n}{p^3}\right\rfloor+\cdots=\sum_{k=1}^{\infty} \left\lfloor\frac{n}{p^k}\right\rfloor$$

the formula to calculate the trailing zeroes of a binomal coefficient is: $$E_5=E_5(n!)-E_5(r!)-E_5((n-r)!) $$ $$E_2=E_2(n!)-E_2(r!)-E_2((n-r)!) $$ $$min(E_5, E_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.