How to reverse the $n$ choose $k$ formula?

If $X$ is only as large as $10^7$ then this is straightforward to do with computer assistance. First note the elementary inequalities $$\frac{n^k}{k!} \ge {n \choose k} \ge \frac{(n-k)^k}{k!}$$

which are close to tight when $k$ is small. If $X = {n \choose k}$, then it follows that $$n \ge \sqrt[k]{k! X} \ge n-k$$

hence that $$\sqrt[k]{k! X} + k \ge n \ge \sqrt[k]{k! X}$$

so for fixed $k$ you only have to check at most $k+1$ possible values of $n$, which is manageable when $k$ is small. You can speed up this process by factoring $X$ if you want and applying Kummer's theorem (the first bullet point in that section of the article), but computing binomial coefficients for $k$ small is straightforward so this probably isn't necessary.

For larger $k$, note that you can always assume WLOG that $n \ge 2k$ since ${n \choose k} = {n \choose n-k}$, hence you can assume that $$X = {n \choose k} \ge {2k \choose k} > \frac{4^k}{2k+1}$$

(see Erdős' proof of Bertrand's postulate for details on that last inequality). Consequently you only have to check logarithmically many values of $k$ (as a function of $X$). For example, if $X \le 10^7$ you only have to check up to $k = 14$.

In total, applying the above algorithm you only have to check $O(\log(X)^2)$ pairs $(n, k)$, and each check requires at worst $O(\log(X))$ multiplications of numbers at most as large as $X$, together with at worst a comparison of two numbers of size $O(X)$. So the above algorithm takes polynomial time in $\log(X)$.

Edit: It should be totally feasible to just factor $X$ at the sizes you're talking about, but if you want to apply the Kummer's theorem part of the algorithm to larger $X$, you don't actually have to completely factor $X$; you can probably do the Kummer's theorem comparisons on the fly by computing the greatest power of $2$ that goes into $X$, then $3$, then $5$, etc. and storing these as necessary. As a second step, if neither $X$ nor the particular binomial coefficient ${n_0 \choose k_0}$ you're testing are divisible by a given small prime $p$, you can appeal to Lucas' theorem. Of course, you have to decide at some point when to stop testing small primes and just test for actual equality.

Here's an implementation in code of Qiaochu's answer. The algorithm, to recap, is:

• Input $X$. (We want to find all $(n, k)$ such that $\binom{n}{k} = X$.)

• For each $k \ge 1$ such that $4^k/(2k + 1) < X$,

  • Let $m$ be the smallest number such that $m^k \ge k!X$.

  • For each $n$ from $\max(m, 2k)$ to $m + k$ (inclusive),

    • If $\binom{n}{k} = X$, yield $(n, k)$ and $(n, n-k)$.

It is written in Python (chose this language for readability and native big integers, not for speed). It is careful to use only integer arithmetic, to avoid any errors due to floating-point precision.

The version below is optimized to avoid recomputing $\binom{n+1}{k}$ from scratch after having computed $\binom{n}{k}$; this speeds it up so that for instance for $\binom{1234}{567}$ (a $369$-digit number) it takes (on my laptop) 0.4 seconds instead of the 50 seconds taken by the unoptimized version in the first revision of this answer.

#!/usr/bin/env python
from __future__ import division
import math

def binom(n, k):
    """Returns n choose k, for nonnegative integer n and k"""
    assert k >= 0
    assert n >= 0
    assert k == int(k)
    assert n == int(n)
    k = min(k, n - k)
    ans = 1
    for i in range(k):
        ans *= n - i
        ans //= i + 1
    return ans

def first_over(k, c):
    """Binary search to find smallest value of n for which n^k >= c"""
    n = 1
    while n ** k < c:
        n *= 2
    # Invariant: lo**k < c <= hi**k
    lo = 1
    hi = n
    while hi - lo > 1:
        mid = lo + (hi - lo) // 2
        if mid ** k < c:
            lo = mid
        else:
            hi = mid
    assert hi ** k >= c
    assert (hi - 1) ** k < c
    return hi

def find_n_k(x):
    """Given x, yields all n and k such that binom(n, k) = x."""
    assert x == int(x)
    assert x > 1
    k = 0
    while True:
        k += 1
        # https://math.stackexchange.com/a/103385/205
        if (2 * k + 1) * x <= 4**k:
            break
        nmin = first_over(k, math.factorial(k) * x)
        nmax = nmin + k + 1
        nmin = max(nmin, 2 * k)
        choose = binom(nmin, k)
        for n in range(nmin, nmax):
            if choose == x:
                yield (n, k)
                if k < n - k:
                    yield (n, n - k)
            choose *= (n + 1)
            choose //= (n + 1 - k)

if __name__ == '__main__':
    import sys
    if len(sys.argv) < 2:
        print('Pass X in the command to see (n, k) such that (n choose k) = X.')
        sys.exit(1)
    x = int(sys.argv[1])
    if x == 0:
        print('(n, k) for any n and any k > n, and (0, 0)')
        sys.exit(0)
    if x == 1:
        print('(n, 0) and (n, n) for any n, and (1, 1)')
        sys.exit(0)
    for (n, k) in find_n_k(x):
        print('%s %s' % (n, k))

Example runs:

~$ ./mse_103377_binom.py 2
2 1
~$ ./mse_103377_binom.py 3
3 1
3 2
~$ ./mse_103377_binom.py 6 
6 1
6 5
4 2
~$ ./mse_103377_binom.py 10
10 1
10 9
5 2
5 3
~$ ./mse_103377_binom.py 20
20 1
20 19
6 3
~$ ./mse_103377_binom.py 55
55 1
55 54
11 2
11 9
~$ ./mse_103377_binom.py 120
120 1
120 119
16 2
16 14
10 3
10 7
~$ ./mse_103377_binom.py 3003
3003 1
3003 3002
78 2
78 76
15 5
15 10
14 6
14 8
~$ ./mse_103377_binom.py 8966473191018617158916954970192684
8966473191018617158916954970192684 1
8966473191018617158916954970192684 8966473191018617158916954970192683
123 45
123 78
~$ ./mse_103377_binom.py 116682544286207712305570174244760883486876241791210077037133735047856714594324355733933738740204795317223528882568337264611289789138133946725471443924278812277695432803500115699090641248357468388106131543801393801287657125117557432072695477147403395443757359171876874010770591355653882772562301453205472707597435095925666815012707478996454360460481159339802667334477440
116682544286207712305570174244760883486876241791210077037133735047856714594324355733933738740204795317223528882568337264611289789138133946725471443924278812277695432803500115699090641248357468388106131543801393801287657125117557432072695477147403395443757359171876874010770591355653882772562301453205472707597435095925666815012707478996454360460481159339802667334477440 1
116682544286207712305570174244760883486876241791210077037133735047856714594324355733933738740204795317223528882568337264611289789138133946725471443924278812277695432803500115699090641248357468388106131543801393801287657125117557432072695477147403395443757359171876874010770591355653882772562301453205472707597435095925666815012707478996454360460481159339802667334477440 116682544286207712305570174244760883486876241791210077037133735047856714594324355733933738740204795317223528882568337264611289789138133946725471443924278812277695432803500115699090641248357468388106131543801393801287657125117557432072695477147403395443757359171876874010770591355653882772562301453205472707597435095925666815012707478996454360460481159339802667334477439
1234 567
1234 667