2
$\begingroup$

Find the number of solutions to $x_1 + \ldots + x_5 = 26$ for $x_k \leq 10$

The answer is
$$\binom{30}4 - \binom{5}1 \binom{19}4 + \binom{5}2\binom{8}4$$

by Inclusion-Exclusion principle.

However, why can't I just simply use the substitution $y_k = 10-x_j \geq 0$
to count number of solutions to
$$y_1 + \ldots + y_5 = 50 - 26 = 24$$ for $y_k \geq 0$?

This would be
$$\binom{28}4.$$

$\endgroup$
4
  • 1
    $\begingroup$ If $y_k=10-x_k$ then $0\leq y_k\leq10$ (so not only $y_k\geq0$). Sometimes the trick works. This if the new outcome (here $24$) is such that condition $y_k\leq10$ is automatically satisfied. $\endgroup$
    – drhab
    Oct 9, 2017 at 12:21
  • 1
    $\begingroup$ You are counting the solution $(y_1,\cdots,y_5)=(20,1,1,1,1)$ in the second method, no? But this does not correspond to an acceptable choice of $x_i$. $\endgroup$
    – lulu
    Oct 9, 2017 at 12:21
  • $\begingroup$ Oh I see. So because $x_k\leq 10$ will (usually) mean also $0 \leq x_k \leq 10$, then I can't do substitutions like I could for conditions like $x_k \geq a$? $\endgroup$
    – Natash1
    Oct 9, 2017 at 12:25
  • 1
    $\begingroup$ If $x_k\geq a$ then usually you can substitute $y_k=x_k-a$ resulting in a condition of nonnegative. $\endgroup$
    – drhab
    Oct 9, 2017 at 12:32

2 Answers 2

Reset to default
3
$\begingroup$

When restrictions like $x_i\leq\square$ or $x_i\geq\square$ are encountered we should subtract the opposite situations from all the results, but we have to be careful about the maximal amount of numbers we can equate to $10$ ,here it is $2$ we will evaluate it firstly for each $1$ $x_i$ and then two different $x_i$ $x_j$ ; the whole situations are:$$\dbinom{26+5-1}{5-1}$$ and the situations in which $x_i\geq 11$ are to be subtracted: $$x_1'+11+x_2+\cdots+x_5=26$$ from here $$5\dbinom{15+5-1}{5-1}$$ (we added the $5$ because we substitude $11$ for each $x_i$ and now we do it for $2$;$$x_1'+11+x_2'+11+x_3+\cdots+x_5=26$$ that is; $$\dbinom{5}{2}\dbinom{4+5-1}{5-1}$$ and now we bring them together with; $$\dbinom{30}{4}-5\dbinom{19}{4}+\dbinom{5}{2}\dbinom{8}{4}$$ (This $+$ and $-$ thing is a principle driver from sets $s(A\cup B)=s(A)+s(B)-s(A\cap B)$ we have multiplied a $-$ up there)(P.S I have used that the integer solutions for $x_1+\cdots+x_r=n$ , $\dbinom{n+r-1}{r-1}$

$\endgroup$
1
$\begingroup$

Since $$ 0\leq x_j\leq 10 $$ then $$ 10\geq10-x_j\geq0 $$ which implies that the substitution does not change anything.

$\endgroup$
3
  • 2
    $\begingroup$ Something has changed: the summation must now equalize $24$ instead of $26$. Unfortunately that does not help much here, but there are cases where it does help. See here for example. $\endgroup$
    – drhab
    Oct 9, 2017 at 12:29
  • $\begingroup$ Cool ! The substitution works there. I never meet that example before. $\endgroup$
    – Le YAN
    Oct 9, 2017 at 12:36
  • $\begingroup$ Yes. If you meet problems like this then it is a good custom to check whether the trick will make the problem more simple. $\endgroup$
    – drhab
    Oct 9, 2017 at 12:41

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.