2
$\begingroup$

How many solutions are there to the equation $x_1+x_2+x_3+x_4+x_5=21$, where $x_i,i=1,2,3,4,5$, is a nonnegative integer such that $ 0 ≤ x_1 ≤ 3$, $1 ≤ x_2 < 4$, and $x_3 ≥ 15$? I tried it .My Approach-:

$ x_3=x_3'+15 \implies x_1+x_2+x_3'+15+x_4+x_5=21 \implies x_1+x_2+x_3'+x_4+x_5=6 \implies C(5+6-1,6)$ but stuck at finding $0 ≤ x_1 ≤3$

$1 ≤ x_2 ≤4$

please help!!!

$\endgroup$
2
$\begingroup$

Without resorting to multiple changes in the nomenclature of the variables,
pre-place $1$ in $x_2$ and $15$ in $x_3$, which change the problem to

$x_1 + x_2 + .... +x_5 = 5\:$ in non-negative integers, $\;x_1 \le3, x_2<3$

Without the last two constraints, the answer would be $\binom{5+5-1}{5-1}$

To take care of the two constraints, note that both can't be simultaneously violated, and exclude solutions that violate a constraint by placing $4\; in \;x_1\;\;XOR\;\; 3\;\; in\;\; x_2$

Thus final answer is $\binom94 - \binom54 - \binom64$


Added link

The link here might help you in dealing with "stars and bars" with various types of constraints.

$\endgroup$
1
$\begingroup$

Your approach seems to start well. I am assuming you consider $1\leq x_2 \leq 4$ and that you have five variables (was $x_6$ here from the beginning?)

What I would advise is to build a "tree" (consider disjonctive cases) of what would have been possible without these constraints. Here, I consider first the cases on $x_2$ and then on $x_1$

The number of solutions you would have had for $x_1=4$ and $1 \leq x_2 \leq 4$ is $\binom{3}{2}+4$ ($4$ more for the solutions where one of the other variables is equal to 2, and the first term for the case where two of them are equal to one).

The number of solutions you would have had for $x_1=5$ and $1 \leq x_2 \leq 4$ is $1$

The number of solutions you would have had for $x_1=6$ and $1 \leq x_2 \leq 4$ is $0$

The number of solutions you would have had for $x_2=0$ is $4^6$

The number of solutions you would have had for $x_2=5$ is $4$

The number of solutions you would have had for $x_2=6$ is $1$

Can you finish?

$\endgroup$
  • $\begingroup$ Edited my question .Thanks for pointing my mistake in the question @vincent $\endgroup$ – virat Aug 31 '16 at 10:11
0
$\begingroup$

Let $y_3 = x_3 -15$. We need the number of solutions to $x_1+x_2+y_3+x_4+x_5 = 21 - 15$ with $y_3 \geq 0$, $0 \leq x_1 \leq 3$ and $1 \leq x_2 <4$. The number of solutions is the coefficient of $x^6$ in \begin{align*} (1+x+x^2+x^3)&(x+x^2+x^3)(1+x+x^2+\cdots)(1+x+x^2+\cdots)(1+x+x^2+\cdots)\\ &= x(1+x+x^2+x^3)(1+x+x^2)(1+x+x^2+\cdots)^3 \\ &= x\left(\frac{1-x^4}{1-x}\right)(1+x+x^2)\left(\frac{1}{1-x}\right)^3\\ &= x(1-x^4)(1+x+x^2)(1-x)^{-4} \\ &=x(1-x^4)(1+x+x^2)\left(1+4x+\binom{5}{2}x^2+\binom{6}{3}x^3+ \cdots\right)\\ &= x(1+x+x^2-x^4-x^5-x^6)\left(1+4x+\binom{5}{2}x^2+\binom{6}{3}x^3+ \cdots\right)\\ \end{align*} Hence the coefficient is \begin{align*} -1-4+\binom{6}{3}+\binom{7}{4}+\binom{8}{5} = 106 \end{align*}

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