# Combinatorics - Number of ways to move up and down a staircase

I like to solve combinatorics problems recreationally. I recently thought of the following and am having a lot of trouble wrapping my head around this:

Suppose you have a staircase with n many steps. For n seconds, you'll walk up and down this staircase, taking one step at a time. During the first second, you always begin on the first step. During each subsequent second, you can walk up one step, down one step, or stay where you are. The only exceptions are that if you are on the first step you cannot walk down any further, and if you are on the nth step you cannot walk up any further.

How many different ways can you walk up and down the steps?

Example: If n = 3, there are four ways. They are represented as 1-1-1, 1-2-1, 1-2-2, and 1-2-3.

You can define a function $N(n,k,p)$ which is the number of ways to be at step $k$ after $p$ steps on a staircase of $n$ steps. Now define a recurrence. For the middle steps you have $N(n,k,p)=N(n,k-1,p-1)+N(n,k,p-1)+N(n,k+1,p-1)$ For the end steps you remove one term. Now if you define a column vector $N(n,*,p)$ you can find a matrix $A$ so that $N(n,*,p)=AN(n,*,p-1)$ Since $A$ is symmetric it can be diagonalized and since it is tridiagonal it is easy. You can also make the recurrence in a spreadsheet. Each $N(n,k,p)$ is a polynomial of degree at most $n$ in $p$, so you can use the spreadsheet fitting to find the polynomial.