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.

Is there a way to efficiently(ie: without building the actual triangle) to find out which row a number first occurs in in Pascal's triangle?

This is equivalent to answering: given A what is the smallest number m such that there exists n such that m choose n = A. This is due to the fact that a number at row m and column n in Pascal's triangle is equal to m choose n.

share|improve this question
2  
Related: math.stackexchange.com/questions/103377/… –  JavaMan Jan 29 '12 at 1:10
    
Apply the algorithm described in the link above, but start with the largest value of $k$ first. –  Qiaochu Yuan Jan 29 '12 at 1:11
add comment

1 Answer

up vote 1 down vote accepted

The link provided by JavaMan indeed answers this question: How to reverse the $n$ choose $k$ formula?

A summary of the algorithm -- took me while to figure out from that answer, so I'm writing it as an algorithm instead of an explanation of one. If you want to know how this works, I highly recommend visiting that answer and upvoting it, it's very informative -- is as follows. First, the problem is minimizing n given X such that:

$${n \choose k} = X$$

First we determine max(k) given that we know that: $$X > \frac{4^k}{2k+1}$$

From there we iterate over 1 to max(k). At each step of the iteration, n, if it exists is contained in the interval:

$$\sqrt[k]{k! X} + k \ge n \ge \sqrt[k]{k! X}$$

We iterate over that interval and check if ${n \choose k}=X$. We can then easily find the minimum such n.

share|improve this answer
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.