I am studying Combinatorics from Richard Brualdi and I am unable to think about this particular question.
Its hint is given in Question 2 of this image.
Unfortunately I am not able to think how to use that hint.
One solution is given on MSE of this question but it doesn't uses the hint given in the book (image) and i have serious doubts in it because approach is different. So, can anybody please help with the solution using that hint.
The sequences in the hint are directly related both to Dyck paths and to legally nested parentheses, both of which are counted by Catalan numbers. Map the $+1$ terms to northeast edges in the Dyck path, or to open parentheses; map the $-1$ terms to southeast edges, or to close parentheses. The needed condition on the sequences is that the partial sums be non-negative. This corresponds to the property that a Dyck path never goes below the east-west line, or to the property that the cumulative number of close parentheses never exceeds the cumulative number of open parentheses in a properly nested expression.
Thinking in terms of legally nested parentheses, we can associate, for example, the expression (()())() with the array $$ \begin{bmatrix}1 & 2 & 4 & 7\\ 3 & 5 & 6 & 8\end{bmatrix}. $$ The first row of the array contains the positions of the open parentheses, in increasing order, and the second row contains the positions of the close parentheses, in increasing order. Clearly the $j^\text{th}$ close parenthesis comes after the $j^\text{th}$ open parenthesis, which implies that the array has all desired properties. Going from arrays to properly nested expressions is similarly straightforward.