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

Comments
  • 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
Add Comment