2
$\begingroup$

What's the number of solutions to $x_1 + x_2 + x_3 + x_4 < 100$ with $x_1 \in (1,2,3,..)$, $x_2 \in (2,3,4,..)$ and $x_3, x_4 \in (3,4,5..)$.

So the plan of attack is to define an equality of $x_1 + x_2 + x_3 + x_4 + c = 100$ and then defining a one-to-one correspondence between this equality and the inequality we have to solve.

If we have no constraints on the variables then by the method of "stars and bars", we know that the equality above has $\binom{5+100-1}{100}= \binom{104}{100} $ solutions.

However, we have the following conditions:

$A: x_1 \geq 1$

$B:x_2 \geq 2$

$C: x_3 \geq 3$

So we define

$x_1' = x_1 - 1$

$x'_2 = x_2 - 2$

$x'_3 = x_3 + 3$

$x'_4 = x_4 + 3$

Then we get $x_1' + 1 + x_2' +2 + x_3' + 3 + x_4' + 3 + c = 100$, which gives us $$x_1' + x_2' + x_3' + x_4' + c = 91$$ where $x_1', x_2', x_3', x_4', c \geq 0 $ so the number of solutions is $\binom{91+5-1}{91} = \binom{95}{91}$.

However, I have two problems:

  • Is this what I wrote above correct?
  • What would be the one-to-one correspondence here between the equality and the inequality? I don't really see it.

edit: Perhaps the one-to-one correspondence would be $(x_1,x_2,x_3,x_4) \mapsto (x_1-1,x_2-2,x_3-3, x_4-3, c=100-(x_1+x_2+x_3+x_4)$?

$\endgroup$
3
  • $\begingroup$ Did you mean to write $x_3, x_4 \in (3, 4, 5, \ldots)$? $\endgroup$ May 13, 2017 at 22:02
  • $\begingroup$ @N.F.Taussig Yes, I'll correct that. $\endgroup$ May 13, 2017 at 22:03
  • 2
    $\begingroup$ Your approach is correct. The statement $x_3', x_4' = x_3, x_4 + 3$ was not clear until I read the following line and realized you meant that $x_3' = x_3 + 3$ and $x_4' = x_4 + 3$. $\endgroup$ May 13, 2017 at 22:07

2 Answers 2

0
$\begingroup$

Use generating functions: First note that the question is equivalent to finding the number of solutions such that $$ \begin{cases} x_1+x_2+x_3+x_4+x_5=100\\ 1\leq x_1\\ 2\leq x_2\\ 3\leq x_3,x_4\\ 0\leq x_5\\ \end{cases} $$ So the G.F. is $$ G(x)=(x+x^2+x^3+\ldots)(x^2+x^3+x^4+\ldots)(x^3+x^4+\ldots)^2(1+x+x^2+\ldots) $$ Now find the coefficient of $x^{100}$.

$\endgroup$
1
  • 2
    $\begingroup$ The O.P. solved the problem correctly. Also, you did not address the questions the O.P. posed. $\endgroup$ May 13, 2017 at 22:10
0
$\begingroup$

Another way to see your problem is to see it as a problem involving composition of a number. I do not want to give the solution but it would be much easier if you see this problem as composition.

Since your x$_{2}$ can only start from 2, you can replace x$_{2}$ by another variable x$_{2}$ = (x$_{2}^{'}$-1) which can start from one. Similarly, x$_{3}$ and x$_{4}$ can be shifted by 2 each so it would something like,

x$_{1}$ + x$_{2}$ + x$_{3}$ + x$_{4}$ $<$ 100

$\rightarrow$ x$_{1}$ + (x$_{2}^{'}$-1) + (x$_{3}^{'}$-2) + (x$_{4}^{'}$-2) $<$ 100 , where each variable can start from 1.

$\rightarrow$ x$_{1}$ + x$_{2}^{'}$ + x$_{3}^{'}$ + x$_{4}^{'}$$<$ 105 , which is just the composition of all the integers from 1 to 104 in 4 parts.

The composition of an integer 'n' in k parts is given by C(n-1,k-1). Now since k = 4, k-1 =3 and n varies from 4 to 104.

Add all of them up and you have the answer.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .