print all the catalan numbers from 0 to n n being the user input the catalan numbers are a sequence of positive integers that appear in many counting problems in combinatorics 1 such problems include counting 2 the number of dyck words of length 2n the number wellformed expressions with n pairs of parentheses e g is valid but is not the number of different ways n 1 factors can be completely parenthesized e g for n 2 cn 2 and abc and abc are the two valid ways to parenthesize the number of full binary trees with n 1 leaves a catalan number satisfies the following recurrence relation which we will use in this algorithm 1 c0 c1 1 cn sumci cni1 from i 0 to n1 in addition the nth catalan number can be calculated using the closed form formula below 1 cn 1 n 1 2n choose n sources 1 https brilliant orgwikicatalannumbers 2 https en wikipedia orgwikicatalannumber return a list of the catalan number sequence from 0 through upperlimit catalannumbers5 1 1 2 5 14 42 catalannumbers2 1 1 2 catalannumbers1 traceback most recent call last valueerror limit for the catalan sequence must be 0 base case c0 c1 1 recurrence relation ci sumcj cij1 from j 0 to i return a list of the catalan number sequence from 0 through upper_limit catalan_numbers 5 1 1 2 5 14 42 catalan_numbers 2 1 1 2 catalan_numbers 1 traceback most recent call last valueerror limit for the catalan sequence must be 0 base case c 0 c 1 1 recurrence relation c i sum c j c i j 1 from j 0 to i
def catalan_numbers(upper_limit: int) -> "list[int]":
    
    if upper_limit < 0:
        raise ValueError("Limit for the Catalan sequence must be ≥ 0")

    catalan_list = [0] * (upper_limit + 1)

    
    catalan_list[0] = 1
    if upper_limit > 0:
        catalan_list[1] = 1

    
    for i in range(2, upper_limit + 1):
        for j in range(i):
            catalan_list[i] += catalan_list[j] * catalan_list[i - j - 1]

    return catalan_list


if __name__ == "__main__":
    print("\n********* Catalan Numbers Using Dynamic Programming ************\n")
    print("\n*** Enter -1 at any time to quit ***")
    print("\nEnter the upper limit (≥ 0) for the Catalan number sequence: ", end="")
    try:
        while True:
            N = int(input().strip())
            if N < 0:
                print("\n********* Goodbye!! ************")
                break
            else:
                print(f"The Catalan numbers from 0 through {N} are:")
                print(catalan_numbers(N))
                print("Try another upper limit for the sequence: ", end="")
    except (NameError, ValueError):
        print("\n********* Invalid input, goodbye! ************\n")

    import doctest

    doctest.testmod()