Number of Dyck Paths that touch the diagonal exactly $k$ times?

Have a look at Rukavicka's proof of $C_n=\frac{1}{n+1}\binom{2n}{n}$. He introduces the combinatorial concept of exceedance of a path and a path transform the increases/decreases the exceedance by one. Now consider what happens to the the number of crossings of the main diagonal when applying such transform, and the solution will be at hand.

As an alternative, we may consider Vandermonde's convolution. For instance, the following sum

$$ \sum_{a+b=n}\frac{1}{a+1}\binom{2a}{a}\frac{1}{b+1}\binom{2b}{b}, $$ is the coefficient of $x^n$ in $$ \left(\sum_{m\geq 0}\binom{2m}{m}\frac{x^m}{m+1}\right)^2 = \left(\frac{1-\sqrt{1-4x}}{2x}\right)^2 =\frac{1-2x-\sqrt{1-4x}}{2x^2}$$ i.e. the coefficient of $x^{n+1}$ in $\frac{1-\sqrt{1-4x}}{2x}$, that is again a Catalan number.

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.

The number of lattice paths, going from $(0,0)$ to $(n,n)$, with steps in ${(1,0),(0,1)}$, and remaining below or touching the diagonal is counted, as you said, by the Catalan Number $$ C(n) = \left( \begin{gathered} 2n \\ n \\ \end{gathered} \right) - \left( \begin{gathered} 2n \\ n + 1 \\ \end{gathered} \right) = \left( \begin{gathered} 2n \\ n \\ \end{gathered} \right) - \left( \begin{gathered} 2n \\ n - 1 \\ \end{gathered} \right) = \frac{1} {{n + 1}}\left( \begin{gathered} 2n \\ n \\ \end{gathered} \right) $$

Then, as shown in the sketch, the number of paths that remain below the diagonal without touching it, except at the extremes, is given by $$ N(n,1) = C(n - 1) = \left( \begin{gathered} 2n - 2 \\ n - 1 \\ \end{gathered} \right) - \left( \begin{gathered} 2n - 2 \\ n - 2 \\ \end{gathered} \right) = \frac{{\left[ {1 \leqslant n} \right]}} {n}\left( \begin{gathered} 2n - 2 \\ n - 1 \\ \end{gathered} \right) $$ where the square brackets indicates the Iverson bracket.
Here the number of touches is counted as $1$, corresponding to the number of distinct contact points minus one. So $$ N(n,0) = \left[ {0 = n} \right] $$ Clearly the number of paths below the diagonal, with exactly 1 touch in between, will be the convolution of two "no-intermediate-touch" paths ($m=1$) $$ N(n,2) = \sum\limits_{0\, \leqslant \,k\, \leqslant \,n} {N(k,1)N(n - k,1)} = \sum\limits_{1\, \leqslant \,k\, \leqslant \,n - 1} {\frac{1} {{k\left( {n - k} \right)}}\left( \begin{gathered} 2k - 2 \\ k - 1 \\ \end{gathered} \right)\left( \begin{gathered} 2n - 2k - 2 \\ n - k - 1 \\ \end{gathered} \right)} $$ and so on $$ N(n,m) = \sum\limits_{0\, \leqslant \,k\, \leqslant \,n} {N(k,m - 1)N(n - k,1)} $$ Computing the convolutions as above you obtain for $N(n,m)$ the matrix that corresponds to OEIS sequence A106566 (see also A033184 and A009766 ), whose row sums $=C(n)$ and which corresponds to the final formula given by Brian.