0

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?

Shadekur Rahman
  • 45
  • Depends on what you mean by explicitly. Does constructing the Pascal triangle count? Or would a detour like the Beta function be preferred? – Tunococ Feb 06 '16 at 02:29
  • row and column number can be very large number like 10^15. So manually constructing pascal triangle is not a feasible solution. – Shadekur Rahman Feb 06 '16 at 02:36
  • And using binomial coefficients is somehow less preferred? Why? – JMoravitz Feb 06 '16 at 02:38
  • 3
    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. – David K Feb 06 '16 at 02:47
  • 1
    Exactly like David K said, if you want really $\binom nr$ with $n$ and $r$ very large numbers, you should use approximation. – Tunococ Feb 06 '16 at 02:53
  • you are right, David. More specifically I can say that I don't need exact value of nCr but modulo of nCr. – Shadekur Rahman Feb 06 '16 at 02:54
  • Tunococ, can you explain approximation or give a link? – Shadekur Rahman Feb 06 '16 at 02:56
  • 2
    "modulo"? Do you mean, you only need the remainder when you divide by some given prime $p$? Then what you want is Lucas' Theorem, https://en.wikipedia.org/wiki/Lucas%27_theorem – Gerry Myerson Feb 06 '16 at 03:54
  • So, Shadekur, is Lucas' Theorem what you wanted? – Gerry Myerson Feb 07 '16 at 08:20
  • I have used Fermat's Little theorem as modulo is done by a prime number. – Shadekur Rahman Feb 08 '16 at 09:02
  • How do you use Fermat's Little Theorem on a problem involving factorials? Please, if you have a solution, write it up and post it as an answer, so we can all see what you have done. – Gerry Myerson Feb 08 '16 at 10:12

2 Answers2

0

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?

Community
  • 1
Shadekur Rahman
  • 45
  • 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? – Gerry Myerson Feb 08 '16 at 11:55
  • 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.
    • – Shadekur Rahman Feb 08 '16 at 12:33
  • 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? – Gerry Myerson Feb 08 '16 at 21:47
  • I say, what seems tough about the Lucas formula? – Gerry Myerson Feb 10 '16 at 05:11
  • 1
    I never implemented it. Now I understand a little bit. Hopefully will be able to implement it in future. – Shadekur Rahman Feb 10 '16 at 11:12