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

If I want to find how many possible ways there are to choose k out of n elements I know you can use the simple formula below:

$$\binom{n}{k} = \frac{n! }{ k!(n-k)! } .$$

What if I want to go the other way around though?

That is, I know I want to have $X$ possible combinations, and I want to find all the various pairs of $n$ and $k$ that will give me that number of combinations.

For example, if the number of combinations I want is $3$, I want a formula/method to find that all the pairs that will result in that number of combinations are $(3,1)$ and $(3,2)$

I know I could test all the possible pairs, but this would be impractical for large numbers.

But perhaps there's no easier way of doing this then the brute force approach?

-
This is actually very hard. You can write down some approximations of ${n \choose k}$ (using e.g. Stirling's formula) that would let you rule out large $(n, k)$, and after that I suppose you could use information about the prime factorizations of binomial coefficients (see en.wikipedia.org/wiki/Lucas'_theorem for starters). What do you actually need to do this for? About how large will $X$ need to be? –  Qiaochu Yuan Jan 28 '12 at 20:30
I agree with @Qiaochu: generally speaking, expressing a given number as a binomial coefficient in different ways is not well understood yet. For one example open problem in this area, see this post. –  Srivatsan Jan 28 '12 at 20:33
X might be as high as 10000000. It's to solve a math puzzle I am working on. –  DanielS Jan 28 '12 at 20:34
I am afraid, there is no way to compute the exact value by using mathematical tools. There will be a point in your analysis that you will need to apply heuristic. –  Jalaj Jan 28 '12 at 20:39
Gotcha, thanks. –  DanielS Jan 28 '12 at 20:49

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.

-
⍝ giving the number of combinations X, for each k (1,2,3, ..)
⍝ find a natural number n in the polynomial: n*(n-1)*...*(n-k+1) = X*k!
⍝ stop when n <= 2*k

⍝ example: X = 120
⍝ k=1: n = 120 , found 1!120
⍝ k=2: n*(n-1)/2 = 120 ==> n*(n-1) = 240 ==> n = 16 , found 2!16
⍝ k=3: n*(n-1)*(n-2)/6 = 120 ==> n*(n-1)*(n-2) = 720 ==> n = 10 , found 3!10
⍝ k=4: n*(n-1)*(n-2)*(n-3) = 2880 ==> n = 8.911136728 , not found
⍝ k=5: n*(n-1)*(n-2)*(n-3)*(n-4) = 14400 ==> n = 8.934898082 , n <= 2*k , stop

⍝   answer is (n,k): (120,1) (16,2) and (10,3)
⍝ also with (n,n-k): (120,119) (16,14) and (10,7)

⍝ i.e. the number of pairs found is 6

-
Sorry, but is this intended to be an answer to the question? –  Casteels Mar 3 at 15:40