Number of balanced bracket sequences with given prefix and suffix

Question

I've been trying to solve the following problem:

Find the number of balanced bracket sequences of size $N+M+K$ which start with a prefix of $N$ continuous opening brackets and end with a suffix of $M$ continuous closing brackets (there can be any sequence of brackets of length $K$ as long as whole sequence is balanced).

I thought that maybe there is some correlation between this problem and Dyck paths/Catalan numbers but even after doing some research, I couldn't find any paper describing it in detail. Is it an already known (and well-studied) problem? Is there any formula for that? Thanks in advance!

Answer 1

These correspond to sort of possibly raised double-sided ballot paths, a rather straightforward variant of ballot paths, and that may be the reason you don't see many papers describing it. You might want to check some papers on tunnels in Dyck paths to see if you find more useful information.

Suppose at first that none of the initial $N$ brackets match any of the final $M$ brackets.

Think of this as Dyck paths of length $N+M+K$ starting with $N$ up-steps and ending at height $M$ down-steps. Remove the initial $N$ up-steps and final $M$ down-steps, and shine two lights horizontally from $-\infty$ and $\infty$ onto your path. This highlights $N$ down-steps and $M$ up-steps. This yields a unique decomposition of your remaining path $P$ of length $K$ starting at height $N$, ending at height $M$, and never going below the $x$-axis, as $$ D=P_Nd\dots P_2dP_1dRuQ_1uQ_2\dots uQ_M, $$ where the $u$'s and the $d$'s are the highlighted steps (they correspond to the brackets matching the initial $N$ opening brackets and final $M$ closing brackets), and $P_1,\dots,P_N, Q_1,\dots,Q_M,R$ are some Dyck paths of total semilength $\frac{K-N-M}{2}$.

Thus, the generating function for our paths over all $K$ is $$ x^{N+M}C(x)^{N+M+1}, $$ where $C(x)$ is the Catalan generating function, and we want the coefficient at $x^{N+M+\frac{K-N-M}{2}}=x^{\frac{K+N+M}{2}}$ in its power series, which is \begin{multline*} [x^\frac{K+N+M}{2}]x^{N+M}C(x)^{N+M+1}=[x^{\frac{K-N-M}{2}}]C(x)^{N+M+1}\\ =\frac{N+M+1}{\frac{K+N+M}{2}+1}\binom{K}{\frac{K+N+M}{2}}=\binom{K}{\frac{K+N+M}{2}}-\binom{K}{\frac{K+N+M}{2}+1}, \end{multline*} where the last equality follows e.g. from applying Lagrange inversion.

Now suppose exactly $L$ of the $N$ initial steps match $L$ of $M$ final steps, where $L\le\min(M,N)$. Then remove these $L$ pairs of matching brackets to arrive at the case considered above, but with $N\gets N-L$ and $M\gets M-L$, so our count in that case is $$ \frac{N+M+1-2L}{\frac{K+N+M}{2}+1-L}\binom{K}{\frac{K+N+M}{2}-L}=\binom{K}{\frac{K+N+M}{2}-L}-\binom{K}{\frac{K+N+M}{2}+1-L}. $$

Thus, our total count is $$ \begin{split} &\sum_{L=0}^{\min(M,N)}{\left(\binom{K}{\frac{K+N+M}{2}-L}-\binom{K}{\frac{K+N+M}{2}+1-L}\right)}\\ &=\binom{K}{\frac{K+N+M}{2}-\min(M,N)}-\binom{K}{\frac{K+N+M}{2}+1}. \end{split} $$ However, note that $\frac{K+N+M}{2}-\min(M,N)\in\left\{\frac{K-N+M}{2},\frac{K+N-M}{2}\right\}$ and these values sum to $K$, so it does not matter which one is used at the bottom of the binomial coefficient. Thus, our answer is $$ \binom{K}{\frac{K-N+M}{2}}-\binom{K}{\frac{K+N+M}{2}+1}. $$

Answer 2

Let $T = \frac{K+M+N}2$. Your expression has $T$ open brackets and $T$ closed brackets, corresponding to lattice walks in the plane from $(0,0)$ to $(T,T)$ which stay at or above the line $y=x$. Since you are requiring the path to start with $N$ open brackets and $M$ closed brackets, you can only freely choose the path from $(0,N)$ to $(T-M,T)$. The total number of paths, ignoring the $y=x$ restriction, is $$ \binom{(T-M)+(T-N)}{T-N}=\binom{K}{(K+M-N)/2}. $$ We must now subtract the bad paths from $(0,N)$ to $(T-M,T)$ which at some point hit the line $y=x-1$. If we reflect such a bad path at the first point it hits $y=x-1$, the reflected path will instead end at $(T+1,T-M-1)$ instead of $(T-M,T)$. Since reflection is a bijection, the number of bad paths is equal to the total number of paths from $(0,N)$ to $(T+1,T-M-1)$, which is$$\binom{(T+1)+(T-M-N-1)}{T+1}=\binom{K}{(K+M+N)/2+1}.$$ Therefore, the number of good paths is $$ \boxed{\binom{K}{(K+M-N)/2}-\binom{K}{(K+M+N)/2+1}.} $$