Trinomial Coefficients in Python

Question

Trying to figure out a dynamic programming way to return the trinomial coefficients.

I'm confused on how to get the value of the rows. I was able to set up the structure of the rows. The number of values in the row is the row number + 2. I can't figure out the code for the real values, so I just have placeholder values.

I know the middle value in the row is the sum of the row above, ignoring the 1s on the side. I know some formula like you go up 1, and diagonal 1 and add those values to get the value underneath, but I don't how to put that into code.

def Trinomial_Triangle(Number_of_Rows):
    Triangle = [[1]]
    Length_of_Row = 1

    for Outer_Index in range(Number_of_Rows - 1):

        Temporary_Array = [0] + Triangle[Outer_Index] + [0]
        print("Temporary Array", Temporary_Array)
        Length_of_Row += 2
        Values_in_Row = []

        for First_Inner_Index in range(Length_of_Row):

            Value = Triangle[Outer_Index][0]

            Values_in_Row.append(Value)
        Triangle.append(Values_in_Row)
    return Triangle


print(Trinomial_Triangle(5))

Answer 1

You can just do something like that:

def trinomial_triangle(num_of_rows):
    triangle = [[1]]
    for outer_idx in range(num_of_rows):
        prev_row = [0, 0] + triangle[outer_idx] + [0, 0]
        triangle.append([])
        for idx in range(1, len(prev_row) - 1):
            triangle[-1].append(sum(prev_row[idx - 1: idx + 2]))
    return triangle

print(trinomial_triangle(5))

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]]

---

I padded the last row with 4 zeros - two of each side:

• One to create the length of the new row
• One for padding for the sum of the 3 values above (to avoid extra steps for the first and last values)

Then I summed the 3 values from the prev row (one before and one after the current index) and appended it to the last list in triangle.

The trinomial triangle is a variation of Pascal’s triangle. The difference between the two is that an entry in the trinomial triangle is the sum of the three (rather than the two in Pascal’s triangle) entries above it

You can read more about trinomial triange and how to create it in this article