Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
Related:… – 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
up vote 2 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|cite|improve this answer

Your Answer


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.