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

$\endgroup$
7
  • 11
    $\begingroup$ 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? $\endgroup$ Jan 28 '12 at 20:30
  • 3
    $\begingroup$ 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. $\endgroup$
    – Srivatsan
    Jan 28 '12 at 20:33
  • $\begingroup$ X might be as high as 10000000. It's to solve a math puzzle I am working on. $\endgroup$ Jan 28 '12 at 20:34
  • $\begingroup$ 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. $\endgroup$
    – Jalaj
    Jan 28 '12 at 20:39
  • $\begingroup$ Gotcha, thanks. $\endgroup$ Jan 28 '12 at 20:49
55
$\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$ 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). $\endgroup$
    – user25406
    Mar 13 '19 at 18:59
8
+100
$\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
        # 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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.