Number of solutions over positive integers of $x_1 + x_2 + ... + x_n = S$ for $x_i \in [0, 25]$ [duplicate]

Question

How many solutions are there to $x_1 + x_2 + ... + x_n = S$ for given $S$ assuming that $0 \le x_i \le 25$? I can solve it when there are no constraints on $x_i$ other that $x_i$ must be non-negative.

Answer 1

Assuming $n$ fixed.

Generating function approach

Let $a_s$ be the number of solutions for $x_1+\cdots+x_n=s$ with $0\leq x_i\leq 25$. Then:

$$\begin{align}\sum_{s=0}^\infty a_sz^s &= (1+z+z^2+\cdots+z^{25})^n\\ &=\frac{(1-z^{26})^n}{(1-z)^n} =(1-z^{26})^n\sum_{i=0}^{\infty}\binom{i+n-1}{n-1}z^i \end{align}$$

Using $(1-z^{26})^n=\sum_{j=0}^n \binom{n}{j}(-1)^jz^{26j}$, you get:

$$a_S = \sum_{j=0}^{n} (-1)^j\binom{n}{j}\binom{S+n-1-26j}{n-1}$$

Inclusion-Exclusion approach

Let $A$ be the set of all solutions $x_1+\cdots+x_n=S$, with only the condition that the $x_i\geq 0$.

Let $A_i$ be the elements of $A$ with $x_i\geq 26$.

Then you want the size of $A\setminus(A_1\cup A_2\cup\cdots\cup A_n)$. This is ideal for inclusion/exclusion.

You get:

$$\begin{align}|A\setminus(A_1\cup\cdots\cup A_n)|=&|A|\\&-(|A_1|+|A_2|+\cdots+|A_n|)\\ &+(|A_1\cap A_2|+|A_1\cap A_3|+\cdots +|A_{n-1}\cap |A_n|)\\ &\vdots\\ &+(-1)^n|A_1\cap A_2\cap \cdots \cap A_n| \end{align}$$

This will turn into the same formula as above. Each term in each row is the same, and there are $\binom{n}{j}$ terms in the $j$th row (starting with $j=0$ at $|A|$.)