Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
6  
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? –  Qiaochu Yuan Jan 28 '12 at 20:30
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. –  Srivatsan Jan 28 '12 at 20:33
    
X might be as high as 10000000. It's to solve a math puzzle I am working on. –  DanielS 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. –  Jalaj Jan 28 '12 at 20:39
    
Gotcha, thanks. –  DanielS Jan 28 '12 at 20:49
add comment

2 Answers

up vote 26 down vote accepted

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.

share|improve this answer
add comment

See my algorithm based on previous answer...

and enter image description here

D Hardisky

share|improve this answer
    
Please try to describe as much here as possible in order to make the answer self-contained. Links are fine as support, but they can go stale and then an answer which is nothing more than a link loses its value. –  robjohn Apr 24 at 14:33
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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