This is a followup to this question, where the difference between consecutive entries of the tuple is at most $\Delta$.
Question: Given $k, n, \Delta \in \mathbb{N}$, how many integer tuples $(x_1, \dots, x_k)$ are there such that:
- $1 \leq x_1 \leq x_2 \leq \cdots \leq x_{k-1} \leq x_k \leq n$
- $x_{i+1} - x_{i} \leq \Delta$ for all $i$
If we had only the first bullet point, the answer is available on the linked question above.
If we had only the second bullet point, I believe we could say that the amount of tuples is equal to $(1 + \Delta)^{k}$ because for each entry of the tuple we have $1 + \Delta$ options to choose the increase relative to the last entry.
But we have both restrictions simultaneously, so of course the amount of tuples is bounded above by the minimum of both values, but I'm stuck trying to find out the exact value.
Any help is appreciated! Thanks!
Let $z_0,z_1,\dots,z_k$ be variables defined by $z_i=x_{i+1}-x_i$, with the convention that $z_0=x_1-1$ and $z_k=n-x_k$ Note that $$ z_0+z_1+\dots+z_k=n-1,\\ z_0,z_n\ge 0,\\\tag 1 0\le z_i\le \Delta\quad\text{for }1\le i\le k-1 $$ The number of integer solutions to this system of equations and inequalities can be found using generating functions. It is the coefficient of $t^{n-1}$ in the generating function $$ (1+t+\dots+t^\Delta)^{k-1}(1-t)^{-2}=(1-t^{\Delta+1})^{k-1}(1-t)^{-(k+1)} $$ This coefficient is $$ \boxed{\sum_{i=0}^{\frac{k+n-1}{\Delta+1}}\binom{k-1}i(-1)^i\binom{k+(n-i(\Delta+1))-1}{k}.} $$
Edit: You can also count the solutions to $(1)$ using the principle of inclusion exclusion. Start by counting solutions to $(1)$ while ignoring the conditions $z_i\le \Delta$ for $1 \le i \le k-1$. Now you just want to count the number of series ways to choose non-negative integers $z_i$ summing to $n-1$; by stars-and-bars, this is $\binom{n-1+k}{k}$.
From these, we must subtract the bad solutions where some $z_i\ge \Delta+1$. If say $z_1\ge \Delta+1$, then looking at the variables $z_0,z_1-(\Delta+1),z_2,\dots,z_k$, then we have $k+1$ nonnegative variables summing to $n-1-(\Delta+1)$. The number of ways to choose the bad variable is $\binom{k-1}1$, and there are $\binom{n-1-(\Delta+1)+k}{k}$ ways to choose the bad solutions, so we must subtract $\binom{k-1}1\binom{n-1-(\Delta+1)+k}{k}$.
However, we have double subtracted the number of solutions with two bad variables. These must be added back in, then the triple bad solutions must be subtracted out, etc. Going all the way down, you arrive at the same summation as before.