2
$\begingroup$

Possible Duplicate:
How to reverse the $n$ choose $k$ formula?

Given integers $y\geq 0$ and $z>0$, is there a good way to find an integer $x\geq y$ such that $z=\binom x y$?

I could just guess and check a few values for x because in practice its range is relatively small but this makes me feel dumb.

  • 0
    The sequence for varying $x$ is increasing so get an upper bound and then do a binary search.2012-09-02

1 Answers 1

2

The first thing that comes to mind is this: $z = {x\choose y}$ has the form $x^y\over y! $ plus some lower-order terms. So calculate $x' = (y!z)^{1/y}$ and check integers that are around $x'$ to see if they work. That is a linear search, but it is a linear search that starts in almost the right place, so it is not a completely dumb linear search. If it is not smart enough, do the same thing with ${x\choose y}\approx \frac1{y!}x^{y-1}(x - y)$ instead.

I wrote a little code to do this and it seems to work reasonably well.

  • 0
    Yes, just so. I have inserted the missing parentheses into the answer. By "around" I meant "I think it is a close upper bound, but I have not looked at it carefully enough to be completely sure that it is always greater than the correct answer."2012-09-02