In how many ways can you order (with repetition) elements from $\{0, 1, 2, 3, ..., k\}$ in $s > k + 1$ spots such that the difference between $2$ consecutive elements is $0$ or $1$?
These are some of my ideas:
- Define $s-1$ new variables (call them $m_i$) that represent the differences between $2$ consecutive numbers. Now think of the number of ways of ordering $0$'s and $1$'s across these $m_i$'s and the number of ways to get $a_{i + 1} - a_i = m_i$ where $a_i \in \{0, 1, 2, 3, ..., k\}$. The problem with this is that I'm not being able to account for the fact that the $a_{i + 1}$ for $m_i$ is equal to the $a_{i}$ for $m_{i + 1}.$
- Stars and Bars: Sum over all possible summations of the $m_i$'s listed above where all possible bounds on the variables are considered. In the best case, this perhaps yields nested sums.
- Principle of inclusion-exclusion: There are $s^{k + 1}$ total permutations, representing the universal set. Of these, I need to find the union of all permutations s.t. the difference between $2$ elements is not $0$ nor $1$. The number of sets and intersections to consider is making this a big challenge.
- Recursion: This has the problem of not necessarily being a linear constant-coefficient homogeneous relation which can reduce the likelihood of forming a general formula. Moreover, I'm unable to construct one.
Fundamentally, I'm unable to break down this question into accessible cases to work with. What I find especially frustrating is that choosing a $0$ or $k$ gives $2$ possible choices for the next number while all the numbers in between give $3$ choices. Accounting for every case while the pattern changes sporadically is something I'm not being able to control.
Your problem can be stated in terms of graph theory. Consider the graph whose vertex set is $\{0,1,\dots,k\}$, where two vertices $x,y\in \{0,\dots,k\}$ are connected by an edge if and only if $|x-y|\le 1$ (meaning there is a loop joining every vertex to itself). Then your problem is equivalent to counting the number of walks of length $s-1$ in this graph (the length of a walk is the number of edges, which is one less than the number of vertices).
Let $A_k$ be the $(k+1)\times(k+1)$ matrix where $A_{ij}=1$ when $|i-j|\le 1$, and $A_{ij}=0$ otherwise. This is the adjacency matrix for this graph. It is well known that the number of walks of length $\ell$ from vertex number $i$ to vertex number $j$ in a graph with adjacency matrix $A$ is the $(i,j)$ entry of $A^\ell$. Therefore, the answer to your question is $$ \sum_{i=0}^k\sum_{j=0}^k(A^{s-1})_{i,j} $$ Equivalently, if we let ${\bf 1}=[1\;1\;\dots\;1]$ be the row vector with $k+1$ ones, then the number of sequences is $$ {\bf 1}\cdot A^{s-1}\cdot {\bf 1}^\top $$