Calculate element in matrix incrementally, using neighbors

Question

I have this Java problem, which I suspect it relates to a higher-level algorithm, but my searches haven't been able to come up with anything practical.

You construct an array as follows:

1
1   1
1   2   1
1   3   3   1
1   4   6   4   1
1   5   10  10  5  1

Basically, A_i,j = A_i-1,j-1+A_i-1,j. It's supposed to return the element at index (l, c): for (4, 1) it should return 4, (5, 2) returns 10, etc. My solution is straightforward, but it is not enough:

static long get(int l, int c){
    long[][] matrix = new long[l+1][l+1];
    matrix[0][0]=1;
    matrix[1][0]=1; 
    matrix[1][1]=1;
    for(int i=2;i<=l;i++){
        matrix[i][0]=1;
        for(int j=1;j<=i;j++){
            matrix[i][j] = matrix[i-1][j-1]+matrix[i-1][j];
        }   
    }
    return matrix[l][c];
}

It doesn't work for large values of l and c. Using BigInteger doesn't work. My searches have led me to loop skewing and scalarization, but I don't know where to start. Any steer in the right direction is really appreciated.

PS: Sorry for the newbie-vibe, this is my first question!

Answer 1

You are describing Pascal's triangle, for which a closed formula exists:

matrix[n][k] = n!/(k! * (n-k)!)

P.S. If these numbers seem familiar, it is because they are also from the binomial theorem, where the common examples are:

(x+y)^2 = 1* x^2 + 2xy + 1*y^2
(x+y)^3 = 1*x^3 + 3*xy^2 + 3yx^2 + 1*y^3

Answer 2

You don't need to use a loop, this is simply pascal's triangle, the formula:

(n, k) = n! / ( k! * (n-k)!)

Will generate your answer for the position (n, k).