Menu Close

Find-the-number-of-solutions-for-positive-integers-x-y-z-satisfying-x-2y-3z-n-




Question Number 84182 by mr W last updated on 11/Mar/20
Find the number of solutions for  positive integers (x,y,z) satisfying  x+2y+3z=n.
$${Find}\:{the}\:{number}\:{of}\:{solutions}\:{for} \\ $$$${positive}\:{integers}\:\left({x},{y},{z}\right)\:{satisfying} \\ $$$$\boldsymbol{{x}}+\mathrm{2}\boldsymbol{{y}}+\mathrm{3}\boldsymbol{{z}}=\boldsymbol{{n}}. \\ $$
Answered by mr W last updated on 10/Mar/20
Method 1  let′s find at first the number of  solutions for x+2y=m with m≥3.  ⇒1≤y≤⌊((m−1)/2)⌋  i.e. there are ⌊((m−1)/2)⌋ solutions for  x+2y=m.    1≤z≤⌊((n−3)/3)⌋  m=n−3z  total number of solutions:  ⇒N(n)=Σ_(z=1) ^(⌊((n−3)/3)⌋) ⌊((m−1)/2)⌋=Σ_(z=1) ^(⌊((n−3)/3)⌋) ⌊((n−3z−1)/2)⌋    examples:  n=6: N=1  n=10: N=4  n=55: N=225  n=78: N=469  n=1000: N=82834
$${Method}\:\mathrm{1} \\ $$$${let}'{s}\:{find}\:{at}\:{first}\:{the}\:{number}\:{of} \\ $$$${solutions}\:{for}\:\boldsymbol{{x}}+\mathrm{2}\boldsymbol{{y}}=\boldsymbol{{m}}\:{with}\:{m}\geqslant\mathrm{3}. \\ $$$$\Rightarrow\mathrm{1}\leqslant{y}\leqslant\lfloor\frac{{m}−\mathrm{1}}{\mathrm{2}}\rfloor \\ $$$${i}.{e}.\:{there}\:{are}\:\lfloor\frac{{m}−\mathrm{1}}{\mathrm{2}}\rfloor\:{solutions}\:{for} \\ $$$${x}+\mathrm{2}{y}={m}. \\ $$$$ \\ $$$$\mathrm{1}\leqslant{z}\leqslant\lfloor\frac{{n}−\mathrm{3}}{\mathrm{3}}\rfloor \\ $$$${m}={n}−\mathrm{3}{z} \\ $$$${total}\:{number}\:{of}\:{solutions}: \\ $$$$\Rightarrow{N}\left({n}\right)=\underset{{z}=\mathrm{1}} {\overset{\lfloor\frac{{n}−\mathrm{3}}{\mathrm{3}}\rfloor} {\sum}}\lfloor\frac{{m}−\mathrm{1}}{\mathrm{2}}\rfloor=\underset{{z}=\mathrm{1}} {\overset{\lfloor\frac{{n}−\mathrm{3}}{\mathrm{3}}\rfloor} {\sum}}\lfloor\frac{{n}−\mathrm{3}{z}−\mathrm{1}}{\mathrm{2}}\rfloor \\ $$$$ \\ $$$${examples}: \\ $$$${n}=\mathrm{6}:\:{N}=\mathrm{1} \\ $$$${n}=\mathrm{10}:\:{N}=\mathrm{4} \\ $$$${n}=\mathrm{55}:\:{N}=\mathrm{225} \\ $$$${n}=\mathrm{78}:\:{N}=\mathrm{469} \\ $$$${n}=\mathrm{1000}:\:{N}=\mathrm{82834} \\ $$
Answered by mr W last updated on 10/Mar/20
Method 2  generating function for x+2y+3z is  (x/(1−x))×(x^2 /(1−x^2 ))×(x^3 /(1−x^3 ))=(x^6 /((1−x)(1−x^2 )(1−x^3 )))  number of solutions of x+2y+3z=n  is the coefficient of x^n  term of the  generating function above.   the taylor series of (x^6 /((1−x)(1−x^2 )(1−x^3 ))):
$${Method}\:\mathrm{2} \\ $$$${generating}\:{function}\:{for}\:\boldsymbol{{x}}+\mathrm{2}\boldsymbol{{y}}+\mathrm{3}\boldsymbol{{z}}\:{is} \\ $$$$\frac{{x}}{\mathrm{1}−{x}}×\frac{{x}^{\mathrm{2}} }{\mathrm{1}−{x}^{\mathrm{2}} }×\frac{{x}^{\mathrm{3}} }{\mathrm{1}−{x}^{\mathrm{3}} }=\frac{{x}^{\mathrm{6}} }{\left(\mathrm{1}−{x}\right)\left(\mathrm{1}−{x}^{\mathrm{2}} \right)\left(\mathrm{1}−{x}^{\mathrm{3}} \right)} \\ $$$${number}\:{of}\:{solutions}\:{of}\:\boldsymbol{{x}}+\mathrm{2}\boldsymbol{{y}}+\mathrm{3}\boldsymbol{{z}}=\boldsymbol{{n}} \\ $$$${is}\:{the}\:{coefficient}\:{of}\:{x}^{{n}} \:{term}\:{of}\:{the} \\ $$$${generating}\:{function}\:{above}.\: \\ $$$${the}\:{taylor}\:{series}\:{of}\:\frac{{x}^{\mathrm{6}} }{\left(\mathrm{1}−{x}\right)\left(\mathrm{1}−{x}^{\mathrm{2}} \right)\left(\mathrm{1}−{x}^{\mathrm{3}} \right)}: \\ $$
Commented by mr W last updated on 10/Mar/20
Commented by mr W last updated on 10/Mar/20
the coefficient of x^6  term is 1, it   means x+2y+3z=6 has one solution.  the coefficient of x^(78)  term is 469, it   means x+2y+3z=78 has 469 solutions.  all results coincide with the results  from method 1.
$${the}\:{coefficient}\:{of}\:{x}^{\mathrm{6}} \:{term}\:{is}\:\mathrm{1},\:{it}\: \\ $$$${means}\:{x}+\mathrm{2}{y}+\mathrm{3}{z}=\mathrm{6}\:{has}\:{one}\:{solution}. \\ $$$${the}\:{coefficient}\:{of}\:{x}^{\mathrm{78}} \:{term}\:{is}\:\mathrm{469},\:{it}\: \\ $$$${means}\:{x}+\mathrm{2}{y}+\mathrm{3}{z}=\mathrm{78}\:{has}\:\mathrm{469}\:{solutions}. \\ $$$${all}\:{results}\:{coincide}\:{with}\:{the}\:{results} \\ $$$${from}\:{method}\:\mathrm{1}. \\ $$

Leave a Reply

Your email address will not be published. Required fields are marked *