6
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\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.