(root 0,0) -->-->-->--> | | | | -->-->--> | | | -->--> | | --> | (leaf n,n)
At each point of the sequence, the number of "(" is no less than that of ")". So all possible states are nodes in the above figure. forward means adding a "(", and downward means adding a ")". Thus, there is a binary tree! with each node represented by a coordinate.
For n pairs, there are (n+2)(n+1)/2 = O(n^2). Can be
It's not a 'binary tree'. It's a half directional grid with 'forward' and 'downward' edges.
The number of valid permutations is equivalent to half the number of paths from left-highest node to right-lowest node.
The number of paths is A = number of combinations to choose n from 2n
= (2n)! / (n! * n!) = (1+1/n)(1+2/n)(1+3/n)...(1+n/n)
This number A: A > e^n and A<2^n. But it's still exponential.