Number of solutions to equation of varying size, with varying upper-bound range restrictions

Although the information in this answer has been provided repeatedly in mathSE, I have never observed the information provided at this level of detail. Therefore, I hope that the posted question is not deleted as a duplicate. That way, all future questions in this area may specifically refer to this answer as a stand-alone reference.

Identify all solutions to $x_1 + \cdots + x_k = n$ subject to the following constraints:

• $x_1, \cdots, x_k$ are all non-negative integers.
• $c_1, \cdots, c_k$ are all fixed positive integers.
• $x_i \leq c_i ~: ~i \in \{1,2,\cdots, k\}.$

Yes, the approach in the linked article generalizes well. To the best of my knowledge, there are two general approaches:

• Generating functions : which I know nothing about.

• Stars and Bars which is also discussed here combined with Inclusion-Exclusion.

First, I will provide the basic Inclusion Exclusion framework. Then, within this framework, I will apply Stars and Bars theory.

Let $A$ denote the set of all solutions to the equation $x_1 + \cdots + x_k = n ~: ~x_1, \cdots, x_k$ are all non-negative integers.

For $i \in \{1,2,\cdots, k\}$, let $A_i$ denote the subset of A, where $x_i$ is restricted to being $> c_i$. That is, $A_i$ represents the specific subset where the upper bound on $x_i$ is violated.

For any finite set $S$, let $|S|$ denote the number of elements in the set $S$.

Then it is desired to enumerate $|A| - |A_1 \cup \cdots \cup A_k|.$

Let $T_0$ denote $|A|$.

For $j \in \{1,2, \cdots, k\}$ let $T_j$ denote

$\displaystyle \sum_{1 \leq i_1 < i_2 < \cdots < i_j \leq k} |A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_j}|.$

That is, $T_j$ represents the sum of $\binom{k}{j}$ terms.

Then, in accordance with Inclusion - Exclusion theory, the desired enumeration is

$$\sum_{i = 0}^k (-1)^iT_i.$$

This concludes the description of the Inclusion-Exclusion framework.

All that remains is to provide a systematic algorithm for enumerating
$T_0, T_1, \cdots, T_k$.

Stars and Bars theory:

(1)
$T_0 = \binom{n + [k-1]}{k-1}.$

(2)
To enumerate $A_i$, you have to enumerate the number of solutions to $x_1 + \cdots + x_k = n ~: x_i > c_i$.

The standard approach is to set $y_i = x_i - (c_i + 1),$ with all of the rest of the variables $y_1, \cdots, y_k = x_1, \cdots, x_k,$ respectively.

Then, there is a one to one correspondence between the solutions that you are trying to enumerate and the solutions to

$y_1 + \cdots + y_i + \cdots + y_k = n - (c_i + 1) ~: ~$ each variable is restricted to the non-negative integers.

Here, $n - (c_i + 1) < 0$ implies that there are $0$ solutions.

Otherwise, per (1) above, the number of solutions is $\displaystyle \binom{n - [c_i + 1] + [k-1]}{k-1}.$

As defined, $T_1 = \sum_{i = 1}^k |A_i|$, so now, the procedure for enumerating $T_1$ is clear.

(3)
Consider how to enumerate $T_2$ which denotes

$\displaystyle \sum_{1 \leq i_1 < i_2 \leq k} |A_{i_1} \cap A_{i_2}|.$

That is, $T_2$ denotes the summation of $\binom{k}{2}$ terms.

I will illustrate how to specifically enumerate $|A_1 \cap A_2|$, with the understanding that this same approach should also be used on the other
$\displaystyle \left[ \binom{k}{2} - 1\right]$ terms.

The approach will be very similar to that used in (2) above.

Let $y_1 = x_1 - (c_1 + 1).$
Let $y_2 = x_2 - (c_2 + 1).$
Let $y_i = x_i ~: ~3 \leq i \leq k$.

Then, there is a one to one correspondence between $|A_1 \cap A_2|$ and the number of non-negative integer solutions to

$y_1 + y_2 + y_3 + \cdots + y_k = n - (c_1 + 1) - (c_2 + 1).$

Again, if $n - (c_1 + 1) - (c_2 + 1) < 0$, then the number of solutions $= 0$.

Otherwise, again per (1) above, the number of solutions is given by

$\displaystyle \binom{n - [c_1 + 1] - [c_2 + 1] + [k-1]}{k-1}.$

(4)
Now, consider how to enumerate $T_j ~: ~3 \leq j \leq k$ which denotes

$\displaystyle \sum_{1 \leq i_1 < i_2 < \cdots < i_j \leq k} |A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_j}|.$

That is, $T_j$ denotes the summation of $\binom{k}{j}$ terms.

I will illustrate how to specifically enumerate $|A_1 \cap A_2 \cap \cdots \cap A_j|$, with the understanding that this same approach should also be used on the other
$\displaystyle \left[ \binom{k}{j} - 1\right]$ terms, when $j < k$.

The approach will be very similar to that used in (3) above.

Let $y_1 = x_1 - (c_1 + 1).$
Let $y_2 = x_2 - (c_2 + 1).$
$\cdots$
Let $y_j = x_j - (c_j + 1).$
Let $y_i = x_i ~: ~j < i \leq k.$

Then, there is a one to one correspondence between $|A_1 \cap A_2 \cap \cdots \cap A_j|$ and the number of non-negative integer solutions to

$y_1 + y_2 + y_3 + \cdots + y_k = n - (c_1 + 1) - (c_2 + 1) - \cdots - (c_j + 1).$

Again, if $n - (c_1 + 1) - (c_2 + 1) - \cdots - (c_j + 1) < 0$, then the number of solutions $= 0$.

Otherwise, again per (1) above, the number of solutions is given by

$\displaystyle \binom{n - [c_1 + 1] - [c_2 + 1] - \cdots - (c_j + 1) + [k-1]}{k-1}.$

This completes the Stars and Bars theory.

Addendum
Shortcuts

Suppose, for example, that $c_1 = c_2 = \cdots = c_k$.

Then, to enumerate $T_j$, all that you have to do is enumerate
$|A_1 \cap A_2 \cdots \cap A_j|$.

When $j < k$, the other $\displaystyle \left[\binom{k}{j} - 1\right]$ terms will be identical.

Therefore, $T_j$ will enumerate as

$\displaystyle \binom{k}{j} \times |A_1 \cap A_2 \cdots \cap A_j|$.

Further, if only some of the variables $c_1, c_2, \cdots, c_k$ are equal to each other, you can employ similar (but necessarily sophisticated) intuition to presume that some of the $\binom{k}{j}$ terms will have the same enumeration.

Also, in practice, you typically don't have to manually enumerate each of $T_1, T_2, \cdots, T_k.$

The following concept is based on the assumption (which may be false) that
$(c_1 + 1) + (c_2 + 1) + \cdots + (c_k + 1) > n.$

Re-order the scalars $c_1, \cdots c_k$ in ascending order, as
$m_1 \leq m_2 \leq \cdots \leq m_k.$

Find the smallest value of $j$ such that $(m_1 + 1) + \cdots + (m_j + 1) > n$.

Then $T_j, T_{j+1}, \cdots, T_k$ must all equal $0$.