Number of distinct solutions of $x_1+x_2+\dots+x_k=n$ with $0\le x_i\le r$

Question

Let $n,k,r$ be positive integers. Let $S(n,k,r)$ be the number of all solutions of the Diophantine Equation $x_1+x_2+\dots+x_k=n$ with $0\le x_i\le r$ for every $i\in \{1,2,\dots,k\}$?

How many of these solutions are distinct, that is, $x_i\ne x_j$ for $i\ne j$?

---

Let $T(n,k,r)$ be this number. Let $s\le k$. There are $\binom{k}{s}$ ways to select $s$ unknowns $x_i$. The number of solutions in which these $s$ unknowns are equal, seems to be $$\sum_{i=0}^{\lfloor \frac{n}{s}\rfloor}T(n-si,k-s,r)$$

So it seems:

$$T(n,k,r)=S(n,k,r)-\sum_{s=2}^n\sum_{i=0}^{\lfloor \frac{n}{s}\rfloor}\binom{k}{s}T(n-si,k-s,r).$$

Can we derive a formula for $T(n,k,r)$ from it?

It doesn't seem to be a good approach. Assuming $S(n,k,r)$ is known, is there a formula for $T(n,k,r)$?

Answer 1

For future reference here is a formula using the cycle index $Z(P_k)$ of the unlabeled set operator $\mathfrak{P}_{=k}:$

$$[z^n] Z(P_k)\left(1+z+\cdots +z^r\right).$$

This cycle index has OGF $$G(w) = \exp\left(a_1z-a_2\frac{z^2}{2}+a_3\frac{z^3}{3}-\cdots\right) = \exp\left(\sum_{l\ge 1} (-1)^{l-1} a_l \frac{w^l}{l}\right).$$

Doing the substitution for this particular case we obtain $$H(z, w) = \exp\left(\sum_{l\ge 1} (-1)^{l-1} \frac{w^l}{l} \sum_{q=0}^r z^{lq}\right) \\ = \exp\left(\sum_{q=0}^r \sum_{l\ge 1} (-1)^{l-1} \frac{w^l}{l} z^{lq}\right) \\ = \exp\left(\sum_{q=0}^r \log(1+wz^q)\right) \\ = \prod_{q=0}^r (1+wz^q).$$

We get for the answer $$[w^k] [z^n] H(z, w) = [w^k] [z^n] \prod_{q=0}^r (1+wz^q)$$ which matches what was observed in the comments.

Multiply by $k!$ if permutations are considered distinct.

Remark. Obviously this does not need PET and follows straightforwardly by inspection.