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 ? :)

A 'valid' combination is when the parenthesis are correctly nested of course
(()()) is valid
(((()) is not

()()() ~ 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/...

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/...

@thejohnhoffer you might be right ! The interviewer said something about Cathar numbers

The formal question should be something akin to "Count the rooted trees with N terminal nodes" where N is half the number of parens.

@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.

@willol Catalan numbers*

@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!

The key is that the Catalan numbers count the Noncrossing partitions while the Bell numbers count all the partitions.

@thejohnhoffer Look at third proof of catalan in wikipedia, I believe you can also get bell numbers subtletly modifying it

@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!

@matanl oh yeah, catalan not Cathar! My bad :)

I find it funny how this puzzle seems easy but isn't, at all !

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.

@Ashkin mathematical thinking, to solve problems which nobody solved yet for example