I find it easier to work with up-down paths, defined as sequence of up-steps (e.g., from $\langle m,n\rangle$ to $\langle m+1,n+1\rangle$) and downsteps (e.g., from $\langle m,n\rangle$ to $\langle m+1,n-1\rangle$). A Dyck path is then an up-down path that does not go below the $x$-axis, and there are $C_n$ Dyck paths from $\langle 0,0\rangle$ to $\langle 2n,0\rangle$.
If $n,n'\ge 0$, $m<m'$, and $t\ge 0$, let $\mathscr{D}(m,n,m',n',t)$ be the set of Dyck paths from $\langle m,n\rangle$ to $\langle m',n'\rangle$ that hit the $x$-axis exactly $t$ times, and let $d(m,n,m',n',t)=|\mathscr{D}(m,n,m',n',t)|$. Thus, $d(0,0,2n,0,2)=C_n$.
Suppose that $t\ge 1$, and $0\le k<t$. Let $P\in\mathscr{D}(m,n,m',n',t)$. Let the points where $P$ hits the $x$-axis be $\langle\ell_i,0\rangle$ for $i=1,\ldots,t$, where $\ell_1<\ldots<\ell_t$. Since $P$ is a Dyck path, $P$ has an up-step immediately after each of these points except possibly the last. Remove the first $k$ of these up-steps, and translate the resulting path upwards $k$ units to get a path $\hat P$; it’s straightforward to check that $\hat P\in\mathscr{D}(m,n+k,m'-k,n',t-k)$: the path has been shortened by $k$ steps, and the first $k$ hits have been eliminated.
This procedure is reversible. If $P\in\mathscr{D}(m,n+k,m'-k,n',t-k)$, we first shift $P$ down by $k$ units to get an up-down path $P'$. For $i=1,\ldots,k$ let $\ell_i$ be minimal such that $\langle\ell_i,1-i\rangle$ is on $P'$. Let $Q$ be the up-down path obtained from $P'$ by inserting an up-step immediately after each of the points $\langle\ell_i,1-i\rangle$. Then $Q\in\mathscr{D}(m,n,m',n',t)$, and $Q=\hat P$. It follows that
$$d(m,n,m',n',t)=d(m,n+k,m'-k,n',t-k)\;.$$
In particular,
$$d(0,0,2n,0,k+1)=d(0,k,2n-k,0,1)=d(0,0,2n-k,k,1)\;.$$
This bijection between paths $P$ and $\hat P$ is the up-down version of the correspondence that is very, very badly described at your CodeChef link, where its author writes ‘This mapping is same as decreasing value of $y$ for a path when it touches a diagonal’.
Each path in $\mathscr{D}(0,0,2n-k,k,1)$ must begin with an up-step; if we remove this up-step and shift the path one unit down and to the left, we get a Dyck path from $\langle 0,0\rangle$ to $\langle 2n-k-1,k-1\rangle$. Conversely, any Dyck path from $\langle 0,0\rangle$ to $\langle 2n-k-1,k-1\rangle$ becomes a path in $\mathscr{D}(0,0,2n-k,k,1)$ if we shift it one unit up and to the right and prepose an up-step. Thus,
$$d(0,0,2n-k,k,1)=\sum_{t\ge 1}d(0,0,2n-k-1,k-1,t)\;.$$
Each up-down path from $\langle 0,0\rangle$ to $\langle 2n-k-1,k-1\rangle$ corresponds to a possible sequence of $2n-k-1$ votes, $n-1$ of them for candidate $A$ and $n-k$ of them for candidate $B$. On this interpretation the Dyck paths in $\mathscr{D}(0,0,2n-k-1,k-1,1)$ correspond to the sequences in which candidate $A$ is never behind candidate $B$. Calculating the number of such paths is essentially the ballot problem.
Clearly there are $\binom{2n-k-1}{n-1}$ up-down paths from $\langle 0,0\rangle$ to $\langle 2n-k-1,k-1\rangle$. If $P$ is one of these paths that is not a Dyck path, there is a least $\ell$ such that $\langle\ell,-1\rangle$ is on the path $P$. Reflect the initial segment of $P$ between $\langle 0,0\rangle$ and $\langle\ell,-1\rangle$ in the line $y=-1$; the result is a path $P'$ from $\langle 0,-2\rangle$ to $\langle 2n-k-1,k-1\rangle$ that first hits the line $y=-1$ at $x=\ell$. Note that if this initial segment has $u$ up-steps, then it has $u+1$ down-steps, and the rest of $P$ has $n-1-u$ up-steps. As a result, $P'$ has $(n-1-u)+(u+1)=n$ up-steps and $n-k-1$ down-steps.
Conversely, if $P$ is an up-down path from $\langle 0,-2\rangle$ to $\langle 2n-k-1,k-1\rangle$ that first hits the line $y=-1$ at $x=\ell$, reflecting the first $\ell$ steps of $P$ in the line $y=-1$ produces an up-down path $Q$ from $\langle 0,0\rangle$ to $\langle 2n-k-1,k-1\rangle$ that first hits the line $y=-1$ at $x=\ell$, and it’s clear that $Q'=P$. Every up-down path from $\langle 0,-2\rangle$ to $\langle 2n-k-1,k-1\rangle$ hits the line $y=-1$, and there are $\binom{2n-k-1}{n}$ such paths (since each has $n$ up-steps and $n-k-1$ down-steps). Thus, the number of up-down paths from $\langle 0,0\rangle$ to $\langle 2n-k-1,k-1\rangle$ that are not Dyck paths is $\binom{2n-k-1}n$, and
$$\begin{align*}
d(0,0,2n,0,k+1)&=\binom{2n-k-1}{n-1}-\binom{2n-k-1}n\\
&=\binom{2n-k-1}{n-k}-\binom{2n-k-1}{n-k-1}\\
&=\binom{2n-k-1}{n-k}\left(1-\frac{n-k}{n}\right)\\
&=\binom{2n-k-1}{n-k}\frac{k}n\;.
\end{align*}$$
The Dyck paths in $\mathscr{D}(0,0,2n,0,k+1)$ correspond naturally to the paths in the plane from $\langle 0,0\rangle$ to $\langle n,n\rangle$ using only right-steps and up-steps that hit the diagonal exactly $k-1$ times between the two endpoints, or $k+1$ times including the endpoints.
Best Answer
$f$ generates the Riordan numbers, OEIS A005043, and the combinatorial proof of their Catalan-like recurrence below is adapted from Bernhart's Catalan, Motzkin and Riordan numbers listed as a reference there.
Bernhart defines a short bush as a rooted ordered tree that is either trivial ($0$) or where all internal vertices have at least two children. If $b(n)$ is the number of such bushes with $n$ edges, $b(n)$ satisfies the same Catalan-like recurrence as $f(n)$ through the following almost-bijection between short bushes with $n+1$ edges and ordered pairs of short bushes with $n$ total edges:
Descend into the leftmost child of each vertex from the root $r$ of a short bush $B$ until encountering
There exists an inverse to this map, but $(B_{2k},0)$ has no inverse. The existence of these unmatchable objects adds $1$ to $b(n)$ when $n$ is even and subtracts $1$ when it is odd, thus showing the Catalan-like recurrence.
$b(n)$ is in turn equivalent to the number of "feasible" non-crossing partitions of $n$ objects, where no part uses two consecutive items when the items form a circle, and from there equivalent to $f(n)$ through the following bijections:
Postorder-traverse the edges, using unbroken paths under this order as part labels. Then preorder-traverse the edges and write the part labels in this order around a circle – since we started with a short bush, it is easy to prove that the resulting partition is feasible non-crossing.
Now given a feasible non-crossing partition, form its dual by interlacing new items between the old ones and grouping them into new parts using the old partitions as boundaries. The aforementioned property guarantees that the dual partition is non-crossing with no singletons (which would arise iff a part of the old partition used consecutive items), completing the $b(n)=f(n)$ proof.