How many valid parenthesis combinations?

Question

We have:

• n1 number of {} brackets ,

• n2 number of () brackets ,

• n3 number of [] brackets ,

How many different valid combination of these brackets we can have?

What I thought: I wrote a brute force code in java (which comes in the following) and counted all possible combinations, I know it's the worst solution possible,

(the code is for general case in which we can have different types of brackets)

Any mathematical approach ?

Note 1: valid combination is defined as usual, e.g. {{()}} : valid , {(}){} : invalid

Note 2: let's assume that we have 2 pairs of {} , 1 pair of () and 1 pair of [], the number of valid combinations would be 168 and the number of all possible (valid & invalid) combinations would be 840

static void paranthesis_combination(char[] open , char[] close , int[] arr){
    int l = 0;
    for (int i = 0 ; i < arr.length ; i++)
        l += arr[i];
    l *= 2;
    paranthesis_combination_sub(open , close , arr , new int[arr.length]  , new int[arr.length], new StringBuilder(), l);
    System.out.println(paran_count + " : " + valid_paran_count);
    return;
}


static void paranthesis_combination_sub(char[] open , char[] close, int[] arr , int[] open_so_far , int[] close_so_far, StringBuilder strbld , int l){
    if (strbld.length() == l && valid_paran(open , close , strbld)){
        System.out.println(new String(strbld));
        valid_paran_count++;
        return;
    }
    for (int i = 0 ; i < open.length ; i++){
        if (open_so_far[i] < arr[i]){
            strbld.append(open[i]);
            open_so_far[i]++;
            paranthesis_combination_sub(open , close, arr , open_so_far , close_so_far, strbld , l);
            open_so_far[i]--;
            strbld.deleteCharAt(strbld.length() -1 );
        }
    }
    for (int i = 0 ; i < open.length ; i++){
        if (close_so_far[i] < open_so_far[i]){
            strbld.append(close[i]);
            close_so_far[i]++;
            paranthesis_combination_sub(open , close, arr , open_so_far , close_so_far, strbld , l);
            close_so_far[i]--;
            strbld.deleteCharAt(strbld.length() -1 );
        }
    }
    return;
}

Answer 1

Cn is the nth Catalan number, C(2n,n)/(n+1), and gives the number of valid strings of length 2n that use only (). So if we change all [] and {} into (), there would be Cn1+n2+n3 ways. Then there are C(n1+n2+n3,n1) ways to change n1 () back to {}, and C(n2+n3,n3) ways to change the remaining () into []. Putting that all together, there are C(2n1+2n2+2n3,n1+n2+n3)C(n1+n2+n3,n1)C(n2+n3,n3)/(n1+n2+n3+1) ways.

As a check, when n1=2, n2=n3=1, we have C(8,4)C(4,2)C(2,1)/5=168.

Answer 2

In general, infinitely. However I assume, that you meant to find how many combinations are there provided limited string length. For simplicity lets assume that the limit is an even number. Then, lets create an initial string:

(((...()...))) with length equal to the limit.

Then, we can switch any instance of () pair with [] or {} parenthesis. However, if we change an opening brace, then we ought to change the matching closing brace. So, we can look only at the opening braces, or at pairs. For each parenthesis pair we have 4 options:

• leave it unchanged

• change it to []

• change it to {}

• remove it

So, for each of (l/2) objects we choose one of four labels, which gives: 4^(l/2) possibilities.

EDIT: this assumes only "concentric" parenthesis strings (contained in each other), as you've suggested in your edit. Intuitively however, a valid combination is also: ()[]{} - this solution does not take this into account.