Combinatoric Selections

Python/SageMath's unlimited precision integers make this trivial.

binoms = (binomial(n, r) for n in range(1, 101) for r in range(0, n + 1))
len([b for b in binoms if b > 1000000])

4075

If it weren't for unlimited precision, we would have a problem, since a lot of these binomial coefficients overflow a 64 bit integer - the largest one we encounter here is $\binom{100}{50} = 100891344545564193334812497256$.

However, even in that case there's a pretty simple workaround: finding $n$ and $r$ such that $$\binom{n}{r} > 1000000$$ is the same as finding $n$ and $r$ such that $$\log{\binom{n}{r}} > \log{1000000}$$ By applying the definition of the binomial coefficients and logarithmic identities, this turns to $$\log{n!} - \log{r!} - \log{(n-r)!} > \log{1000000}$$ $\log{100!} \approx 363.739$, nowhere close to overflowing a float.

$\log{n!}$ can be computed in a number of ways. You can use the log-gamma function, or you can implement a function yourself, either by applying logarithmic identities again: $$\log{n!} = \log{1} + \log{2} + \log{3} \cdots + \log{n}$$ or by using Stirling's approximation: $$\log{n!} \approx \left(n + \frac{1}{2}\right)\log{n} - n + \frac{1}{2}\log{2\pi}$$

Copyright (C) 2025 filifa

This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International license and the BSD Zero Clause license.