Enumerating number of solutions to an equation [duplicate]

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

If you consider the following function $$ f_{\rm dim}(\epsilon)=\left(\frac{1-\epsilon^{11}}{1-\epsilon}\right)^{4}, $$ and expand at $\epsilon=0$ then coefficient in front of $\epsilon^{32}$ will give you the correct result, 165.

Explanation of why this works is given in my answer to This question.

The method can be obviously applied to generic case: Suppose there is equation $$\sum_{i=1}^n x_i=M$$ and we demand constraints $\lambda_i\leq x_i\leq \Lambda_i$. Question is how many solutions are there?. The answer is to consider

$$ f_{\rm dim}(\epsilon)=\prod_{i=1}^n\frac{\epsilon^{\lambda_i}-\epsilon^{\Lambda_i+1}}{1-\epsilon}\,, $$ expand this function at $\epsilon=0$ and find the coefficient of expansion at $\epsilon^{M}$.

Definitely, this method is a very efficient approach to use on a computer, much faster than generating all possible permutations as was suggested in another answer to your question.

For your particular example, this method can be also used to perform a computation by hands (though it might be not the case in generic situation). The required coefficient is given by the contour integral $\oint\frac{d\epsilon}{2\pi\,i}\frac{f_{\rm dim}(\epsilon)}{\epsilon^{33}}$ around the origin. But this integral can be also computed by residue at $\epsilon=\infty$ (note that at $\epsilon=1$ there is no pole). For the purpose of finding $1/\epsilon$ term in the large $\epsilon$ epxansion, the replacement $1-\epsilon^{11}\to-\epsilon^{11}$ can be used:

$$ \left(\frac{1-\epsilon^{11}}{1-\epsilon}\right)^{4}\frac 1{\epsilon^{33}}\simeq\epsilon^{11\times 4-33}\frac 1{(1-\epsilon)^4}=\epsilon^7\left(\frac 1{1-\epsilon^{-1}}\right)^4\to\epsilon^7\times\epsilon^{-8}\binom{8+4-1}{4-1}=\frac{165}{\epsilon} $$ After all, the answer is computed by a single Binomial coefficient $\binom{8+4-1}{4-1}$. This gives us a possibility to guess a nice trick. Consider a solution to the equation

$$ y_1+y_2+y_3+y_4=8 $$ with the only constraint $y_i\geq 0$. Then $x_i=10-y_i$ will be a solution to the original equation. It is easy to check that this is one to one map (with given boundary requirements), so $\binom{8+4-1}{4-1}$, the number of solutions for equation on $y$'s, is the desired answer.

Answer 3

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

Answer 4

To maximize the value of this q&a I will assume that, by your asking for a "generalized approach", you were requesting that it work for any...

• # variables (NOT only 4) $=v$.
• Rhs (NOT only 32) $=n$.
• Lower bound (NOT only 0) $=l$.
• Upper bound (NOT only 10) $=u$.

---

My generalization will utilize generating functions (GF)s, coefficient extraction, power series, & evolve over 3 phases (w/ the results of phase 2 & 3 providing a solution to your particular example)...

1. Suppose we were solving (a problem like yours but w/o the upper limit you set @ 10)... $$ card\left(A\right) = card\left(\left\{(x_1,x_2,\ldots,x_v)\in\mathbb{W}^v : x_1 + x_2 + \cdots + x_v = n\right\}\right) $$ We have a linear equation of $v$ variables, w/ every coefficient equal to 1, so... $$ card\left(A\right) = \left[x^n\right]\left(x^0 + x^1 + \cdots\right)^v = \left[x^n\right]\left(\frac{1}{1 - x}\right)^v $$
2. Suppose we were solving (a problem like yours but w/ an upper limit)... $$ card\left(B\right) = card\left(\left\{(x_1,x_2,\ldots,x_v)\in A : x_i\leq u \right\}\right) $$ We have the same setup (as we did in 2) but w/ an upper limit, so... $$ card\left(B\right) = \left[x^n\right]\left(x^0 + x^1 + \cdots + x^u\right)^v = \left[x^n\right]\left(\frac{1 - xx^u}{1 - x}\right)^v $$
3. My final generalization is but a shadow of its most generalized form (made possible/easily-obtainable through the use of GFs): Suppose we were solving (a problem like yours but w/ arbitrary lower AND upper limits)... $$ card\left(C\right) = card\left(\left\{(x_1,x_2,\ldots,x_v)\in\mathbb{Z}^v : x_1 + x_2 + \cdots + x_v = n\;\land\;l\leq x_i\leq u\right\}\right) $$ We still have a linear equation of $v$ variables w/ every coefficient equal to 1, so... $$ card\left(C\right) = \left[x^{n - vl}\right]\left(x^0 + x^2 + \cdots + x^{u - l}\right)^v = \left[x^{n - vl}\right]\left(\frac{1 - xx^{u - l}}{1 - x}\right)^v $$

---

As mentioned in the beginning, the solution to your particular example is given (respectively) by the result of phase 2 or 3...

$$ \left[x^{32}\right]\left(\frac{1 - xx^{10}}{1 - x}\right)^4 = \left[x^{32 - 4\cdot 0}\right]\left(\frac{1 - xx^{10 - 0}}{1 - x}\right)^4 = 165 $$

---

I still consider myself the noob of noobs wrt generating functions but I knew enough to solve this simple example. I intend to keep studying them as they are a very powerful tool (I would even say THE most powerful tool wrt solving combinatorics questions) &, if your interested, this doc taught me everything I know.