The probability that a binomial coefficient is divisible by 12.

Question

I do not know how to solve the following question:

What is the probability that $12$ divides $\binom{n}{12}$ for a randomly chosen natural number n?

Context:

I set this as a question in a problem set. I was trying to write these problems from memory while setting the questions.

Anyway, now I am unable to solve this variant. Essentially $12^5$ divides $12!$ and thus the question reduces to

Find the values of natural $n$ for which $12^6$ divides $n(n-1)(n-2)\cdots (n-11)$.

We can see that $12^5$ divides product of any consecutive $12$ numbers, so we need an additional $12$ from the product. When does this happen?

Answer 1

$$\binom{n}{12}=\frac{n(n-1)(n-2)\ldots(n-11)}{12!}=\frac{n(n-1)(n-2)\ldots(n-11)}{2^{10}\cdot 3^5\cdot 5^2\cdot 7\cdot 11}$$

Any $12$ consecutive integers include $4$ consecutive factors of $3$, at least one of which must be a multiple of $9$, and six consecutive multiples of $2$. Three of these must be multiples of $4$, and at least one must be a multiple of $8$, so their product has at least $10$ factors of $2$. We want to know when the product has at least $6$ factors of $3$ and at least $12$ factors of $2$.

The $12$ integers include two multiples of $9$ if $n$ is congruent to $0,1$, or $2$ modulo $9$, and they include a multiple of $27$ if $n$ is congruent to $0,1,2,\ldots,10$, or $11$ modulo $27$; thus, their product has at least $6$ factors of $3$ if and only if $n$ is congruent to one of the following $15$ numbers modulo $27$:

$$0,1,2,3,4,5,6,7,8,9,10,11,18,19,20$$

If the $12$ integers include two multiples of $8$, one of those must be a multiple of $16$, and their product will then have at least $12$ factors of $2$. If they include only one multiple of $8$, it must be a multiple of $32$ if the product is to have at least $12$ factors of $2$. They include two multiples of $8$ if $n\equiv 0,1,2,3\pmod8$, and they include a multiple of $32$ if $n$ is congruent to $0$, $1$, $2$, $3$, $4$, $5$, $6$, $7$, $8$, $9$, $10$, or $11$ modulo $32$. Thus, their product has at least $12$ factors of $2$ if and only if $n$ is congruent to one of the following $20$ numbers modulo $32$:

$$0,1,2,3,4,5,6,7,8,9,10,11,16,17,18,19,24,25,26,27$$

$\binom{n}{12}$ is a multiple of $12$ if and only if $n$ satisfies both of these conditions, meaning that it is in one of $15\cdot20=300$ residue classes modulo $27\cdot32=864$. As noted in the comments, the expression randomly chosen natural number is at best ill-defined, but we can at least say that the natural (or asymptotic) density of the set of natural numbers $n$ such that $12\mid\binom{n}{12}$ is

$$\frac{300}{864}=\frac{25}{72}\;,$$

and this corresponds reasonably well to the intuitive notion.

Answer 2

The problematic nature of the concept of “a randomly chosen natural number $n$” has already been addressed in the comments. I’ll first find the conditions under which the property holds and then we can consider how to makes this concept precise.

You already have some thoughts on how to approach this and your approach may well lead to success in this case. I’ll use a different approach that can be applied quite generally to such questions.

According to Kummer’s theorem, the binomial coefficient $\binom nk$ contains as many factors of a prime $p$ as there are carries when $k$ and $n-k$ are added in base $p$, or equivalently, as there are borrows when $k$ is subtracted from $n$ in base $p$. We have two primes to consider here, $2$ and $3$.

For $p=2$, we have $12_{10}=1100_2$, so there are at least two borrows if the third binary digit of $n$ is $0$ or if the fourth and fifth are both $0$. That is, we must have $\left\lfloor\frac n4\right\rfloor\equiv0\bmod2$ or $\left\lfloor\frac n8\right\rfloor\equiv0\bmod4$.

For $p=3$, we have $12_{10}=110_3$, and we need only one borrow, so the second or third ternary digit of $n$ must be $0$, that is, we must have $\left\lfloor\frac n3\right\rfloor\equiv0\bmod3$ or $\left\lfloor\frac n9\right\rfloor\equiv0\bmod3$.

Overlaying these conditions yields a pretty complicated pattern that only repeats every $2^5\cdot3^3=864$ integers. Here are the first few results in a table:

\begin{array}{c|cc} n&12&13&14&15&16&17&18&19&20&21&22&23&24&25&26&27\\\hline 12\mid\binom n{12}&✗&✗&✗&✗&✗&✗&✓&✓&✗&✗&✗&✗&✗&✗&✗&✓ \end{array}

Now we can make the question precise and answer it: In any interval of $864$ consecutive integers, the same number will fulfil the property. Thus, we can either uniformly randomly choose $n$ from such an interval (e.g. from $[1,864]$), or we can uniformly randomly choose $n$ from $[1,m]$ and let $m$ go to infinity, which will yield the same proportion as the first approach in the limit.

By the Chinese remainder theorem, the conditions with respect to $2$ and $3$ can be treated separately, and the corresponding probabilities can be multiplied as for independent events.

By inclusion–exclusion, the probability that $\left\lfloor\frac n4\right\rfloor\equiv0\bmod2$ or $\left\lfloor\frac n8\right\rfloor\equiv0\bmod4$ is $\frac12+\frac14-\frac12\cdot\frac14=\frac58$, and the probability that $\left\lfloor\frac n3\right\rfloor\equiv0\bmod3$ or $\left\lfloor\frac n9\right\rfloor\equiv0\bmod3$ is $\frac13+\frac13-\frac13\cdot\frac13=\frac59$. Thus, in either of the two senses defined above, the probability that $12\mid \binom n{12}$ for a randomly chosen integer $n$ is

$$ \frac58\cdot\frac59=\frac{25}{72}\approx35\%\;. $$