Almost all binomial coefficients are divisible by their row number.

This is a theorem from [1]. What does it mean?

If you iterate through Pascal’s triangle, left-to-right and top-to-bottom, noting which entries *C*(*m*, *k*) are divisible by *m*, the proportion approaches 1 in the limit.

The author proves that the ratio converges to 1, but doesn’t say anything about the rate at which it approaches 1. By writing a little Python script we can observe *how* the ratio approaches 1.

First, let’s create a generator that will let us walk through Pascal’s triangle.

def pascal(): m, k = 0, 0 while True: yield (m, k) k += 1 if k > m: m += 1 k = 0

We can use this generator to illustrate Pascal’s triangle mod row number.

from math import comb p = pascal() m, k = next(p) while m < 10: ch = "*" if m > 0 and comb(m, k) % m == 0: ch = "0" print(ch, end="") if m == k: print() m, k = next(p)

This produces the following.

* 00 *0* *00* *0*0* *0000* *0***0* *000000* *0*0*0*0* *00*00*00*

The theorem says that as we keep going, the proportion of 0’s in a diagram like the one above approaches 1.

Now let’s plot the proportion of zeros as we traverse Pascal’s triangle mod row number.

N = 1000 x = np.zeros(N) p = pascal() for n in range(N): m, k = next(p) if m > 0 and comb(m, k) % m == 0: x[n] = 1 y = np.arange(N) plt.plot(y, x.cumsum()/y) plt.show()

Here’s what we get.

The ratio doesn’t seem to be converging to 1. If I had to guess, I might say it’s converging to 0.7 by looking at this plot. But if we go further out and switch to a log scale it seems more plausible that the sequence is converging to 1, albeit very slowly.

[1] Heiko Harborth. Divisibility of Binomial Coefficients by Their Row Number. The American Mathematical Monthly, Jan. 1977, Vol. 84, No. 1, pp. 35–37.

That is one of the slowest convergences I’ve ever seen!

It makes me wonder if its approximate behavior has a bunch of log(log(log(n)))-type terms in it, which are what scare me away from Erdos’ and Ramanujan’s work.

Amusingly, you can build the C(m,k) computation into the generator:

def pascal():

m, k, c = 0, 0, 1

while True:

yield (m, k, c)

c *= m-k

k += 1

if (k > m):

m += 1

k = 0

c = 1

else:

c //= k