# 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
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}")

Current rating: 5