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

  • $\begingroup$ You've double-subtracted the case, say, when $x_1=x_2$ and $x_3=x_4$ but $x_1\neq x_3$ $\endgroup$ Sep 14, 2015 at 15:15
  • $\begingroup$ A side question: What is the value of $S(n,k,r)$ or a good approximation for it? $\endgroup$
    – DirkGently
    Sep 14, 2015 at 15:16
  • 2
    $\begingroup$ 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... $\endgroup$ Sep 14, 2015 at 15:22

1 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.