47
$\begingroup$

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?

  • 10
    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 http://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?2012-01-28
  • 2
    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](http://math.stackexchange.com/q/85442).2012-01-28
  • 0
    X might be as high as 10000000. It's to solve a math puzzle I am working on.2012-01-28
  • 0
    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.2012-01-28
  • 0
    Gotcha, thanks.2012-01-28
  • 0
    See my algorithm based on previous answer... ![](http://i.stack.imgur.com/HEHhG.jpg) and ![enter image description here](http://i.stack.imgur.com/oYZ57.jpg) D Hardisky2014-04-24
  • 0
    Forgive me, but this is a little difficult to read. Please would you provide some explanatory text? :)2015-03-03

2 Answers 2

52

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.

4

Here's an implementation of Qiaochu's answer 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