How to efficiently count specific regular bracket sequences?

Revision en1, by Noobish_Monk, 2024-04-03 01:01:44

I came up on a problem and got it to solving this one, but now I am stuck. Can someone help please?

How can we efficiently count the number of regular bracket sequences with length $$$2n$$$ that have first closing bracket on position $$$k + 1$$$ (any way faster than $$$O(nk)$$$ or $$$O(n^2))$$$?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Noobish_Monk 2024-04-03 01:01:44 343 Initial revision (published)