It seems that there will be no better statement of the problem, so i will give an answer in the same shape. We answer the special case in the framework of the more general case describe below.
We start with a $K\times N$ empty matrix, so there are
- $K$ rows, numbered from $1$ to $K$,
- $N$ columns, numbered from $1$ to $N$,
- $KN$ "cells",
- and build an ordered graph on the cells, from the cell $(k,n)$ we can pass to one of the following cells $(k+1, n-1)$, $(k+1, n+)$, $(k+1, n+1)$, with the condition that the resulted cell lives in the given empty matrix.
The question wants the number $c(K,N)$ of all maximal paths starting from the first column (i.e. from some cell $(k,1)$) to the last column.
We define here the more specialized numbers
$c_i(K,N)$ of all path as above, that start from $(i,1)$, where $i$ can be taken "up to the middle", so that we can use the obvious symmetry of the margins. (So $c_1=c_K$, $c_2=c_{K-1}$ and so on.)
The problem wants in these notations
$$
c(5,5)=
c_1(5,5)+c_2(5,5)+c_3(5,5)+c_2(5,5)+c_1(5,5)\ .
$$
We have obviously
$$
\begin{bmatrix}
c_1(5,N+1)\\
c_2(5,N+1)\\
c_3(5,N+1)\\
c_2(5,N+1)\\
c_1(5,N+1)
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 & 0 & 0 & 0\\
1 & 1 & 1 & 0 & 0\\
0 & 1 & 1 & 1 & 0\\
0 & 0 & 1 & 1 & 1\\
0 & 0 & 0 & 1 & 1
\end{bmatrix}^N
\begin{bmatrix}
c_1(5,1)\\
c_2(5,1)\\
c_3(5,1)\\
c_2(5,1)\\
c_1(5,1)
\end{bmatrix}
$$
or simpler, but with less symmetry
$$
\begin{bmatrix}
c_1(5,N+1)\\
c_2(5,N+1)\\
c_3(5,N+1)\\
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 & 0\\
1 & 1 & 1\\
0 & 2 & 1
\end{bmatrix}^N
\begin{bmatrix}
c_1(5,1)\\
c_2(5,1)\\
c_3(5,1)
\end{bmatrix}\ .
$$
The answer is thus using the simpler version
$$
\begin{bmatrix}
2&2&1
\end{bmatrix}
\begin{bmatrix}
1 & 1 & 0\\
1 & 1 & 1\\
0 & 2 & 1
\end{bmatrix}^4
\begin{bmatrix}
1\\1\\1
\end{bmatrix}
=
259
\ .
$$
So there are $259$ paths in the graph, assuming they are equally probable, the asked probability is $1/259$.
[sage][1] code computing the above number:
sage: q = matrix( 1, 3, [2,2,1] )
sage: A = matrix( 3, 3, [1,1,0, 1,1,1, 0,2,1] )
sage: v = matrix( 3, 1, [1,1,1] )
sage: q*A^4*v
[259]
(Sage computes also the minimal polynomial, we do not have a "simple diagonalization" of the one or the other matrix written above, so for computational reasons the result should be enough.)
