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?
Best Answer
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?