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?
$\endgroup$ 72 Answers
$\begingroup$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.
$\endgroup$ 1 $\begingroup$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 # 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
