Number of particular paths of even length Let $W_n=\{ w=a_1a_2\cdots a_{2n}: a_i\in\{1,-1\},\ a_1+\cdots+a_j\geq 0,\ \forall\ 1\leq j\leq 2n\}$. Let $W_n^k=\{w\in W_n:w\ \text{does not cross the line}\ y=k  \}$. Is there any way to find $\# W_n^k$? 
Example: if $n=2$, then $\# W_2=6$ and $\# W_2^1=1$ and $\#W_2^2=4$. 
 A: Fix $k$ and let $a_{n,i}$ be the number of paths of length $n$ with step sizes $\pm 1$ that never leave the strip $\{0, 1, \ldots, k\}$ and end in state $i$, $0 \leq i \leq k$.  If $0 < i < k$, so $i$ is not on the boundary, there are two ways that we could have arrived at the state $i$: either from $i+1$ or $i-1$.  So $a_{n,i} = a_{n-1, i-1} + a_{n-1, i+1}$.  Furthermore, $a_{n, 0} = a_{n-1, 1}$ and $a_{n, k} = a_{n-1, k-1}$ since if we are on the bottom / top we must have come from just above / below.  Thus we have a linear recurrence.  If we write the recurrence as a matrix equation, we get (e.g., for k = 3) 
$$ \left( \begin{array}{cc}
a_{n, 0} \\
a_{n, 1} \\
a_{n, 2} \\
a_{n, 3} 
\end{array} \right) =
\quad
\left( \begin{array}{cccc}
0 & 1 & 0 & 0 \\
1 & 0 & 1 & 0 \\
0 & 1 & 0 & 1 \\
0 & 0 & 1 & 0 \\
\end{array} \right)\left( \begin{array}{cc}
a_{n-1, 0} \\
a_{n-1, 1} \\
a_{n-1, 2} \\
a_{n-1, 3} 
\end{array} \right)
$$
So inductively, 
$$ \left( \begin{array}{cc}
a_{n, 0} \\
a_{n, 1} \\
a_{n, 2} \\
a_{n, 3} 
\end{array} \right) =
\quad
\left( \begin{array}{cccc}
0 & 1 & 0 & 0 \\
1 & 0 & 1 & 0 \\
0 & 1 & 0 & 1 \\
0 & 0 & 1 & 0 \\
\end{array} \right)^n\left( \begin{array}{cc}
1\\
0 \\
0 \\
0 
\end{array} \right)
$$
since the path starts in state $0$.
Then you may quickly compute $a_{n,i}$, and $$\#W_n^k = \sum_{i=0}^k a_{2n, k}.$$  For $k = 3$ this gives OEIS sequence A001519. If you want an explicit formula, you could diagonalize the matrix; OEIS gives the formula $$(\phi^{2n-1} + \phi^{1-2n})/\sqrt{5},$$ $\phi=(1+\sqrt{5})/2$ the golden ratio.  I don't know whether there is a formula for general $k$.
