C_{n} 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

C_{n} 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

### Like this:

Like Loading...

*Related*

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

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