In how many zeros does the number 130 choose 70 end?

Question

I have a general idea to solve the problem, which is to pair up 2s and 5s in the numerator and denominator, cancel those that are common, and the remaining pairs of 2s and 5s are the number of 0s left. Since 130 choose 70 is so large, how do I do this?

Answer 1

By definition, $$\binom{n}{k} = \frac{n!}{k!(n - k)!}$$ Hence, $$\binom{130}{70} = \frac{130!}{70!60!}$$ A number ends in zero if it is divisible by $10 = 2 \cdot 5$. Every even number is divisible by at least one factor of $2$, so the number of zeros with which $n!$ ends is determined by the number of factors of $5$ that divide it. We can calculate the number of factors of $5$ that divide $n!$ by using the formula $$\left\lfloor \frac{n}{5} \right\rfloor + \left\lfloor \frac{n}{5^2} \right\rfloor + \left\lfloor \frac{n}{5^3} \right\rfloor + \cdots$$ The first term counts the number of factors of $n!$ that are divisible by $5$; the second term counts the number of factors of $n!$ that are divisible by $5^2 = 25$; the third term counts the number of factors of $n!$ that are divisible by $5^3$; and so forth. Consequently, the formula counts each factor of $n!$ that contributes exactly one factor of $5$ once, each factor of $n!$ that contributes exactly two factors of $5$ twice, and so forth.

The number of factors of $5$ that divide $130!$ is $$\left\lfloor \frac{130}{5} \right\rfloor + \left\lfloor \frac{130}{5^2} \right\rfloor + \left\lfloor \frac{130}{5^3} \right\rfloor + \cdots = 26 + 5 + 1 + 0 + 0 + \cdots = 32$$ Since $$\left\lfloor \frac{70}{5} \right\rfloor + \left\lfloor \frac{70}{5^2} \right\rfloor + \left\lfloor \frac{70}{5^3} \right\rfloor + \cdots = 14 + 2 + 0 + 0 + \cdots = 16$$ and $$\left\lfloor \frac{60}{5} \right\rfloor + \left\lfloor \frac{60}{5^2} \right\rfloor + \left\lfloor \frac{60}{5^3} \right\rfloor + \cdots = 12 + 2 + 0 + 0 + \cdots = 14$$ the denominator is divisible by $16 + 14 = 30$ factors of $5$. Therefore, the quotient $\frac{130!}{70!60!}$ is divisible by $32 - 30 = 2$ factors of $5$, which suggests that $\binom{130}{70}$ ends in two zeros.

As @DavidK has pointed out in the comments, this is true provided that there are not more factors of $2$ in the denominator than there are in the numerator since each such factor would reduce a factor of $10$ in the numerator to a factor of $5$, thereby reducing the number of zeros at the end of the number.

The number of factors of $2$ that divide the numerator is $$\left\lfloor \frac{130}{2} \right\rfloor + \left\lfloor \frac{130}{2^2} \right\rfloor + \left\lfloor \frac{130}{2^3} \right\rfloor + \left\lfloor \frac{130}{2^4} \right\rfloor + \left\lfloor \frac{130}{2^5} \right\rfloor + \left\lfloor \frac{130}{2^6} \right\rfloor + \left\lfloor \frac{130}{2^7} \right\rfloor + \cdots\\ = 65 + 32 + 16 + 8 + 4 + 2 + 1 + 0 + 0 + \cdots = 128$$ The number of factors of $2$ that divide $70!$ is $$\left\lfloor \frac{70}{2} \right\rfloor + \left\lfloor \frac{70}{2^2} \right\rfloor + \left\lfloor \frac{70}{2^3} \right\rfloor + \left\lfloor \frac{70}{2^4} \right\rfloor + \left\lfloor \frac{70}{2^5} \right\rfloor + \left\lfloor \frac{70}{2^6} \right\rfloor + \left\lfloor \frac{130}{2^7} \right\rfloor + \cdots\\ = 35 + 17 + 8 + 4 + 2 + 1 + 0 + 0 + \cdots = 67$$ and the number of factors of $2$ that divide $60!$ is $$\left\lfloor \frac{60}{2} \right\rfloor + \left\lfloor \frac{60}{2^2} \right\rfloor + \left\lfloor \frac{60}{2^3} \right\rfloor + \left\lfloor \frac{60}{2^4} \right\rfloor + \left\lfloor \frac{60}{2^5} \right\rfloor + \left\lfloor \frac{60}{2^6} \right\rfloor + \left\lfloor \frac{60}{2^7} \right\rfloor + \cdots\\ = 30 + 15 + 7 + 3 + 1 + 0 + 0 + 0 + \cdots = 56$$ Thus, there are $67 + 56 = 123$ factors of $2$ in the denominator. Since there are fewer factors of $2$ in the denominator than the numerator, the number of zeros at the end of $\binom{130}{70}$ is, in fact, $2$.

Answer 2

Kummer's theorem states that the power of a prime $p$ dividing a binomial coefficient $\binom nk$ is the number of carries needed when adding $k$ to $n-k$ in base $p$ notation.

Here $k=70$ and $n-k=60$. In base $2$, $k=(1000110)_2$ and $n-k=(111100)_2$. So $\binom{130}{70}$ is exactly divisible by $2^5$. In base $5$, $k=(240)_5$ and $n-k=(220)_5$. So $\binom{130}{70}$ is exactly divisible by $5^2$. Therefore, $\binom{130}{70}$ ends in two zeros.