CODEWITHSUNDEEP
mathcombinationscomputer-sciencecombinatoricscalculation
reByte
reByte

Reputation: 93

How to calculate all possible combinations of brackets order

I would like to find out a formula on calculating the maximum possible combinations of brackets order.

First of all there a few rules: - Brackets have to be valid (Every bracket has a closing bracket) - n % 2 == 0 (n = Brackets, only pairs) - The order is sensitive, e.g.: a,b and b,a equals 2 combinations

What is a valid combination ? Lets say n is our variable for the brackets count:

n = 2: () - Only 1 combination possible

n = 4 () (), (()) - Only 2 combinations possible

n = 6 ((())), () () (), (()()), (())(), ()(()) - 5 possible combinations

Now any ideas how to calculate the combinations number when I only have n = ?

Greetings

Upvotes: 0

Views: 1276

Answers (1)

MBo
MBo

Reputation: 80287

You can calculate number of valid combinations using table approach.

One dimension of table refers to overall number of brackets in sequence, second dimension refers to number of left brackets, so table cell might be denoted as F(a, l).

You can add right bracket to sequence if 2 * l > a

You can add left bracket to sequence if 2 * l < n

So fill table cell by cell and get result as F(n, n/2)

There is known formula (Catalan) for number of valid bracket sequences but I suppose that you have to calculate it with simple math logic.

Upvotes: 1

Related Questions