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.

  • 0
    Apply the algorithm described in the link above, but start with the largest value of $k$ first.2012-01-29

1 Answers 1

5

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.