I was trying to solve this problem: How many ways can N pairs of parenthesis form K matching groups? By 'a group of matching parenthesis' I mean a sequence of matching parenthesis which can not be break apart, like this:
$(()(()))$ or $()$ or $(()())$
but not like this:
$()()$ or $(())()$
So for example, when N = 2, and K = 2, there's one possible way:
$()()$
N = 5, K = 3, 9 ways:
$()()(()()), ()()((())), ()(()())(), ()((()))(), (()())()(), ((()))()(), (())(())(), (())()(()), ()(())(())$
It's quite easy to figure out the straightforward way to compute this:
$$f_{k,n} = \sum_{i=0}^{n-1}f_{k-1,i}\times{}C_{n-i-1}$$
where $C_{i}$ is the i-th Catalan number.
But, by staring at the result of $f_{k,n}$, I discovered an interesting recurrence relation:
$$f_{k,n} = f_{k-1,n}-f_{k-2,n-1}$$
And I wonder if there's an intuitive way to explain this relation.
With a shift of index you can rewrite the relationship as
$$f_{k,n}=f_{k-1,n-1}+f_{k+1,n}\;.\tag{1}$$
Let $\mathscr{A}(k,n)$ be the set of strings of $n$ pairs of parentheses having $k$ blocks. Consider a string $\sigma\in\mathscr{A}(k,n)$. If the first block of $\sigma$ is $()$, then $\sigma=()\tau$ for some $\sigma'\in\mathscr{A}(k-1,n-1)$, and the map $\sigma\mapsto\sigma'$ is clearly a bijection from the set of $\sigma\in\mathscr{A}(k,n)$ whose first block is $()$ to $\mathscr{A}(k-1,n-1)$.
Otherwise the first two symbols of $\sigma$ are $(($, and $\sigma=(\tau)\rho$ for some non-empty $\tau$ and some $\rho$ with $k-1$ blocks. Let $\tau=\beta\gamma$, where $\beta$ is the first block of $\tau$, and define $\widehat\sigma=\beta(\gamma)\rho$; clearly $\widehat\sigma\in\mathscr{A}(k+1,n)$. Conversely, if $\eta\in\mathscr{A}(k+1,n)$, we can write $\eta$ uniquely in the form $\beta(\gamma)\rho$, where $\beta$ is the first block of $\eta$ and $\gamma$ may be empty, and it’s clear that $\eta=\widehat\sigma$ for $\sigma=(\beta\gamma)\rho$. Thus, the map $\sigma\mapsto\widehat\sigma$ is a bijection from the set of $\sigma\in\mathscr{A}(k,n)$ whose first block is not $()$ to $\mathscr{A}(k+1,n)$.
The union of these two maps is then a bijection from $\mathscr{A}(k,n)$ to $\mathscr{A}(k-1,n-1)\cup\mathscr{A}(k+1,n)$, and $(1)$ follows immediately.