48
$\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?

  • 0
    Forgive me, but this is a little difficult to read. Please would you provide some explanatory text? :)2015-03-03

2 Answers 2

53

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.

6

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