# 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? 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. Jan 28 '12 at 20:33
• X might be as high as 10000000. It's to solve a math puzzle I am working on. 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. Jan 28 '12 at 20:39
• Gotcha, thanks. 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.

• Qiaochu Yuan, you said that "above algorithm takes polynomial time in log(X)". Does it mean the same algorithm used to factor the same number N takes polynomial time. All we need to factor N once we have found (n,k) is to get the (n,k) of M the immediate neighbor of N and calculate the gcd(N,M). Mar 13 '19 at 18:59

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