How many non-negative solutions for $x_{1} + x_{2} + x_{3} + x_{4} = 40$ where $2 leq x_{1} leq 8, x_{2} leq...
$begingroup$
My solution:
We have:
$x_{1} + x_{2} + x_{3} + x_{4} = 40$ where $2 leq x_{1} leq 8, x_{2} leq 4, x_{3} geq 4, x_{4} leq 5$
$Leftrightarrow x_{2} + x_{3} + x_{4} = 40 - x_{1} quad (*)$
Consider:
$x_{2} + x_{3} + x_{4} = 40 - x_{1}$ where $x_{2} geq 0, x_{3} geq 4, x_{4} geq 0 quad (**)$
$x_{2} + x_{3} + x_{4} = 40 - x_{1}$ where $x_{2} geq 5, x_{3} geq 4, x_{4} geq 6 quad (***)$
Let $f$ is the function that compute the number of non-negative solutions of an equation.
$implies f(*) = f(**) - f(***)$
Thus, the number of non-negative solutions of (*) is $sum_{x_{1} = 2}^{8}( {40 - x_{1} + 3 - 1 choose 3 - 1} - {25-x_{1}+3 - 1 choose 3 - 1}) = 3045$
I found that the right answer is 210 by trying some programming script. But I don't know what was wrong with my solution. Please help me. Thank you!
combinatorics
$endgroup$
add a comment |
$begingroup$
My solution:
We have:
$x_{1} + x_{2} + x_{3} + x_{4} = 40$ where $2 leq x_{1} leq 8, x_{2} leq 4, x_{3} geq 4, x_{4} leq 5$
$Leftrightarrow x_{2} + x_{3} + x_{4} = 40 - x_{1} quad (*)$
Consider:
$x_{2} + x_{3} + x_{4} = 40 - x_{1}$ where $x_{2} geq 0, x_{3} geq 4, x_{4} geq 0 quad (**)$
$x_{2} + x_{3} + x_{4} = 40 - x_{1}$ where $x_{2} geq 5, x_{3} geq 4, x_{4} geq 6 quad (***)$
Let $f$ is the function that compute the number of non-negative solutions of an equation.
$implies f(*) = f(**) - f(***)$
Thus, the number of non-negative solutions of (*) is $sum_{x_{1} = 2}^{8}( {40 - x_{1} + 3 - 1 choose 3 - 1} - {25-x_{1}+3 - 1 choose 3 - 1}) = 3045$
I found that the right answer is 210 by trying some programming script. But I don't know what was wrong with my solution. Please help me. Thank you!
combinatorics
$endgroup$
1
$begingroup$
The three upper limits on $x_1, x_2, x_4$ and that the only variable not upper restrained is dependent on the three restrained makes the stars and bars/choose solution too restrained to be relevent. Do this as pure choose/multiplying. There are so many chooses an the three restrained variables, and the unrestrained can be set up to be completely dependent on the other three. So it is straight mulitplication
$endgroup$
– fleablood
Dec 9 '18 at 16:39
1
$begingroup$
YOu are way over counting. You have the solution for $x_2< 5$ OR $x_4< 5$. You don't want that you want AND. ANd you also never take $x_3 ge 4$ into account. The first term should be $36$ not $40$.
$endgroup$
– fleablood
Dec 9 '18 at 16:47
$begingroup$
@fleablood thank for your comment, this is my wrong.
$endgroup$
– Duy Huynh
Dec 9 '18 at 16:51
add a comment |
$begingroup$
My solution:
We have:
$x_{1} + x_{2} + x_{3} + x_{4} = 40$ where $2 leq x_{1} leq 8, x_{2} leq 4, x_{3} geq 4, x_{4} leq 5$
$Leftrightarrow x_{2} + x_{3} + x_{4} = 40 - x_{1} quad (*)$
Consider:
$x_{2} + x_{3} + x_{4} = 40 - x_{1}$ where $x_{2} geq 0, x_{3} geq 4, x_{4} geq 0 quad (**)$
$x_{2} + x_{3} + x_{4} = 40 - x_{1}$ where $x_{2} geq 5, x_{3} geq 4, x_{4} geq 6 quad (***)$
Let $f$ is the function that compute the number of non-negative solutions of an equation.
$implies f(*) = f(**) - f(***)$
Thus, the number of non-negative solutions of (*) is $sum_{x_{1} = 2}^{8}( {40 - x_{1} + 3 - 1 choose 3 - 1} - {25-x_{1}+3 - 1 choose 3 - 1}) = 3045$
I found that the right answer is 210 by trying some programming script. But I don't know what was wrong with my solution. Please help me. Thank you!
combinatorics
$endgroup$
My solution:
We have:
$x_{1} + x_{2} + x_{3} + x_{4} = 40$ where $2 leq x_{1} leq 8, x_{2} leq 4, x_{3} geq 4, x_{4} leq 5$
$Leftrightarrow x_{2} + x_{3} + x_{4} = 40 - x_{1} quad (*)$
Consider:
$x_{2} + x_{3} + x_{4} = 40 - x_{1}$ where $x_{2} geq 0, x_{3} geq 4, x_{4} geq 0 quad (**)$
$x_{2} + x_{3} + x_{4} = 40 - x_{1}$ where $x_{2} geq 5, x_{3} geq 4, x_{4} geq 6 quad (***)$
Let $f$ is the function that compute the number of non-negative solutions of an equation.
$implies f(*) = f(**) - f(***)$
Thus, the number of non-negative solutions of (*) is $sum_{x_{1} = 2}^{8}( {40 - x_{1} + 3 - 1 choose 3 - 1} - {25-x_{1}+3 - 1 choose 3 - 1}) = 3045$
I found that the right answer is 210 by trying some programming script. But I don't know what was wrong with my solution. Please help me. Thank you!
combinatorics
combinatorics
asked Dec 9 '18 at 16:06
Duy HuynhDuy Huynh
254
254
1
$begingroup$
The three upper limits on $x_1, x_2, x_4$ and that the only variable not upper restrained is dependent on the three restrained makes the stars and bars/choose solution too restrained to be relevent. Do this as pure choose/multiplying. There are so many chooses an the three restrained variables, and the unrestrained can be set up to be completely dependent on the other three. So it is straight mulitplication
$endgroup$
– fleablood
Dec 9 '18 at 16:39
1
$begingroup$
YOu are way over counting. You have the solution for $x_2< 5$ OR $x_4< 5$. You don't want that you want AND. ANd you also never take $x_3 ge 4$ into account. The first term should be $36$ not $40$.
$endgroup$
– fleablood
Dec 9 '18 at 16:47
$begingroup$
@fleablood thank for your comment, this is my wrong.
$endgroup$
– Duy Huynh
Dec 9 '18 at 16:51
add a comment |
1
$begingroup$
The three upper limits on $x_1, x_2, x_4$ and that the only variable not upper restrained is dependent on the three restrained makes the stars and bars/choose solution too restrained to be relevent. Do this as pure choose/multiplying. There are so many chooses an the three restrained variables, and the unrestrained can be set up to be completely dependent on the other three. So it is straight mulitplication
$endgroup$
– fleablood
Dec 9 '18 at 16:39
1
$begingroup$
YOu are way over counting. You have the solution for $x_2< 5$ OR $x_4< 5$. You don't want that you want AND. ANd you also never take $x_3 ge 4$ into account. The first term should be $36$ not $40$.
$endgroup$
– fleablood
Dec 9 '18 at 16:47
$begingroup$
@fleablood thank for your comment, this is my wrong.
$endgroup$
– Duy Huynh
Dec 9 '18 at 16:51
1
1
$begingroup$
The three upper limits on $x_1, x_2, x_4$ and that the only variable not upper restrained is dependent on the three restrained makes the stars and bars/choose solution too restrained to be relevent. Do this as pure choose/multiplying. There are so many chooses an the three restrained variables, and the unrestrained can be set up to be completely dependent on the other three. So it is straight mulitplication
$endgroup$
– fleablood
Dec 9 '18 at 16:39
$begingroup$
The three upper limits on $x_1, x_2, x_4$ and that the only variable not upper restrained is dependent on the three restrained makes the stars and bars/choose solution too restrained to be relevent. Do this as pure choose/multiplying. There are so many chooses an the three restrained variables, and the unrestrained can be set up to be completely dependent on the other three. So it is straight mulitplication
$endgroup$
– fleablood
Dec 9 '18 at 16:39
1
1
$begingroup$
YOu are way over counting. You have the solution for $x_2< 5$ OR $x_4< 5$. You don't want that you want AND. ANd you also never take $x_3 ge 4$ into account. The first term should be $36$ not $40$.
$endgroup$
– fleablood
Dec 9 '18 at 16:47
$begingroup$
YOu are way over counting. You have the solution for $x_2< 5$ OR $x_4< 5$. You don't want that you want AND. ANd you also never take $x_3 ge 4$ into account. The first term should be $36$ not $40$.
$endgroup$
– fleablood
Dec 9 '18 at 16:47
$begingroup$
@fleablood thank for your comment, this is my wrong.
$endgroup$
– Duy Huynh
Dec 9 '18 at 16:51
$begingroup$
@fleablood thank for your comment, this is my wrong.
$endgroup$
– Duy Huynh
Dec 9 '18 at 16:51
add a comment |
4 Answers
4
active
oldest
votes
$begingroup$
$x_1 + x_2 + x_4 le 8 + 4 + 5 = 17$ so $x_3=40 - x_1 + s_2 + x_4 ge 40 -17 ge 4$ so we can ignore the restriction on $x_3$.
$2 le x_1 le 6$ so there are $7$ values that $x_1$ can be, $xle 4$ so there are $5$ values it can be. $x_4 le 5$ so there are $6$ values it can be and $x_3$ must be $40 - x_1 - x_2 -x_4$ there is only one option dependant on the other three options.
So there $7*5*6 = 210$ options.
Your solution dosn't take $x_3 ge 4$ into account (which you can be seting it up so that the some is $36$ and not $40$-- I haven't done the math to figure it out but that will lower you answer significantly. Also by subtracting you are removing the cases with both $x_2 ge 5$ and $x_4 ge 6$ but not removing the cases where one or the other is.)
I think to fix your problem using inclusion exclusion you'd want
$sum_{x_1=2}^8({{40 - 4 -x_1 + 3-1}choose {3-1}} - {{40 - 4-5 -x_1 + 3-1}choose {3-1}}-{{40 - 4-6 -x_1 + 3-1}choose {3-1}}+{{40 - 4 -5-6-x_1 + 3-1}choose {3-1}})=$
And I'm too lazy to finish.
$endgroup$
add a comment |
$begingroup$
$newcommand{bbx}[1]{,bbox[15px,border:1px groove navy]{displaystyle{#1}},}
newcommand{braces}[1]{leftlbrace,{#1},rightrbrace}
newcommand{bracks}[1]{leftlbrack,{#1},rightrbrack}
newcommand{dd}{mathrm{d}}
newcommand{ds}[1]{displaystyle{#1}}
newcommand{expo}[1]{,mathrm{e}^{#1},}
newcommand{ic}{mathrm{i}}
newcommand{mc}[1]{mathcal{#1}}
newcommand{mrm}[1]{mathrm{#1}}
newcommand{pars}[1]{left(,{#1},right)}
newcommand{partiald}[3]{frac{partial^{#1} #2}{partial #3^{#1}}}
newcommand{root}[2]{,sqrt[#1]{,{#2},},}
newcommand{totald}[3]{frac{mathrm{d}^{#1} #2}{mathrm{d} #3^{#1}}}
newcommand{verts}[1]{leftvert,{#1},rightvert}$
A General Method:
begin{align}
&bbox[10px,#ffd]{sum_{x_{1} = 2}^{8}
sum_{x_{2} = 0}^{4}sum_{x_{3} = 4}^{infty}sum_{x_{4} = 0}^{5}
bracks{z^{40}}z^{x_{1} + x_{2} + x_{3} + x_{4}}} =
sum_{x_{1} = 0}^{6}
sum_{x_{2} = 0}^{4}sum_{x_{3} = 0}^{infty}sum_{x_{4} = 0}^{5}
bracks{z^{30}}z^{x_{1} + x_{2} + x_{3} + x_{4}}
\[5mm] = &
bracks{z^{30}}pars{sum_{x_{1} = 0}^{6}z^{x_{1}}}
pars{sum_{x_{2} = 0}^{4}z^{x_{2}}}
pars{sum_{x_{3} = 0}^{infty}z^{x_{3}}}
pars{sum_{x_{1} = 0}^{5}z^{x_{4}}}
\[5mm] = &
bracks{z^{40}}{1 - z^{7} over 1 - z},{1 - z^{5} over 1 - z},{1 over 1 - z},{1 - z^{6} over 1 - z}
\[5mm] = &
bracks{z^{40}}pars{-z^{18} + z^{13} + z^{12} + z^{11} - z^{7} - z^{6} - z^{5} + 1}pars{1 - z}^{-4}
\[5mm] = &
-{-4 choose 22} - {-4 choose 27} + {-4 choose 28} -
{-4 choose 29} + {-4 choose 33} - {-4 choose 34} +
{-4 choose 35} + {-4 choose 40}
\[5mm] = &
- underbrace{25 choose 22}_{ds{2300}} +
underbrace{30 choose 27}_{ds{4060}} +
underbrace{31 choose 28}_{ds{4495}} +
underbrace{32 choose 29}_{ds{4960}} -
underbrace{36 choose 33}_{ds{7140}} -
underbrace{37 choose 34}_{ds{7770}} -
\[2mm] & -
underbrace{38 choose 35}_{ds{8436}} +
underbrace{43 choose 40}_{ds{12341}} = bbx{large 210}
end{align}
$endgroup$
add a comment |
$begingroup$
It's the coefficient of $x^{40}$ of the product polynomial
$$(x^2+x^3+x^4 +x^5 + x^6 + x^7 + x^8)(1+x^1+x^2+x^3 +x^4)(x^4 + x^5 + ldots)(1+x^1+x^2+x^3 +x^4 + x^5)$$
Or equivalently the coefficient of $x^{34}$ of
$$(1+x+x^2+x^3+x^4 +x^5 + x^6 )(1+x^1+x^2+x^3 +x^4)(1 + x + x^2 + ldots)(1+x^1+x^2+x^3 +x^4 + x^5)$$
which can be found using (generalised) binomials etc.
$endgroup$
$begingroup$
Isn't this just rephrasing the problem?
$endgroup$
– Christoph
Dec 9 '18 at 16:56
$begingroup$
@Christoph just giving an alternative path.
$endgroup$
– Henno Brandsma
Dec 9 '18 at 16:58
add a comment |
$begingroup$
Math answer
Note that the given constraints for $x_1, x_2$ and $x_4$ and $sumlimits_{i = 1}^4 x_i = 40$ allows us to define
$$
begin{aligned}
x_3 &= 40 - x_1 - x_2 - x_4 \
&ge 40 - 8 - 4 - 5 \
&= 23.
end{aligned}$$
This renders the constraint $x_3 ge 4$ redundant. As a result, the required answer is $(8-2+1) times (4+1) times (5+1) = 210$.
Julia Programming Script
x1 = 2:8
x2 = 0:4
x4 = 0:5
x3 = [40 - i - j - k for i in x1 for j in x2 for k in x4]
println(minimum(x3)) # returns 23
println(length(x3)) # returns 210
Test this script on Tutorial's Point's online compiler.
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3032553%2fhow-many-non-negative-solutions-for-x-1-x-2-x-3-x-4-40-where%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
$x_1 + x_2 + x_4 le 8 + 4 + 5 = 17$ so $x_3=40 - x_1 + s_2 + x_4 ge 40 -17 ge 4$ so we can ignore the restriction on $x_3$.
$2 le x_1 le 6$ so there are $7$ values that $x_1$ can be, $xle 4$ so there are $5$ values it can be. $x_4 le 5$ so there are $6$ values it can be and $x_3$ must be $40 - x_1 - x_2 -x_4$ there is only one option dependant on the other three options.
So there $7*5*6 = 210$ options.
Your solution dosn't take $x_3 ge 4$ into account (which you can be seting it up so that the some is $36$ and not $40$-- I haven't done the math to figure it out but that will lower you answer significantly. Also by subtracting you are removing the cases with both $x_2 ge 5$ and $x_4 ge 6$ but not removing the cases where one or the other is.)
I think to fix your problem using inclusion exclusion you'd want
$sum_{x_1=2}^8({{40 - 4 -x_1 + 3-1}choose {3-1}} - {{40 - 4-5 -x_1 + 3-1}choose {3-1}}-{{40 - 4-6 -x_1 + 3-1}choose {3-1}}+{{40 - 4 -5-6-x_1 + 3-1}choose {3-1}})=$
And I'm too lazy to finish.
$endgroup$
add a comment |
$begingroup$
$x_1 + x_2 + x_4 le 8 + 4 + 5 = 17$ so $x_3=40 - x_1 + s_2 + x_4 ge 40 -17 ge 4$ so we can ignore the restriction on $x_3$.
$2 le x_1 le 6$ so there are $7$ values that $x_1$ can be, $xle 4$ so there are $5$ values it can be. $x_4 le 5$ so there are $6$ values it can be and $x_3$ must be $40 - x_1 - x_2 -x_4$ there is only one option dependant on the other three options.
So there $7*5*6 = 210$ options.
Your solution dosn't take $x_3 ge 4$ into account (which you can be seting it up so that the some is $36$ and not $40$-- I haven't done the math to figure it out but that will lower you answer significantly. Also by subtracting you are removing the cases with both $x_2 ge 5$ and $x_4 ge 6$ but not removing the cases where one or the other is.)
I think to fix your problem using inclusion exclusion you'd want
$sum_{x_1=2}^8({{40 - 4 -x_1 + 3-1}choose {3-1}} - {{40 - 4-5 -x_1 + 3-1}choose {3-1}}-{{40 - 4-6 -x_1 + 3-1}choose {3-1}}+{{40 - 4 -5-6-x_1 + 3-1}choose {3-1}})=$
And I'm too lazy to finish.
$endgroup$
add a comment |
$begingroup$
$x_1 + x_2 + x_4 le 8 + 4 + 5 = 17$ so $x_3=40 - x_1 + s_2 + x_4 ge 40 -17 ge 4$ so we can ignore the restriction on $x_3$.
$2 le x_1 le 6$ so there are $7$ values that $x_1$ can be, $xle 4$ so there are $5$ values it can be. $x_4 le 5$ so there are $6$ values it can be and $x_3$ must be $40 - x_1 - x_2 -x_4$ there is only one option dependant on the other three options.
So there $7*5*6 = 210$ options.
Your solution dosn't take $x_3 ge 4$ into account (which you can be seting it up so that the some is $36$ and not $40$-- I haven't done the math to figure it out but that will lower you answer significantly. Also by subtracting you are removing the cases with both $x_2 ge 5$ and $x_4 ge 6$ but not removing the cases where one or the other is.)
I think to fix your problem using inclusion exclusion you'd want
$sum_{x_1=2}^8({{40 - 4 -x_1 + 3-1}choose {3-1}} - {{40 - 4-5 -x_1 + 3-1}choose {3-1}}-{{40 - 4-6 -x_1 + 3-1}choose {3-1}}+{{40 - 4 -5-6-x_1 + 3-1}choose {3-1}})=$
And I'm too lazy to finish.
$endgroup$
$x_1 + x_2 + x_4 le 8 + 4 + 5 = 17$ so $x_3=40 - x_1 + s_2 + x_4 ge 40 -17 ge 4$ so we can ignore the restriction on $x_3$.
$2 le x_1 le 6$ so there are $7$ values that $x_1$ can be, $xle 4$ so there are $5$ values it can be. $x_4 le 5$ so there are $6$ values it can be and $x_3$ must be $40 - x_1 - x_2 -x_4$ there is only one option dependant on the other three options.
So there $7*5*6 = 210$ options.
Your solution dosn't take $x_3 ge 4$ into account (which you can be seting it up so that the some is $36$ and not $40$-- I haven't done the math to figure it out but that will lower you answer significantly. Also by subtracting you are removing the cases with both $x_2 ge 5$ and $x_4 ge 6$ but not removing the cases where one or the other is.)
I think to fix your problem using inclusion exclusion you'd want
$sum_{x_1=2}^8({{40 - 4 -x_1 + 3-1}choose {3-1}} - {{40 - 4-5 -x_1 + 3-1}choose {3-1}}-{{40 - 4-6 -x_1 + 3-1}choose {3-1}}+{{40 - 4 -5-6-x_1 + 3-1}choose {3-1}})=$
And I'm too lazy to finish.
edited Dec 9 '18 at 17:08
answered Dec 9 '18 at 16:32
fleabloodfleablood
71k22686
71k22686
add a comment |
add a comment |
$begingroup$
$newcommand{bbx}[1]{,bbox[15px,border:1px groove navy]{displaystyle{#1}},}
newcommand{braces}[1]{leftlbrace,{#1},rightrbrace}
newcommand{bracks}[1]{leftlbrack,{#1},rightrbrack}
newcommand{dd}{mathrm{d}}
newcommand{ds}[1]{displaystyle{#1}}
newcommand{expo}[1]{,mathrm{e}^{#1},}
newcommand{ic}{mathrm{i}}
newcommand{mc}[1]{mathcal{#1}}
newcommand{mrm}[1]{mathrm{#1}}
newcommand{pars}[1]{left(,{#1},right)}
newcommand{partiald}[3]{frac{partial^{#1} #2}{partial #3^{#1}}}
newcommand{root}[2]{,sqrt[#1]{,{#2},},}
newcommand{totald}[3]{frac{mathrm{d}^{#1} #2}{mathrm{d} #3^{#1}}}
newcommand{verts}[1]{leftvert,{#1},rightvert}$
A General Method:
begin{align}
&bbox[10px,#ffd]{sum_{x_{1} = 2}^{8}
sum_{x_{2} = 0}^{4}sum_{x_{3} = 4}^{infty}sum_{x_{4} = 0}^{5}
bracks{z^{40}}z^{x_{1} + x_{2} + x_{3} + x_{4}}} =
sum_{x_{1} = 0}^{6}
sum_{x_{2} = 0}^{4}sum_{x_{3} = 0}^{infty}sum_{x_{4} = 0}^{5}
bracks{z^{30}}z^{x_{1} + x_{2} + x_{3} + x_{4}}
\[5mm] = &
bracks{z^{30}}pars{sum_{x_{1} = 0}^{6}z^{x_{1}}}
pars{sum_{x_{2} = 0}^{4}z^{x_{2}}}
pars{sum_{x_{3} = 0}^{infty}z^{x_{3}}}
pars{sum_{x_{1} = 0}^{5}z^{x_{4}}}
\[5mm] = &
bracks{z^{40}}{1 - z^{7} over 1 - z},{1 - z^{5} over 1 - z},{1 over 1 - z},{1 - z^{6} over 1 - z}
\[5mm] = &
bracks{z^{40}}pars{-z^{18} + z^{13} + z^{12} + z^{11} - z^{7} - z^{6} - z^{5} + 1}pars{1 - z}^{-4}
\[5mm] = &
-{-4 choose 22} - {-4 choose 27} + {-4 choose 28} -
{-4 choose 29} + {-4 choose 33} - {-4 choose 34} +
{-4 choose 35} + {-4 choose 40}
\[5mm] = &
- underbrace{25 choose 22}_{ds{2300}} +
underbrace{30 choose 27}_{ds{4060}} +
underbrace{31 choose 28}_{ds{4495}} +
underbrace{32 choose 29}_{ds{4960}} -
underbrace{36 choose 33}_{ds{7140}} -
underbrace{37 choose 34}_{ds{7770}} -
\[2mm] & -
underbrace{38 choose 35}_{ds{8436}} +
underbrace{43 choose 40}_{ds{12341}} = bbx{large 210}
end{align}
$endgroup$
add a comment |
$begingroup$
$newcommand{bbx}[1]{,bbox[15px,border:1px groove navy]{displaystyle{#1}},}
newcommand{braces}[1]{leftlbrace,{#1},rightrbrace}
newcommand{bracks}[1]{leftlbrack,{#1},rightrbrack}
newcommand{dd}{mathrm{d}}
newcommand{ds}[1]{displaystyle{#1}}
newcommand{expo}[1]{,mathrm{e}^{#1},}
newcommand{ic}{mathrm{i}}
newcommand{mc}[1]{mathcal{#1}}
newcommand{mrm}[1]{mathrm{#1}}
newcommand{pars}[1]{left(,{#1},right)}
newcommand{partiald}[3]{frac{partial^{#1} #2}{partial #3^{#1}}}
newcommand{root}[2]{,sqrt[#1]{,{#2},},}
newcommand{totald}[3]{frac{mathrm{d}^{#1} #2}{mathrm{d} #3^{#1}}}
newcommand{verts}[1]{leftvert,{#1},rightvert}$
A General Method:
begin{align}
&bbox[10px,#ffd]{sum_{x_{1} = 2}^{8}
sum_{x_{2} = 0}^{4}sum_{x_{3} = 4}^{infty}sum_{x_{4} = 0}^{5}
bracks{z^{40}}z^{x_{1} + x_{2} + x_{3} + x_{4}}} =
sum_{x_{1} = 0}^{6}
sum_{x_{2} = 0}^{4}sum_{x_{3} = 0}^{infty}sum_{x_{4} = 0}^{5}
bracks{z^{30}}z^{x_{1} + x_{2} + x_{3} + x_{4}}
\[5mm] = &
bracks{z^{30}}pars{sum_{x_{1} = 0}^{6}z^{x_{1}}}
pars{sum_{x_{2} = 0}^{4}z^{x_{2}}}
pars{sum_{x_{3} = 0}^{infty}z^{x_{3}}}
pars{sum_{x_{1} = 0}^{5}z^{x_{4}}}
\[5mm] = &
bracks{z^{40}}{1 - z^{7} over 1 - z},{1 - z^{5} over 1 - z},{1 over 1 - z},{1 - z^{6} over 1 - z}
\[5mm] = &
bracks{z^{40}}pars{-z^{18} + z^{13} + z^{12} + z^{11} - z^{7} - z^{6} - z^{5} + 1}pars{1 - z}^{-4}
\[5mm] = &
-{-4 choose 22} - {-4 choose 27} + {-4 choose 28} -
{-4 choose 29} + {-4 choose 33} - {-4 choose 34} +
{-4 choose 35} + {-4 choose 40}
\[5mm] = &
- underbrace{25 choose 22}_{ds{2300}} +
underbrace{30 choose 27}_{ds{4060}} +
underbrace{31 choose 28}_{ds{4495}} +
underbrace{32 choose 29}_{ds{4960}} -
underbrace{36 choose 33}_{ds{7140}} -
underbrace{37 choose 34}_{ds{7770}} -
\[2mm] & -
underbrace{38 choose 35}_{ds{8436}} +
underbrace{43 choose 40}_{ds{12341}} = bbx{large 210}
end{align}
$endgroup$
add a comment |
$begingroup$
$newcommand{bbx}[1]{,bbox[15px,border:1px groove navy]{displaystyle{#1}},}
newcommand{braces}[1]{leftlbrace,{#1},rightrbrace}
newcommand{bracks}[1]{leftlbrack,{#1},rightrbrack}
newcommand{dd}{mathrm{d}}
newcommand{ds}[1]{displaystyle{#1}}
newcommand{expo}[1]{,mathrm{e}^{#1},}
newcommand{ic}{mathrm{i}}
newcommand{mc}[1]{mathcal{#1}}
newcommand{mrm}[1]{mathrm{#1}}
newcommand{pars}[1]{left(,{#1},right)}
newcommand{partiald}[3]{frac{partial^{#1} #2}{partial #3^{#1}}}
newcommand{root}[2]{,sqrt[#1]{,{#2},},}
newcommand{totald}[3]{frac{mathrm{d}^{#1} #2}{mathrm{d} #3^{#1}}}
newcommand{verts}[1]{leftvert,{#1},rightvert}$
A General Method:
begin{align}
&bbox[10px,#ffd]{sum_{x_{1} = 2}^{8}
sum_{x_{2} = 0}^{4}sum_{x_{3} = 4}^{infty}sum_{x_{4} = 0}^{5}
bracks{z^{40}}z^{x_{1} + x_{2} + x_{3} + x_{4}}} =
sum_{x_{1} = 0}^{6}
sum_{x_{2} = 0}^{4}sum_{x_{3} = 0}^{infty}sum_{x_{4} = 0}^{5}
bracks{z^{30}}z^{x_{1} + x_{2} + x_{3} + x_{4}}
\[5mm] = &
bracks{z^{30}}pars{sum_{x_{1} = 0}^{6}z^{x_{1}}}
pars{sum_{x_{2} = 0}^{4}z^{x_{2}}}
pars{sum_{x_{3} = 0}^{infty}z^{x_{3}}}
pars{sum_{x_{1} = 0}^{5}z^{x_{4}}}
\[5mm] = &
bracks{z^{40}}{1 - z^{7} over 1 - z},{1 - z^{5} over 1 - z},{1 over 1 - z},{1 - z^{6} over 1 - z}
\[5mm] = &
bracks{z^{40}}pars{-z^{18} + z^{13} + z^{12} + z^{11} - z^{7} - z^{6} - z^{5} + 1}pars{1 - z}^{-4}
\[5mm] = &
-{-4 choose 22} - {-4 choose 27} + {-4 choose 28} -
{-4 choose 29} + {-4 choose 33} - {-4 choose 34} +
{-4 choose 35} + {-4 choose 40}
\[5mm] = &
- underbrace{25 choose 22}_{ds{2300}} +
underbrace{30 choose 27}_{ds{4060}} +
underbrace{31 choose 28}_{ds{4495}} +
underbrace{32 choose 29}_{ds{4960}} -
underbrace{36 choose 33}_{ds{7140}} -
underbrace{37 choose 34}_{ds{7770}} -
\[2mm] & -
underbrace{38 choose 35}_{ds{8436}} +
underbrace{43 choose 40}_{ds{12341}} = bbx{large 210}
end{align}
$endgroup$
$newcommand{bbx}[1]{,bbox[15px,border:1px groove navy]{displaystyle{#1}},}
newcommand{braces}[1]{leftlbrace,{#1},rightrbrace}
newcommand{bracks}[1]{leftlbrack,{#1},rightrbrack}
newcommand{dd}{mathrm{d}}
newcommand{ds}[1]{displaystyle{#1}}
newcommand{expo}[1]{,mathrm{e}^{#1},}
newcommand{ic}{mathrm{i}}
newcommand{mc}[1]{mathcal{#1}}
newcommand{mrm}[1]{mathrm{#1}}
newcommand{pars}[1]{left(,{#1},right)}
newcommand{partiald}[3]{frac{partial^{#1} #2}{partial #3^{#1}}}
newcommand{root}[2]{,sqrt[#1]{,{#2},},}
newcommand{totald}[3]{frac{mathrm{d}^{#1} #2}{mathrm{d} #3^{#1}}}
newcommand{verts}[1]{leftvert,{#1},rightvert}$
A General Method:
begin{align}
&bbox[10px,#ffd]{sum_{x_{1} = 2}^{8}
sum_{x_{2} = 0}^{4}sum_{x_{3} = 4}^{infty}sum_{x_{4} = 0}^{5}
bracks{z^{40}}z^{x_{1} + x_{2} + x_{3} + x_{4}}} =
sum_{x_{1} = 0}^{6}
sum_{x_{2} = 0}^{4}sum_{x_{3} = 0}^{infty}sum_{x_{4} = 0}^{5}
bracks{z^{30}}z^{x_{1} + x_{2} + x_{3} + x_{4}}
\[5mm] = &
bracks{z^{30}}pars{sum_{x_{1} = 0}^{6}z^{x_{1}}}
pars{sum_{x_{2} = 0}^{4}z^{x_{2}}}
pars{sum_{x_{3} = 0}^{infty}z^{x_{3}}}
pars{sum_{x_{1} = 0}^{5}z^{x_{4}}}
\[5mm] = &
bracks{z^{40}}{1 - z^{7} over 1 - z},{1 - z^{5} over 1 - z},{1 over 1 - z},{1 - z^{6} over 1 - z}
\[5mm] = &
bracks{z^{40}}pars{-z^{18} + z^{13} + z^{12} + z^{11} - z^{7} - z^{6} - z^{5} + 1}pars{1 - z}^{-4}
\[5mm] = &
-{-4 choose 22} - {-4 choose 27} + {-4 choose 28} -
{-4 choose 29} + {-4 choose 33} - {-4 choose 34} +
{-4 choose 35} + {-4 choose 40}
\[5mm] = &
- underbrace{25 choose 22}_{ds{2300}} +
underbrace{30 choose 27}_{ds{4060}} +
underbrace{31 choose 28}_{ds{4495}} +
underbrace{32 choose 29}_{ds{4960}} -
underbrace{36 choose 33}_{ds{7140}} -
underbrace{37 choose 34}_{ds{7770}} -
\[2mm] & -
underbrace{38 choose 35}_{ds{8436}} +
underbrace{43 choose 40}_{ds{12341}} = bbx{large 210}
end{align}
answered Dec 9 '18 at 17:54
Felix MarinFelix Marin
68k7108142
68k7108142
add a comment |
add a comment |
$begingroup$
It's the coefficient of $x^{40}$ of the product polynomial
$$(x^2+x^3+x^4 +x^5 + x^6 + x^7 + x^8)(1+x^1+x^2+x^3 +x^4)(x^4 + x^5 + ldots)(1+x^1+x^2+x^3 +x^4 + x^5)$$
Or equivalently the coefficient of $x^{34}$ of
$$(1+x+x^2+x^3+x^4 +x^5 + x^6 )(1+x^1+x^2+x^3 +x^4)(1 + x + x^2 + ldots)(1+x^1+x^2+x^3 +x^4 + x^5)$$
which can be found using (generalised) binomials etc.
$endgroup$
$begingroup$
Isn't this just rephrasing the problem?
$endgroup$
– Christoph
Dec 9 '18 at 16:56
$begingroup$
@Christoph just giving an alternative path.
$endgroup$
– Henno Brandsma
Dec 9 '18 at 16:58
add a comment |
$begingroup$
It's the coefficient of $x^{40}$ of the product polynomial
$$(x^2+x^3+x^4 +x^5 + x^6 + x^7 + x^8)(1+x^1+x^2+x^3 +x^4)(x^4 + x^5 + ldots)(1+x^1+x^2+x^3 +x^4 + x^5)$$
Or equivalently the coefficient of $x^{34}$ of
$$(1+x+x^2+x^3+x^4 +x^5 + x^6 )(1+x^1+x^2+x^3 +x^4)(1 + x + x^2 + ldots)(1+x^1+x^2+x^3 +x^4 + x^5)$$
which can be found using (generalised) binomials etc.
$endgroup$
$begingroup$
Isn't this just rephrasing the problem?
$endgroup$
– Christoph
Dec 9 '18 at 16:56
$begingroup$
@Christoph just giving an alternative path.
$endgroup$
– Henno Brandsma
Dec 9 '18 at 16:58
add a comment |
$begingroup$
It's the coefficient of $x^{40}$ of the product polynomial
$$(x^2+x^3+x^4 +x^5 + x^6 + x^7 + x^8)(1+x^1+x^2+x^3 +x^4)(x^4 + x^5 + ldots)(1+x^1+x^2+x^3 +x^4 + x^5)$$
Or equivalently the coefficient of $x^{34}$ of
$$(1+x+x^2+x^3+x^4 +x^5 + x^6 )(1+x^1+x^2+x^3 +x^4)(1 + x + x^2 + ldots)(1+x^1+x^2+x^3 +x^4 + x^5)$$
which can be found using (generalised) binomials etc.
$endgroup$
It's the coefficient of $x^{40}$ of the product polynomial
$$(x^2+x^3+x^4 +x^5 + x^6 + x^7 + x^8)(1+x^1+x^2+x^3 +x^4)(x^4 + x^5 + ldots)(1+x^1+x^2+x^3 +x^4 + x^5)$$
Or equivalently the coefficient of $x^{34}$ of
$$(1+x+x^2+x^3+x^4 +x^5 + x^6 )(1+x^1+x^2+x^3 +x^4)(1 + x + x^2 + ldots)(1+x^1+x^2+x^3 +x^4 + x^5)$$
which can be found using (generalised) binomials etc.
answered Dec 9 '18 at 16:12
Henno BrandsmaHenno Brandsma
110k347116
110k347116
$begingroup$
Isn't this just rephrasing the problem?
$endgroup$
– Christoph
Dec 9 '18 at 16:56
$begingroup$
@Christoph just giving an alternative path.
$endgroup$
– Henno Brandsma
Dec 9 '18 at 16:58
add a comment |
$begingroup$
Isn't this just rephrasing the problem?
$endgroup$
– Christoph
Dec 9 '18 at 16:56
$begingroup$
@Christoph just giving an alternative path.
$endgroup$
– Henno Brandsma
Dec 9 '18 at 16:58
$begingroup$
Isn't this just rephrasing the problem?
$endgroup$
– Christoph
Dec 9 '18 at 16:56
$begingroup$
Isn't this just rephrasing the problem?
$endgroup$
– Christoph
Dec 9 '18 at 16:56
$begingroup$
@Christoph just giving an alternative path.
$endgroup$
– Henno Brandsma
Dec 9 '18 at 16:58
$begingroup$
@Christoph just giving an alternative path.
$endgroup$
– Henno Brandsma
Dec 9 '18 at 16:58
add a comment |
$begingroup$
Math answer
Note that the given constraints for $x_1, x_2$ and $x_4$ and $sumlimits_{i = 1}^4 x_i = 40$ allows us to define
$$
begin{aligned}
x_3 &= 40 - x_1 - x_2 - x_4 \
&ge 40 - 8 - 4 - 5 \
&= 23.
end{aligned}$$
This renders the constraint $x_3 ge 4$ redundant. As a result, the required answer is $(8-2+1) times (4+1) times (5+1) = 210$.
Julia Programming Script
x1 = 2:8
x2 = 0:4
x4 = 0:5
x3 = [40 - i - j - k for i in x1 for j in x2 for k in x4]
println(minimum(x3)) # returns 23
println(length(x3)) # returns 210
Test this script on Tutorial's Point's online compiler.
$endgroup$
add a comment |
$begingroup$
Math answer
Note that the given constraints for $x_1, x_2$ and $x_4$ and $sumlimits_{i = 1}^4 x_i = 40$ allows us to define
$$
begin{aligned}
x_3 &= 40 - x_1 - x_2 - x_4 \
&ge 40 - 8 - 4 - 5 \
&= 23.
end{aligned}$$
This renders the constraint $x_3 ge 4$ redundant. As a result, the required answer is $(8-2+1) times (4+1) times (5+1) = 210$.
Julia Programming Script
x1 = 2:8
x2 = 0:4
x4 = 0:5
x3 = [40 - i - j - k for i in x1 for j in x2 for k in x4]
println(minimum(x3)) # returns 23
println(length(x3)) # returns 210
Test this script on Tutorial's Point's online compiler.
$endgroup$
add a comment |
$begingroup$
Math answer
Note that the given constraints for $x_1, x_2$ and $x_4$ and $sumlimits_{i = 1}^4 x_i = 40$ allows us to define
$$
begin{aligned}
x_3 &= 40 - x_1 - x_2 - x_4 \
&ge 40 - 8 - 4 - 5 \
&= 23.
end{aligned}$$
This renders the constraint $x_3 ge 4$ redundant. As a result, the required answer is $(8-2+1) times (4+1) times (5+1) = 210$.
Julia Programming Script
x1 = 2:8
x2 = 0:4
x4 = 0:5
x3 = [40 - i - j - k for i in x1 for j in x2 for k in x4]
println(minimum(x3)) # returns 23
println(length(x3)) # returns 210
Test this script on Tutorial's Point's online compiler.
$endgroup$
Math answer
Note that the given constraints for $x_1, x_2$ and $x_4$ and $sumlimits_{i = 1}^4 x_i = 40$ allows us to define
$$
begin{aligned}
x_3 &= 40 - x_1 - x_2 - x_4 \
&ge 40 - 8 - 4 - 5 \
&= 23.
end{aligned}$$
This renders the constraint $x_3 ge 4$ redundant. As a result, the required answer is $(8-2+1) times (4+1) times (5+1) = 210$.
Julia Programming Script
x1 = 2:8
x2 = 0:4
x4 = 0:5
x3 = [40 - i - j - k for i in x1 for j in x2 for k in x4]
println(minimum(x3)) # returns 23
println(length(x3)) # returns 210
Test this script on Tutorial's Point's online compiler.
edited Dec 9 '18 at 16:40
answered Dec 9 '18 at 16:32
GNUSupporter 8964民主女神 地下教會GNUSupporter 8964民主女神 地下教會
13.3k72549
13.3k72549
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3032553%2fhow-many-non-negative-solutions-for-x-1-x-2-x-3-x-4-40-where%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
The three upper limits on $x_1, x_2, x_4$ and that the only variable not upper restrained is dependent on the three restrained makes the stars and bars/choose solution too restrained to be relevent. Do this as pure choose/multiplying. There are so many chooses an the three restrained variables, and the unrestrained can be set up to be completely dependent on the other three. So it is straight mulitplication
$endgroup$
– fleablood
Dec 9 '18 at 16:39
1
$begingroup$
YOu are way over counting. You have the solution for $x_2< 5$ OR $x_4< 5$. You don't want that you want AND. ANd you also never take $x_3 ge 4$ into account. The first term should be $36$ not $40$.
$endgroup$
– fleablood
Dec 9 '18 at 16:47
$begingroup$
@fleablood thank for your comment, this is my wrong.
$endgroup$
– Duy Huynh
Dec 9 '18 at 16:51