I have a problem that leads to the following equation:


$${x \choose k} = N$$


For some unknown $x$ and known constants $k$ and $N$. Here all numbers are natural numbers. I can solve this analytically for $k=1$ and $k=2$ but I can't find a general formula for any $k$. However, I was able to show that $ x \lt k N^{1/k} $.


Is there a way to solve for $x$ analytically? If not, is there a better way of finding $x$ than binary search?



Solve equation involving binomial coefficient
Solving exactly will be tough. There are shockingly simple things about binomial coefficients that we don’t know (but that we would know if we could solve that explicitly for $x$). See for instance [Singmaster’s conjecture](https://en.m.wikipedia.org/wiki/Singmaster%27s_conjecture), which is the assertion that for any fixed value of $N > 1$, that equation has at most $100$ solutions. This is asking if there are any numbers other than 1 that show up more than 100 times in Pascal’s triangle (which is still an open problem!). [Of course, this is asking to solve for integer values of $x$. So it’s *conceivable* a formula might be findable but verifying whether or not it gives you an integer is tricky... Unsure...]


That said, if you want asymptotics, try


$ \left( \dfrac{x}{k} \right) ^k \leq {x \choose k} \leq \left( \dfrac{ex}{k} \right) ^k$.


This gives $k N^{1/k}/e \leq x \leq k N^{1/k}$.


If that’s not good enough for you, you can use some tighter bounds on the binomial coefficients. What range do you want?


Or there are also the simple bounds


$\dfrac{(x-k)^k}{k!} \leq {x \choose k} \leq \dfrac{x^k}{k!}$,


which give us


$(N k!)^{1/k} \leq x \leq (N k!)^{1/k} + k$.


We could get closer still if that’s what you’re into. Lemme know.


If you want an algorithm to find $x$ given $N$ and $k$, binary search isn’t bad (you’d need to test $\log(k)$ terms by using the above). You could also try something involving modular arithmetic, but it’s gonna be hard to beat $\log(k)$ anyway since it takes that long just to read the number $k$. If interested in an algorithm, lemme know roughly how $k$ grows with $N$, and lemme know what parts of the computation are “expensive” for you.


