# Complexity of finding binomial coefficient which equals to a number

Assume you are getting a number $m$ (using $O(\log m)$ bits in binary encoding).

How fast can you find (or determine such does not exist) $$n,k\in \mathbb N, 1<k\leq\frac{n}{2}:{n \choose k}=m$$ ?

For example, given the input $m=8436285$, one may output $n=27, k=10$.

A naive algorithm for the problem would go over all possible values for $n$, and search for a value of $k$ which satisfies the property.

A simple observation is that there no need to check values of $n$ smaller than $\log m$ or larger than $O(\sqrt m)$. However (even if we could check only $O(1)$ possible $k$ values per $n$ value) this ends up in an inefficient algorithm which is exponential in the input size.

An alternative approach would be to go over the possible values of $k$ (it's enough to check $\{2,3,\ldots,2\log m\}$) and for each check for possible $n$ values. We can then use: $$\left(\frac{n}{k}\right)^k<{n\choose k}< \frac{n^k}{k!}$$

So for a given $k$ we only need to check $n$ values in the range $[\sqrt[\leftroot{-2}\uproot{2}k]{m\cdot k!},\sqrt[\leftroot{-2}\uproot{2}k]{m}\cdot{k}]$, Doing so using binary search (when $k$ is fixed, $n \choose k$ is monotonically increasing in $n$), this gives a polynomial algorithm running in $O(\log^2m)$.

This still seems inefficient to me and I guess that this could be solved in linear time (in the input size).

• What have you tried so far? Hint: Assume $n$ was given, too. Could you solve this then? What's the range of possible values for $n$? Or, assume $k$ was given; could you solve it in that case? What's the range of possible values for $k$? – D.W. Jan 5 '15 at 0:59

It is not true that $(n-k)^k<{n\choose k}$. For example ${9\choose 2} = 36 < 49 = (9-2)^2$.
You could, for each $k$, solve for $n$ by taking an initial guess (say $\sqrt[k]{k!\cdot m}$) and using an analytical method such as Newton-Raphson. You want to solve ${n\choose k} - m = 0$. The derivative of the left hand side with respect to $n$ is $(\psi(n+1)-\psi(n-k+1)){n\choose k}$ where $\psi$ is the digamma function, which is easy to compute.
So overall for each $k$ the search should be $O(1)$ (assuming, as you seem to have done, that computing a binomial coefficient takes constant time), hence the total complexity for the algorithm using your bounds for $k$ would be $O(\log(m))$.
• While I agree the bounds were off (see edit, thanks for that), can you explain why the search, given $k$ takes $O(1)$? – R B Jan 11 '15 at 9:00