- 512,586 hits
Make the frequent cases fast and the rare case correct
Dyck Words – Project Euler problem 15 (Variant) – use of Catalan Numbers
February 23, 2011Posted by on
Cn is the number of Dyck words of length 2n. A Dyck word is a string consisting of n X’s and n Y’s such that no initial segment of the string has more Y’s than X’s (Dyck language). For example, the following are the Dyck words of length 6: – Wikipedia
XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY.
Re-interpreting the symbol X as an open parenthesis and Y as a close parenthesis, Cn counts the number of expressions containing n pairs of parentheses which are correctly matched:
((())) ()(()) ()()() (())() (()()) – check this article for some code.
Problem 15 – Project Euler
Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.
If we modify this question to find paths which do not pass above the diagonal or paths which do not pass below the diagonal.
Then solution is a Catalan Number
Cn is the number of monotonic paths along the edges of a grid with n × n square cells, which do not pass above the diagonal. A monotonic path is one which starts in the lower left corner, finishes in the upper right corner, and consists entirely of edges pointing rightwards or upwards. Counting such paths is equivalent to counting Dyck words: X stands for “move right” and Y stands for “move up”. The following diagrams show the case n = 4: – Wikipedia