# How to find all positive integers $n,k$ such that ${n\choose k}=m$ for a given $m$?

This question is motivated by a simple exercise in Peter Cameron's Combinatorics: Topics, Techniques, Algorithms:

A restaurant near Vancouver offered Dutch pancakes with ‘a thousand and one combinations’ of toppings. What do you conclude?

The intended solution (according to Cameron's website) is the following: since $${14 \choose 4}=1001$$, most likely there were $$14$$ possible toppings and each serving of pancakes allowed the patron to choose $$4$$ toppings.

However, this begs a much more general question:

For a given positive integer $$m$$, how can we find all positive integers $$n$$ and $$k$$ such that $${n \choose k}=m$$?

This seems like a very natural and obvious question to ask, but preliminary searches didn't yield much apart from specific values of $$m$$. Any insight to this question for more general classes of positive integers $$m$$, or links to relevant references, would be appreciated.

• Commented Mar 19 at 2:42
• We have $1001 = 7\cdot 11\cdot 13$. It is just the product of three relatively large primes, which means there are likely to be few ways to produce it as a binomial coefficient. The existence of $13$ means the top number is at least $13$, and the absence of $17$ almost means the top number is at most $16$. At this stage the existence of $7$ means the top number must acutally be at least $14$, since in $\binom{13}{k}$ the factor of $7$ always cancels out. And $\binom{16}k$ is always even (apart from $1$). Looking for combinations that leave the $11$ uncancelled makes the search go pretty fast. Commented Mar 19 at 3:13
• (This approach is very much not generalizable in a nice way, but I suspect that the intended solution to that particular problem would go along these lines.) Commented Mar 19 at 3:14
• It might be somewhat more reasonable to require at most $k$ toppings, rather than exactly $k$. However, it turns out the only solution to $\sum_{i=0}^k {n \choose i} = 1001$ turns out to be $n=1000$, $k=1$, and it would be hard for the restaurant to offer $1000$ toppings. Commented Mar 19 at 3:27
• For a given value of $~m,~$ my first step would be to determine the prime factorization of $~m.~$ My second step would be to focus on the highest power of prime $~p~$ dividing $~n!$. Then, I would try to determine under what circumstances $~\displaystyle \binom{n}{k}~$ would be divisible by $~p^\alpha,~$ but not divisible by $~p^{\alpha + 1}.~$ Personally, I have never attacked this problem, so my approach might well fail.See also Legendre's formula. Commented Mar 19 at 4:11

It turns out to be quite fast

If $$k = 1$$ then $$n = m$$

If $$k > 1$$ then $$\frac{n^k}{k!} > m > \frac{(n-k)^k}{k!}$$, therefore $$(k!m)^{1/k} < n < (k!m)^{1/k}+k$$

Notice that $$\left(\begin{matrix}n\\k\end{matrix}\right) = \left(\begin{matrix}n\\n-k\end{matrix}\right)$$ so we only need to check for $$k \leq n/2$$. This means $$2k < (k!m)^{1/k}+k$$ Therefore $$\frac{k^k}{k!} < m$$ As this grows quite fast for k (as shown in the below plot), only a handful of number of candidates need to be checked. Or one use Stirling approximation $$\frac{k^k}{k!} \approx \frac{e^k}{\sqrt{2\pi k}}$$

## UPDATE:

The range for possible values of k can be improved even further by directly using Stirling series:

$$m = \left(\begin{matrix}n \\ k\end{matrix}\right) \geq \left( \begin{matrix}2k \\ k\end{matrix}\right) > \frac{4^k\left(1+\frac{1}{12k}\right)}{\sqrt{k\pi}\left(1+\frac{1}{12k}+\frac{1}{288k^2}\right)^2}$$

although it's probably faster to compute some values of $$\left(\begin{matrix}2k\\k\end{matrix}\right)$$ beforehand

• $+1$, nice approach! On the right you could use $-(k-1)$; that saves one check per $k$ value. And you could cut the number of checks roughly by half by using the AM/GM inequality: Since the correct numerator is the $k$-th power of the geometric mean of $n,n-1,\ldots,n-(k-1)$, the base on the left can be replaced by the arithmetic mean $n-\frac{k-1}2$. The search range for $n$ can thus be reduced to $$(k!m)^{1/k}+\frac{k-1}2 < n < (k!m)^{1/k}+k-1\;,$$ with a corresponding slight improvement in the range for $k$, $$\frac{(k+1)^k}{k!}\lt m\;.$$ Commented Mar 19 at 4:19
• I've some further improvement using Stirling's formula. But the best strategy would be just precompute some values of $\left(\begin{matrix}2k\\k\end{matrix}\right)$ Commented Mar 19 at 5:43