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.
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