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

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)$?

• You've double-subtracted the case, say, when $x_1=x_2$ and $x_3=x_4$ but $x_1\neq x_3$ Sep 14, 2015 at 15:15
• A side question: What is the value of $S(n,k,r)$ or a good approximation for it? Sep 14, 2015 at 15:16
• Generating function: The answer is the coefficient of $x^ky^n$ in $(1+x)(1+xy)\cdots(1+xy^r)$. Not sure how that helps... Sep 14, 2015 at 15:22

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.

• what is $[z^n]$? Sep 15, 2015 at 2:39