Question and Answers Forum

All Questions      Topic List

Algebra Questions

Previous in All Question      Next in All Question      

Previous in Algebra      Next in Algebra      

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

Terms of Service

Privacy Policy

Contact: info@tinkutara.com