The Gateway to Computer Science Excellence
+2 votes
167 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\ $

in Combinatory by Boss (21.6k points) | 167 views
+1
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
+3
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

@Satbir thanks for the reply..

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

https://gateoverflow.in/blog/6412/generating-function-recurrence-relation-useful-link

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.
 

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,492 answers
195,439 comments
100,700 users