Can anyone solve this problem not using brute force? I'm so happy if somebody can help me.

A beautiful bit string is a string which can be described as a right bracket string, and lexicography order not larger than all of its bracket-circle-permutation. For example: 111000 -> ((())) is a beautiful string (110001 -> (()))( is not a right permutation), but 101 -> ()( is not, and 110010 is also not, because 110010 > 101100 and 101100 -> ()(()) is a bracket-circle-permutation of 110010.

(I have changed the problem set, this is my original problem, I realize that the last one I wrote is not enough to solve my original one.)

Count the number of beautiful strings with n bit. And let a n-bit beautiful string, count the number of beautiful strings which have lexicography order smaller than this. Of course, n is even.