Finding total amount of paths in a triangle grid (iterative without recursion)

Question

i have a given a triangle grid:

Triangle

For every point (i,j) with i+j being even:

Given recursive function

Now i need to write a iterative function that finds all possible paths from (0,0) to the point (2n,0) given that n ∈ N.

So my idea, written in pseudo code:

def path (i,j):
       
    paths = set()
    A = [ 1 for  x in range(j)]
    
    for x in range (i - len(A)):
          A.append (last)-(-1)
          A.append (-1)
    set.append(path)
 
    for i in range (i!):
          candidate = permutate(A)
          for i in range(len(A)):
              if sum (A [1: i]) < 0
                  break
          Paths.append(candidate)
    return len(paths)

i need to count the total amount of paths possible to (2n,0)

Answer 1

On a more mathy note, this problem is equivalent to a more famous problem- balancing parenthesis. Ever step up-right is a ( and ever step down-right is a ), with n parenthesis pairs, how many valid sequences of parenthesis are there?

The answer for n is the nth catalan number, which is nck(2n, n) - nck(2n, n+1) (nck being "n choose k"). In python, this comes out to-

from math import comb

def catalan(n):
    return comb(2*n, n) - comb(2*n, n+1)

So the answer to "How many distinct shortest paths from (0, 0) to (2n, 0) through my triangular grid are there?" is catalan(n).