10
$\begingroup$

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?

$\endgroup$
20
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.