I think this question has something to do with Catalan numbers but I'm not really sure. I want to find out the number of strings that consist of $n$ $L$'s and $n$ $R$'s, under the constraint that for any given prefix, the number of unmatched $L$'s is atmost $a$ and the number of unmatched $R$'s is atmost b.
$\begingroup$
$\endgroup$
8
-
$\begingroup$ Sorry the formulation is slightly disorienting for me. Why do you say "$n$ pairs"? Do you just mean words of even length in the two letter alphabet? $\endgroup$– მამუკა ჯიბლაძეCommented Jun 25, 2021 at 10:11
-
1$\begingroup$ But "n pairs" suggests more than "words of even length in the alphabet ${L,R}$. It suggests exactly $n$ instances of $L$ and exactly $n$ instances of $R$. Is that what you mean? $\endgroup$– Nathan ReadingCommented Jun 25, 2021 at 12:26
-
5$\begingroup$ This is the same as walks from $(0,0)$ to $(2n,0)$ with steps of the form $(1,1)$ and $(1,-1)$ that never go above the horizontal line $x=a$ and never go below the horizontal line $x=-b$. $\endgroup$– Sam HopkinsCommented Jun 25, 2021 at 13:47
-
1$\begingroup$ Assuming that an $L$ can only be matched with a later $R$ (like parentheses), this is not quite the same as walks staying between $x=a$ and $x=-b$. For example, the string $RRRRLLLL$ stays between $x=0$ and $x=-4$, yet it has four unmatched $L$'s and $R$'s. $\endgroup$– Mike EarnestCommented Jun 28, 2021 at 0:56
-
1$\begingroup$ @MikeEarnest: True; OP should clarify. $\endgroup$– Sam HopkinsCommented Jun 28, 2021 at 1:48
|
Show 3 more comments