Balls in Bins with Bounded Discrepancy How many ways are there to distribute N balls into M ordered bins, with the constraint that the number of balls in two adjacent bins differs by at most one? Letting $n_i$ be the number of balls in the $i$th bin, this discrepancy constraint requires that $|n_i - n_j| \leq 1$ for all $i,j \in [M]$ such that $|i - j| \leq 1$.
Without the discrepancy constraint, I know the answer can be computed easily using stars and bars. However, I'm stuck on how to solve it with the discrepancy constraint.
 A: I do not think there is a formula per se, but I can find a sort of modular generating function for the number of ways. I did need to use the simplifying assumtion $N>M^2/2$ discussed in the comments.
Let $N\newcommand{\mod}{\,\%\,}\mod M$ denote the remainder of $N$ divided by $M$, so $0\le N\mod M\le M-1$.

Theorem: Suppose that $N>\binom M2$. Then the number of ways to write $N=n_1+n_2+\dots+n_M$, where each $n_i$ is a nonnegative integer such that $|n_i-n_{i+1}|\le 1$ for each $i\in \{1,\dots,M-1\}$, is equal to the coefficient of $x^{N\mod M}$ in the polynomial
$$\prod_{i=1}^{M-1}(1+x^i+x^{M-i})\pmod {x^M-1}$$

For each $i\in \{1,\dots,M\}$, define
$$
d_i:=n_i-n_{i-1}
$$
with the special case that $d_1=n_1$. This means that
$$
n_i=d_1+d_2+\dots+d_i
$$
which further implies
$$
N=\sum_{i=1}^Mn_i=\sum_{i=1}^M\sum_{j=1}^id_j=\sum_{j=1}^Md_j\sum_{i=j}^M1=\sum_{j=1}^M(M-j+1)d_j
$$
Now, let us look at this equation modulo $M$. Note that the first summand on the RHS is $M\cdot d_1$, which is zero $\pmod M$. Therefore,
$$
N\equiv \sum_{j=2}^M (M-j+1)d_j\equiv-\sum_{j=1}^{M-1}jd_{j+1}\pmod M
$$
Furthermore, each $d_{j+1}$ is constrained to be in $\{-1,0,1\}$. So, when choosing the $(j+1)^\text{st}$ factor, we can decide whether or not to increase the sum by $j$, to decrease it by $j$, or to leave the sum unchanged. This is exactly captured by the generating function in the Theorem statement. When expanding that product, and choosing the factor from the term $(1+x^i+x^{M-i})$, we are deciding whether or not $d_{i+1}$ is equal to $0,+i,$ or $-i$. Remember, $-i\equiv M-i\pmod M$.
Finally, once we have chosen $d_2,\dots,d_M$ such that $N\equiv -\sum_{j=1}^{M-1}jd_j\pmod M$ is satisfied, you can always choose $d_1$ such that $N=\sum_{j=\color{blue}0}^{M-1}(M-j)d_{j+1}$ holds with actual equality. Since increasing $d_1$ by one has the effect of increasing the sum by $M$, you can simply start with $d_1=0$, and increment $d_1$ until equality is achieved. Since $N>\binom M2$, we know that the final result is an actual legal placement of balls into bins, in the sense that each $n_i\ge 0$.
