Let $T, n_1, n_2 \in \mathbb{Z}$ s.t. $T \geq 1$ be fixed. Consider the set
$$\mathcal{P}(0, T - 1, n_1, n_2) = \Big\{x:\{0, 1, \dots, T - 1\} \to \mathbb{Z} \space \Big| \space \big(x(0) = n_1\big) \wedge \big(x(T - 1) = n_2\big) \wedge \forall i \in \big\{0, 1, \dots, T - 2\big\} \space \big(|x(i + 1) - x(i)| \leq 1\big)\Big\}$$
i.e. the set of integer sequences of length $T$ with fixed endpoints that vary only in increments of $-1$, $0$, and $1$. The problem is to find $\big|\mathcal{P}(0, T - 1, n_1, n_2)\big|$, the size of the set. I suspect the result is well-known, but I figured I'd try my hand at it. Here's my attempt:
For a given sequence $x \in \mathcal{P}(0, T - 1, n_1, n_2)$, define $\Delta x: \{0, 1, \dots, T - 2\} \to \{-1, 0, 1\}$ as
$$\Delta x(i) = x(i + 1) - x(i)$$
Notice that
$$\sum_{i = 0}^{T - 2}\Delta x(i) = \sum_{i = 0}^{T - 2}\big(x(i + 1) - x(i)\big) = n_2 - n_1$$
There are three cases to consider:
Case 1: $T - 1 < |n_2 - n_1|$
In this case, $\big|\mathcal{P}(0, T - 1, n_1, n_2)\big| = 0$.
Case 2: $T - 1 = |n_2 - n_1|$
In this case, $\big|\mathcal{P}(0, T - 1, n_1, n_2)\big| = 1$.
Case 3: $T - 1 > |n_2 - n_1|$
This is the most interesting case. Let $N_-$ denote the number of $-1$ increments in this sequence, $N_0$ the number of $0$'s, and $N_+$ the number of $1$'s. We have that
$$0 \leq N_- \leq T - 1, \space \space \space 0 \leq N_0 \leq T - 1, \space \space \space 0 \leq N_+ \leq T - 1$$ $$N_- + N_0 + N_+ = T - 1, \space \space \space N_+ - N_- = n_2 - n_1$$
Then for any fixed $N_+$, we must have that
$$N_0 = (T - 1) + (n_2 - n_1) - 2N_+, \space \space \space N_- = N_+ - (n_2 - n_1)$$
It then follows that
$$n_2 - n_1 \leq N_+ \leq (T - 1) + (n_2 - n_1), \space \space \space \frac{1}{2}(n_2 - n_1) \leq N_+ \leq \frac{1}{2}\big[(T - 1) + (n_2 - n_1)\big]$$
Which yields the following sharp bounds on $N_+$:
$$\max(0, n_2 - n_1) \leq N_+ \leq \Big\lfloor\frac{1}{2}\big[(T - 1) + (n_2 - n_1)\big]\Big\rfloor$$
Now, for any fixed number $N_+$ of $1$'s, there will be exactly
$$\frac{(T - 1)!}{N_+!\big[(T - 1) - N_+\big]!}$$
distinct ways of arranging the $1$'s in a sequence of length $T - 1$. Similarly, there will be exactly
$$\frac{\big[(T - 1) - N_+\big]!}{\big[N_+ - (n_2 - n_1)\big]!\big[(T - 1) + (n_2 - n_1) - 2N_+\big]!}$$
distinct ways of arranging the $-1$'s in the remaining spaces. The rest of the spaces must be occupied by $0$'s. Therefore, the number of sequences with a fixed $N_+$ is
$$\frac{(T - 1)!}{N_+!\big[N_+ - (n_2 - n_1)\big]!\big[(T - 1) + (n_2 - n_1) - 2N_+\big]!}$$
And then the total number of sequences is given by summing over all allowed values of $N_+$ in the allowed range.
Is this correct, or did I make a mistake somewhere? It seems to work for some simple cases, but the number of possibilities grows rapidly enough with $T$ that checking the result by hand is impractical.
