Dyck paths and Catalan numbers

A Dyck path can be described as a sequence of $$n$$ horizontal steps for which, at each step a vertical step of $$+1$$ or $$-1$$ is taken subject to the constraints that the vertical coordinate never decreases below its initial value and the number of "up" and "down" steps is equal. For example,

   /\/\
/\/    \

is a valid Dyck path (where / indicates an "up" step and \ a "down step), whereas

   /\/\/
/\/

and

    /\/\
/\ /    
  \

are not. The number of Dyck paths with $$2n$$ steps (clearly there must be an even number of steps) is given by the Catalan number,

C_n = \frac{1}{n+1}\left( \begin{array}{c}2n \\ n \end{array} \right)

The Catalan numbers are $1, 2, 5, 14, 42, 132, 429, \ldots$ for $n = 1, 2, 3, \ldots$ and occur in a large number of combinatorial problems. For example, in the number of full binary trees with $$n + 1$$ leaves, and the number of ways of balancing $$n$$ pairs of brackets, as demonstrated by the code below, which recursively generates Dyck paths for a given number of steps:

$ python3 make_paths.py 3

(naming the script make_paths.py and providing $$n$$ on the command line), generates:

  /\
 /  \
/    \
((()))

 /\/\
/    \
(()())

 /\
/  \/\
(())()

   /\
/\/  \
()(())


/\/\/\
()()()
C(3) = 5

The code:

import sys

def make_path(k, h, s):
    """Complete the Dyck path from k at height h in string s."""
    if k == 2*n:
        # We're done for this path.
        yield s
    if h < 2*n-k:
        # We can go up.
        for s2 in make_path(k+1, h+1, s +'/'):
            yield s2
    if h > 0:
        # We can always go down if we're above sea-level.
        for s2 in make_path(k+1, h-1, s + '\\'):
            yield s2

def make_mountains(s):
    """Make a mountain text sketch out of / and \."""
    dh = {'/': 1, '\\': -1}
    nx = len(s)
    ny = nx // 2
    # Start with a blank canvas nx wide and ny high.
    arr = [[' ']*nx for _ in range(ny)]
    h, c = -1, '/'
    for k in range(nx):
        if not(k and s[k] != s[k-1]):
            # If this step is the same as the last, take it
            # (otherwise, this step reverses the altitude change of the
            # last step, so there is no overall change in h.)
            h += dh[s[k]]
        arr[h][k] = s[k]
    # Join the array of characters together in one pretty multi-line string.
    ms = '\n'.join(''.join(arr[ny-h-1]) for h in range(ny))
    return ms

if __name__ == "__main__":
    n = int(sys.argv[1])
    N = 0
    for s in make_path(0, 0, ''):
        print(make_mountains(s))
        # Also depict the string as a Dyck word of balanced parentheses.
        print(s.replace('/', '(').replace('\\', ')'))
        N +=1
    # N should be a Catalan number: 1, 2, 5, 14, 42, 132, ...
    print(f"C({n}) = {N}")