What is the number of integer sequences of length $T$ with fixed endpoints?

Question

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.

Answer 1

The question asked is a special case of a general combinatorial enumeration problem.

Given a finite alphabet of symbols $A = \{a,b,\dots,z\}$, define $A^*$ to be the set of all finite strings (or words) over the alphabet $A$. Define $A^n$ to be the set of strings $w=w_1w_2\dots w_n$ of length $n=|w|$ in $A^*$. Given a numerical weight (or score) function on symbols $s:A\to\mathbb{Z}$, extend it to all finite strings with

$$ s(w) := \sum_{i=1}^{|w|} s(w_i). \tag1 $$

Given a formal variable $x$, define the generating function of a set of strings $L\subseteq A^*$ to be

$$ s(L) := \sum_{w\in L}x^{s(w)}. \tag2 $$

Verify the result that

$$ s(A) = \sum_{\lambda\in A} x^{s(\lambda)}, \qquad s(A^n) = s(A)^n. \tag3 $$

The question asked is equivalent to determining the generating function of $A^n$ where here

$$ A = \{a,b,c\},\quad s(a)=-1, s(b)=0, s(c)=1. \tag4 $$

Use the result in equation $(3)$ to get

$$ s(A^n) = (x^{-1}+1+x)^n = x^{-n}(1+x+x^2)^n. \tag5 $$

The coefficients of this trinomial are given in the OEIS sequence $A027907$ as

$$ \sum_{k=0}^{2n} T(n,k)\,x^k := (1+x+x^2)^n\tag6 $$

and one of several formulas given for this trinomial coefficient is

$$ T(n,k) = \sum_{j=0}^n {\binom n j} {\binom j {k-j}}. \tag7 $$