1

I am trying to find trinomial coefficients and I want to avoid using negative index in my array. There will be instances whereby i or j will become negative and will return array out of bounds error. Is there anyway I can mirror the array contained in the negative indexes to a positive index?

Here’s the recursive formula: Recursion Formula

I recognize that T(0, -1) = T(0, 1) but how do I implement it?

example:

row 0: T(0, 0) = 1 , T(0, 1) = 0 ...

row 1: T(1, 0) = T(0, -1) + T(0, 0) + T(0, 1) , T(2, 0) ...

The trinomial coefficient T(n,k) is the coefficient of x^(n+k) in the expansion of (1+x+x^2)^n.

Trinomial triangle (middle index is 0, negative on the left of 0, positive on the right of 0):

enter image description here

Note: The code below iterates through the array from middle index 0 to the right.

public class ClassNameHere {
    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        int k = Integer.parseInt(args[1]);
        long[][] DP = new long[n + 1][k + 1];
        DP[0][0] = 1;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= Math.min(i, k); j++) {
                if (i == j || ((j == 0) && i < 2)) DP[i][j] = 1;
                else if (j < -i) {
                    DP[i][j] = 0;
                } else DP[i][j] = DP[i - 1][j];
            }
        }
        System.out.println(DP[n][k]);
    }
}

Now I am able to get the terms from T(0, 0) to T(1, 0) with my code but unable to continue past T(2, 0) onwards by adding T(1,0) + T(1, 1) + T(1, 2). When I tried to implement DP[i][j] = DP[i - 1][j - 1] + DP[i - 1][j] + DP[i - 1][j + 1], it returns ArrayIndexOutOfBoundsException again.. I think that something is wrong with the implementation of the above statement ^. Any suggestions on how to go on with this?

HC Tang
  • 31
  • 10

2 Answers2

1

You can populate such an array as follows: first create a new empty array with height n and width 2n+1, filled with zeros, and set the first entry at the upper midpoint to 1, then iterate over the rows and columns and set the other entries, each equal to the sum of the three entries above it:

T[i][j] = T[i-1][j-1] + T[i-1][j] + T[i-1][j+1];

Code:

int n = 7;
// new array filled with zeros
int[][] arr = new int[n][2 * n + 1];
// first entry
arr[0][n] = 1;
// iterate over the rows of the array
// starting from the second
for (int i = 1; i < arr.length; i++) {
    // iterate over the columns of the array
    // from the second to the penultimate
    for (int j = 1; j < arr[i].length - 1; j++) {
        // each entry is the sum of the three entries above it
        arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j] + arr[i - 1][j + 1];
    }
}

// output
for (int[] row : arr) {
    for (int cell : row)
        if (cell > 0)
            System.out.printf("%3d ", cell);
        else
            System.out.print("    ");
    System.out.println();
}

Output:

                              1                             
                          1   1   1                         
                      1   2   3   2   1                     
                  1   3   6   7   6   3   1                 
              1   4  10  16  19  16  10   4   1             
          1   5  15  30  45  51  45  30  15   5   1         
      1   6  21  50  90 126 141 126  90  50  21   6   1

See also: Finding trinomial coefficients using dynamic programming

0

I have found the cause.

It can be done by initializing the correct length in the 2D array.

long[][] tri = new long[n + 1][k + n + 1];

and using Math.abs() to handle instances where j index will flow to negative indices.

tri[i][j] = tri[i - 1][Math.abs(j - 1)] + tri[i - 1][j] + tri[i - 1][j + 1];
HC Tang
  • 31
  • 10