216 views

Find the number of possible solutions for $x,y,z$ for each the following cases.

$Case\ 1.$    Case of unlimited repetition.

$x + y +z = 10$ and $x \geq 0\ , y \geq 0,\ z \geq 0$

$Case\ 2$   Case of unlimited repetition with variable lower bounds

$x + y +z = 10$ and $x \geq 1\ , y \geq 2 \ , z \geq 3\$

$Case\ 3$    case when upper bounds and lower bounds are given , no variable can be greater than upper bound.

$x + y +z = 10$ and $10 \geq x \geq 0\ , \ 10 \geq y \geq 0 \ , 10 \geq z \geq 0\$

$Case\ 4$    case when upper bounds and lower bounds are given , lower bounds are different, no variable can be greater than upper bound

$x + y +z = 10$ and $10 \geq x \geq 1\ , \ 10 \geq y \geq 2 \ , 10 \geq z \geq 3\$

$Case\ 5$    case when upper bounds and lower bounds are given , only 1 variable can be greater than upper bound in the invalid case that gives correct sum like 11+2+3 = 16

$x + y +z = 16$ and $10 \geq x \geq 0\ , \ 10 \geq y \geq 0 \ , 10 \geq z \geq 0\$

$Case\ 6$    case when upper bounds and lower bounds are given , lower bounds are different ,only 1 variable can be greater than upper bound in the invalid case that gives correct sum like 11+2+3 = 16

$x + y +z = 16$ and $10 \geq x \geq 1\ , \ 10 \geq y \geq 2 \ , 10 \geq z \geq 3\$

$Case\ 7$    case when upper bounds and lower bounds are given , only 2 variable can be greater than upper bound in the invalid case that gives correct sum  like 11+11+3 =25

$x + y +z = 25$ and $10 \geq x \geq 0\ , \ 10 \geq y \geq 0 \ , 10 \geq z \geq 0\$

$Case\ 8$    case when upper bounds and lower bounds are given , lower bounds are different ,only 2 variable can be greater than upper bound in the invalid case that gives correct sum like 11+11+3 =25

$x + y +z = 25$ and $10 \geq x \geq 1\ , \ 10 \geq y \geq 2 \ , 10 \geq z \geq 3\$

$Case\ 9$   case when upper bounds and lower bounds are given , lower bounds are different ,all variable can be greater than upper bound in the invalid case that gives correct sum like 11+11+11 = 33

$x + y +z = 33$ and $10 \geq x \geq 1\ , \ 10 \geq y \geq 2 \ , 10 \geq z \geq 3\$

$Case\ 10$    case when upper bounds and lower bounds are given , and both upper bound and lower bounds are variable.

$x + y +z = 10$ and $8 \geq x \geq 1\ , \ 20 \geq y \geq 2 \ , 12 \geq z \geq 3\$

| 216 views
+2
Basically your question appears to be
how many solutions are there for $x+y+z=s$ where $l_1\le x\le r_1$, $l_2\le y\le r_2$ and $l_3\le z\le r_3$ ? [$x,y,z,s \in \mathbb{Z}$ and $\forall i ~(l_i,r_i) \in \mathbb{Z}$]

The general approach is to find the coefficient of $a^s$ in the expansion of the following expression below.

$(a^{l_1}+a^{l_1+1}+a^{l_1+2}+\cdots+a^{r_1})(a^{l_2}+a^{l_2+1}+a^{l_2+2}+\cdots+a^{r_2})(a^{l_3}+a^{l_3+1}+a^{l_3+2}+\cdots+a^{r_3})$

Here, the coefficient of $a^s$ will be the required answer.
0
yes but there are cases when upper bounds are not defined
+4
In those cases, $r_1, r_2, r_3$ can tend to $\infty$. So, the problem becomes easier in those cases.

$(a^{l_1}+a^{l_1+1}+a^{l_1+2}+\cdots)(a^{l_2}+a^{l_2+1}+a^{l_2+2}+\cdots)(a^{l_3}+a^{l_3+1}+a^{l_3+2}+\cdots)\\=a^{l_1+l_2+l_3}(1+a+a^2+\cdots)^3\\=a^{l_1+l_2+l_3}(\frac{1}{1-a})^3\\=a^{l_1+l_2+l_3}(1-a)^{-3}$

So in the expansion of $(1-a)^{-3}$, we just need to find the coefficient of $a^{s-(l_1+l_2+l_3)}$. which is nothing but $_{}^{s-(l_1+l_2+l_3)+2}\textrm{C}_{2}$.
+1
okay thanks
0

@techbd123 what is 'a' here?? i couldn't get it..

+2
a is a simple polynomial variable. take a small example you would understand it.
0

i have one more question. is there any good way to calculate coefficient of $a^{s}$ in the generating function in this comment..(https://gateoverflow.in/325255/the-interesting-combination-sum-problems?show=325256#c325256) .

+2

Try to see questions on generating function on GO they would help.

0

@chirudeepnamini

It's just a variable in the polynomial expression. Combinatorial problems can be argued using the multiplication of polynomial expressions. BTW you can watch this video to grasp the basic idea.

+1 vote