9. MAZE PATHS ABOVE DIAGONAL

In a square matrix of dimensions nn, we need to find the paths that lead from the lower left corner to the upper right corner such that they do not touch the diagonal line from lower left to lower right. In other words, the paths that stay on or above the main diagonal.

This problem is just like the Mountains and Valleys problem.
For above figure, some of the paths are shown in figure below.

The green path is represented as HHVV and the blue path is represented as HVVH.

All the paths possible for a grid of 3*3 are given below.

Only the paths marked with a tick are our desired paths because for them at no moment the number of H's is more than the number of V's.