Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
someone made an edit that makes it seem like i want to solve for x given x ... but on the other hand maybe my original title was not more clear –  binn Sep 2 '12 at 17:34
    
I've added the question to the body of the post (which is preferable to simply putting it in the title, for future reference), and rephrased it slightly for clarity. Please make certain that I've phrased it in the same way you intended it. –  Cameron Buie Sep 2 '12 at 17:35
1  
I'd just suggest refining guess-and-check to binary search. –  Harry Altman Sep 2 '12 at 17:36
    
You might want to change the title to something like "Algorithm question involving binomial coefficients". That gives people an idea what they're looking at, and then you can give the details in the body of the post. –  Cameron Buie Sep 2 '12 at 17:38
    
@cameron: thanks, your rephrasing in the question body seems accurate. –  binn Sep 2 '12 at 17:39
show 4 more comments

marked as duplicate by Qiaochu Yuan Sep 2 '12 at 18:58

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1 Answer

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.

share|improve this answer
    
Just to clarify, by x' = y!z^1/y I guess you mean x' = (y!z)^1/y , and by "check integers that are around x' [...] That is a linear search" you mean the linear search can be started at ceil(x') without missing the solution. –  binn Sep 2 '12 at 18:48
    
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." –  MJD Sep 2 '12 at 18:56
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.