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}")
Comments
Comments are pre-moderated. Please be patient and your comment will appear soon.
There are currently no comments
New Comment