0

The number of valid parenthesis expressions that consist of $n$ right parentheses and $n$ left parentheses is equal to the $n^\text{th}$ Catalan number. If we restrict that in every point，the sum of right parentheses - the sum of left parentheses is less than k. How many the valid parenthesis expressions?

ehds
  • 101
  • What does nn mean here? – coffeemath Dec 02 '19 at 07:51
  • 1
    Sorry,I have edited it,it means it has n right parentheses.for example $(())())$,there are 3 right parentheses and 3 left. – ehds Dec 02 '19 at 09:22
  • Do you still keep that number of parens (left plus right) totals to $2n$? Also are you interested in the more symmetric restriction $|R=L|<k,$ with $R$ right and $L$ left parens? [or replace $<$ by $\le$]? – coffeemath Dec 02 '19 at 12:46
  • Yes,for example n=6, k=3,Then ()()()() is valid,but ((())) is invalid,because in the first 3 bracketis, they are all left,so the sum of left minus the sum of right is equal to 3 (3>=3),so this expression is invalid. – ehds Dec 02 '19 at 13:05
  • 1
    See https://oeis.org/A080936 . – Travis Willse Dec 03 '19 at 00:02

0 Answers0