Enumerating number of solutions to an equation

Question

How do you find the number of solutions like this?

$$x_1 + x_2 + x_3 + x_4 = 32$$

where $0 \le x_i \le 10$.

What's the generalized approach for it?

Answer 1

First you calculate the number of solutions in non-negative integers without worrying about the upper bound of $10$ on each variable. This is a standard stars-and-bars problem, reasonably well explained in the Wikipedia article. Then you use the inclusion-exclusion principle to get rid of the unwanted solutions.

In this case the first step gives you a preliminary figure of $$\binom{32+4-1}{4-1}=\binom{35}3=6545\;.$$

Now count the number of solutions that make $x_1$ too big. This means that $x_1\ge 11$, so the excess over $11$ in $x_1$ plus the values of $x_2,x_3$, and $x_4$ must add up to $32-11=21$. Each of these unwanted solutions therefore corresponds to a solution in non-negative integers to the equation $y_1+y_2+y_3+y_4=21$, and there are $$\binom{21+4-1}{4-1}=\binom{24}3=2024$$ of those. In fact there are $2024$ unwanted solutions for each of the four variables, so our next approximation is $6545-4\cdot2024=-1551$ solutions.

Of course this obviously isn’t right. The problem is that some solutions exceed the cap of $10$ on more than one variable. Every solution that exceeds the cap on two variables was removed twice when we subtracted $4\cdot 2024$ and therefore has to be added back in. Consider a solution that has both $x_1$ and $x_2$ greater than $10$. Then the excess in $x_1$, the excess in $x_2$ and the values of $x_3$ and $x_4$ must sum to $32-2\cdot11=10$, so we’re essentially counting solutions in non-negative integers to the equation $y_1+y_2+y_3+y_4=10$, of which there are $$\binom{10+4-1}{4-1}=\binom{13}3=286\;.$$ There are $\binom42=6$ pairs of variables, so we must add back in $6\cdot286=1716$ to get a better approximation of $-1551+1716=165$ solutions.

It’s impossible for more than two variables to exceed their quotas, since $3\cdot11=33>32$. Thus, no further corrections are needed, and the final answer is $165$ solutions meeting the original boundary conditions.

Answer 2

In GAP, they can be computed via:

R:=RestrictedPartitions(32,[0..10],4);
S:=Union(List(R,r->Arrangements(r,4)));;
Size(S);

which gives 165.

Note that the first step generates unordered partitions of 32 into 4 parts, which I call $R$. Then I need to permute them in all possible ways, and take their union to create all possibilities, $S$.