5
willol
7y

An interviewer recently asked me "how many 'valid' combinations can you do with N parenthesis, either closing or opening?" It sounds easy enough, yet I didn't manage to find the solution, apparently I was close enough using dynamic programming. Can you solve it ? :)

• 1
A 'valid' combination is when the parenthesis are correctly nested of course
(()()) is valid
(((()) is not
• 1
()()() ~ 111
()(()) ~ 12
(())() ~ 21
((())) ~ 3

With only nested singletons as above, this is just all the different ways to sum up to the number 3.

This is also this https://en.m.wikipedia.org/wiki/...
• 1
The answer might be the (N/2)th Bell number for N parens. The 3rd bell number is 5. There are 5 ways to do this for 6 parens.

https://en.m.wikipedia.org/wiki/...
• 0
@thejohnhoffer you might be right ! The interviewer said something about Cathar numbers
• 0
The formal question should be something akin to "Count the rooted trees with N terminal nodes" where N is half the number of parens.
• 0
@willol I can't find cathar numbers online, but I've found a series called the Caley numbers, which don't quite answer this question.
• 1
@willol Catalan numbers*
• 0
@matanl

Oh wow, it is the Catalan numbers!

The Bell numbers start
1,1,2,5,15....

The Catalan numbers start
1,1,2,5,14....

For 8 parens (index 4), I spent a long time just now searching for that extra 15th paren grouping. But this makes more sense- there are only 14. Thank you!
• 0
The key is that the Catalan numbers count the Noncrossing partitions while the Bell numbers count all the partitions.
• 0
@thejohnhoffer Look at third proof of catalan in wikipedia, I believe you can also get bell numbers subtletly modifying it
• 0
@matanl It will take me a lot of effort to understand that proof, let alone its relation to Bell numbers, but I do appreciate being pointed in that direction!
• 0
@matanl oh yeah, catalan not Cathar! My bad :)

I find it funny how this puzzle seems easy but isn't, at all !
• 0
Why the crap are these puzzles so common in interviews?

If I ran into this problem in a project, I could find an answer pretty quickly using Google.
• 0
@Ashkin mathematical thinking, to solve problems which nobody solved yet for example