4
$\begingroup$

I know that you can find the value of any number in Pascal's Triangle using the row and column with binomial coefficients, but cannot find a method to find the value given an index.

For instance, a Pascal's Triangle with 5 rows looks like: \begin{gather} 1\\ 1 \quad 1\\ 1 \quad 2 \quad 1\\ 1 \quad 3 \quad 3 \quad 1\\ 1 \quad 4 \quad 6 \quad 4 \quad 1 \end{gather}

If you were to index this triangle, it would look like this: \begin{gather} 00\\ 01 \quad 02\\ 03 \quad 04 \quad 05\\ 06 \quad 07 \quad 08 \quad 09\\ 10 \quad 11 \quad 12 \quad 13 \quad 14 \end{gather}

Without using previous values or referencing the row and column, can you find the value at any given index?

$\endgroup$
  • $\begingroup$ you might be able to use the diagonals but that still may relate to the rows and columns. $\endgroup$ – user451844 Jul 13 '17 at 22:37
  • $\begingroup$ I think you'd need to recover the row and column first, which is easily done of course. $\endgroup$ – Joffan Jul 13 '17 at 22:40
4
$\begingroup$

If you do not want to use the row number explicitly from the position index $i$ then you can use the inefficient $$\frac{\Big\lfloor \dfrac{\sqrt{8i+1}-1}{2}\Big\rfloor!}{\left(i-\dfrac{\big\lfloor \frac{\sqrt{8i+1}-1}{2}\big\rfloor\big\lfloor \frac{\sqrt{8i+1}+1}{2}\big\rfloor}{2}\right)!\left(\Big\lfloor \dfrac{\sqrt{8i+1}-1}{2}\Big\rfloor+\dfrac{\big\lfloor \frac{\sqrt{8i+1}-1}{2}\big\rfloor\big\lfloor \frac{\sqrt{8i+1}+1}{2}\big\rfloor}{2}-i\right)!}$$

That is just a substituted version of a more efficient method of finding the row $r=\Big\lfloor \dfrac{\sqrt{8i+1}-1}{2}\Big\rfloor$ using the floor function and and the value of the index of the initial position in the row $s=\dfrac{r(r+1)}{2}$, so the value corresponding to index position $i$ is $\displaystyle {r\choose i-s}=\dfrac{r!}{(i-s)!(r+s-i)!}$

$\endgroup$
  • $\begingroup$ Do you have any references for the formula derivations? $\endgroup$ – Kevin Wallis Dec 1 '17 at 13:54
  • $\begingroup$ @KevinWallis: It is possible to do mathematics almost from scratch $\endgroup$ – Henry Dec 1 '17 at 16:42
1
$\begingroup$

It might not be immediately obvious to you, but the answer I wrote out here shows how to compute the row and column index from the "linear index" and vice versa; once you know these, you've got your answer.

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