0
$\begingroup$

enter image description here

How can I find a value from this pascal triangle given row and column number without calculating $^nC_r$?

For example, for row=$4$, column=$3$: value is $10$,

For row=$3$, column=$5$: value is $15$.

Is there any way to get this value without using $^nC_r$ explicitly?

$\endgroup$
  • $\begingroup$ Depends on what you mean by explicitly. Does constructing the Pascal triangle count? Or would a detour like the Beta function be preferred? $\endgroup$ – Tunococ Feb 6 '16 at 2:29
  • $\begingroup$ row and column number can be very large number like 10^15. So manually constructing pascal triangle is not a feasible solution. $\endgroup$ – Shadekur Rahman Feb 6 '16 at 2:36
  • 3
    $\begingroup$ Any method by which you can find the value of the number in the $r$th place in the $n$th row of Pascal's triangle is a method of calculating $^nC_r$. So basically you're asking for a "better" way of calculating $^nC_r$. There are approximate formulas, if that helps. $\endgroup$ – David K Feb 6 '16 at 2:47
  • 1
    $\begingroup$ Exactly like David K said, if you want really $\binom nr$ with $n$ and $r$ very large numbers, you should use approximation. $\endgroup$ – Tunococ Feb 6 '16 at 2:53
  • 2
    $\begingroup$ "modulo"? Do you mean, you only need the remainder when you divide by some given prime $p$? Then what you want is Lucas' Theorem, en.wikipedia.org/wiki/Lucas%27_theorem $\endgroup$ – Gerry Myerson Feb 6 '16 at 3:54
0
$\begingroup$

I needed the following values modulo P (a prime): $$^xC_1, ^{x+1}C_2, ^{x+2}C_3, ..., ^{x+y-1}C_y$$ where $$0<x<10^{15}, 0<y<10^5, y\le x$$ Now you can consider each $^nC_r$ value as a fraction of numerator and denominator.

So $^xC_1$ = $\frac{x}{1}$, $^{x+1}C_2$ = $\frac{x.(x+1)}{1.2}$, $^{x+2}C_3$ = $\frac{x.(x+1).(x+2)}{1.2.3}$, ...

You can get modulo value of numerator and denominator separately.

Ultimately, $^nC_r = \frac{A}{B} \mod P = (A.B^{-1}) \mod P$ ......... (i)

Now, from Fermat's little theorem, $$a^P \equiv a \mod P$$ $$a^{P-1} \equiv 1 \mod P$$ $$a^{P-2} \equiv a^{-1} \mod P$$ So we need $B^{P-2} \mod P$ in equation (i) which can be calculated by modular exponentiation

Gerry Myerson, can you edit this answer to format properly and add some details if you want?

$\endgroup$
  • $\begingroup$ Good! But, 1) you still need to calculate $A$ and $B$, each a product of as many as $10^5$ numbers, 2) Fermat's Little Theorem, as a way of finding an inverse modulo $p$, is vastly inferior to the (Extended) Euclidean Algorithm), and 3) DID YOU LOOK AT THE LINK TO LUCAS' THEOREM? $\endgroup$ – Gerry Myerson Feb 8 '16 at 11:55
  • $\begingroup$ 1) It is possible to calculate A and B in constant time by using A and B of previous $^nC_r$. Just multiply both A and B with a number (could be different for A and B) to get next A and B. 3) Lucas Theorem seemed to me little bit tougher. $\endgroup$ – Shadekur Rahman Feb 8 '16 at 12:33
  • $\begingroup$ Your question asked how to find a value, but now it seems you want to find all the values. If you just want to find one binomial coefficient modulo $p$, it's hugely inefficient to first find the 10,000 values before the one you want. Also, what exactly seems tough about the Lucas formula? $\endgroup$ – Gerry Myerson Feb 8 '16 at 21:47
  • $\begingroup$ I say, what seems tough about the Lucas formula? $\endgroup$ – Gerry Myerson Feb 10 '16 at 5:11
  • 1
    $\begingroup$ I never implemented it. Now I understand a little bit. Hopefully will be able to implement it in future. $\endgroup$ – Shadekur Rahman Feb 10 '16 at 11:12
-1
$\begingroup$

~~I'm editing in a note at the top of my response here, because defining row and column in the way that you have leads to a different sort of problem than what I have addressed. Apologies~~

~~The value you are looking for is (C+R-2)choose(R-1) where C and R are the row and column values in your examples.~~

The triangle diagram you have included is incorrectly labelled. The rows do not increase on the RHS in the same way that the columns increase on the LHS. Consider that the first row is the 0th row and the first column is the 0th column. So the 0th row has only 1 column. The 1st row has only 2 columns. The nth row has n+1 columns (because the first column of each row is the 0th column). That is, the rows go horizontally (starting from the top) and the columns go vertically (starting from the left); they are not angled as is shown in your diagram.

In your first example, the 3rd element on the 4th row has a value of 4, counting the row and column from 0. Using natural numbers, this would appear to be the 4th element of the 5th row.

In your second example, the 3rd row does not have a 5th column, and so the result of 15 is incorrect.

To answer your question, the best way to solve for any location in the triangle is by drawing it out or by calculating n!/r!(n-r)! Keep in mind that the row and column start at (0,0) and also that the triangle is horizontally symmetrical.

Here is my source for this answer: https://en.wikipedia.org/wiki/Binomial_coefficient

$\endgroup$
  • $\begingroup$ Welcome to MSE. Please use MathJax. $\endgroup$ – José Carlos Santos Feb 12 '18 at 7:41
  • $\begingroup$ Thanks José. I'm sorry not to use it. $\endgroup$ – Andrew M Feb 12 '18 at 7:53

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.