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
    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 clear2012-09-02
  • 0
    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.2012-09-02
  • 1
    I'd just suggest refining guess-and-check to binary search.2012-09-02
  • 0
    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.2012-09-02
  • 0
    @cameron: thanks, your rephrasing in the question body seems accurate.2012-09-02
  • 0
    @harry: the function is monotonic so i can do binary search but this still makes me feel stupid, possibly even stupider than using linear search. if there is not a slick way to get this then i will use linear search.2012-09-02
  • 0
    Also, the equality gives a polynomial in $x$ of degree $y$. So there are at most $y$ such $x$'s.2012-09-02
  • 0
    @jennifer: i'm pretty sure there is exactly one such x with the conditions in my question, but there are possibly more if you want to have negative or fractional counts or extend factorials to complex gamma functions2012-09-02
  • 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