Proper Brackets

Observe that a given bracket sequence of $n$ distinct brackets can be identified with two things: a permutation of the $n$ kinds of brackets, and a proper bracket sequence of $n$ identical brackets. Here, we call the original bracket sequence as varied sequence , and the resulting bracket sequence with only one kind of bracket as standardized sequence ; so a varied sequence is identified by a permutation of brackets and a standardized sequence. For example, the sequence ([]<{}>) can be identified by the permutation (), [], <>, {} and the bracket sequence (()(())) . To determine the permutation, we simply walk from left to right; each time we encounter a new bracket type, append it to the permutation. To determine the standardized sequence, just convert everything into the same bracket kind. To obtain the original varied sequence, walk the standardized sequence from left to right; every time we find an opening bracket, take the next element in the permutation and replace this opening bracket with its matching closing bracket with this type.

Every permutation and standardized sequence gives a unique varied sequence, and every varied sequence can be represented in such a way. Thus it's enough to count the number of pairs of permutations and standardized sequences. But the number of permutations is simply $n!$ ; there are $n$ kinds of brackets, and we arrange them in a row, so there are $n!$ such ways. And the number of standardized sequences is $C_n$ , the $n$ -th Catalan number. (This is well-known; one possible way to find this is to use the identity $C_{n+1} = \sum_{i=0}^n C_i C_{n-i}$ , and noticing that a standardized sequence of $n+1$ brackets must begin with an opening bracket, followed by a standardized sequence of $i$ brackets, followed by a closing bracket (this matches the first opening bracket), followed by the remaining $n-i$ brackets.)

Thus the number of varied sequences of $n$ brackets is simply $n! \cdot C_n = \frac{n!}{n+1} \binom{2n}{n} = \frac{(2n)!}{(n+1)!}$ . For $n = 8$ , this gives $\frac{16!}{9!} = \boxed{57657600}$ .