ISourceCode

Make the frequent cases fast and the rare case correct

Dyck Words – Project Euler problem 15 (Variant) – use of Catalan Numbers

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

2 responses to “Dyck Words – Project Euler problem 15 (Variant) – use of Catalan Numbers

  1. chaitu0max November 24, 2011 at 2:34 pm

    can u give the program in c++ to print all the paths in above algorithm

  2. chinmaylokesh February 14, 2012 at 3:23 am

    Hmm, probably you can convert the java code.

    look at this
    https://chinmaylokesh.wordpress.com/2011/02/23/catalan-number-combinatorial-problem-print-all-valid-properly-opened-and-closed-n-pairs-of-parentheses/

    its a java program i wrote , it prints all the possible bracket sequences . replace ‘(‘ with ‘R’ and ‘)’ with ‘L’ . that should give u the paths in terms of R and L

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: