Stars and Bars question with restriction that two variables must be equal
$begingroup$
How would one proceed in their thought process when trying to solve what appears to be a standard stars and bars equation, with $x_igeqslant$ 0, e.g.
$$x_1+x_2+x_3+x_4=24$$
Except, let's say that there is a restriction that two of the variables must be equal. We can write the equation as such:
$$x_1+x_2+2x_3=24$$
At first, I tried substituting $2x_3$ with $y$, and solving for
$$x_1+x_2+y=24$$
using the standard stars and bars method. However, that would result in over counting, because it does not account for restrictions on $y$, since $y$ has to be even.
Any suggestions on how to solve this sort of problem?
EDIT:
I realize that you can solve smaller numbers using cases, but what would be the approach if you had larger numbers (making it impractical to use cases)?
e.g.
$$x_1+x_2+x_3+x_4+2x_5=350$$
combinatorics
$endgroup$
|
show 1 more comment
$begingroup$
How would one proceed in their thought process when trying to solve what appears to be a standard stars and bars equation, with $x_igeqslant$ 0, e.g.
$$x_1+x_2+x_3+x_4=24$$
Except, let's say that there is a restriction that two of the variables must be equal. We can write the equation as such:
$$x_1+x_2+2x_3=24$$
At first, I tried substituting $2x_3$ with $y$, and solving for
$$x_1+x_2+y=24$$
using the standard stars and bars method. However, that would result in over counting, because it does not account for restrictions on $y$, since $y$ has to be even.
Any suggestions on how to solve this sort of problem?
EDIT:
I realize that you can solve smaller numbers using cases, but what would be the approach if you had larger numbers (making it impractical to use cases)?
e.g.
$$x_1+x_2+x_3+x_4+2x_5=350$$
combinatorics
$endgroup$
$begingroup$
$24$ is very small...Just do it case by case for $yin {0,2,4,cdots, 24}$. You'll get the answer as a sum of binomial coefficients.
$endgroup$
– lulu
Nov 27 '18 at 15:30
$begingroup$
Note: actually, since there are only two variables other than $y$, you don't even need stars and bars for each case (specified $y$). If, say, $y=6$, then we are just trying to solve $x_1+x_2=18$ which has $19$ solutions in non-negative integers.
$endgroup$
– lulu
Nov 27 '18 at 15:49
$begingroup$
What happens with significantly larger numbers? I understand that you can solve by cases for small numbers, but I'm interested in how to solve the general case for this type of question. I'll edit the original question to reflect that. Thanks for your input!
$endgroup$
– James Smithson
Nov 27 '18 at 15:58
$begingroup$
Well, with four variables (as here) it is still trivial, for the reason I mentioned. In full generality? Not sure I expect a simple closed formula. I'd first work a lot of the simpler cases to see if anything suggestive appeared.
$endgroup$
– lulu
Nov 27 '18 at 15:59
$begingroup$
The second problem that you mentioned in your last edit is not equivalent to the original one. In other words: $x_1+x_2+x_3+x_4=24$ with the restriction that two variables are equal and $x_1+x_2+2x_3=24$ are not equivalent (have not the same number of combinations). The second problem was discussed multiple times on MSE: math.stackexchange.com/questions/2036049/…
$endgroup$
– Oldboy
Nov 28 '18 at 9:03
|
show 1 more comment
$begingroup$
How would one proceed in their thought process when trying to solve what appears to be a standard stars and bars equation, with $x_igeqslant$ 0, e.g.
$$x_1+x_2+x_3+x_4=24$$
Except, let's say that there is a restriction that two of the variables must be equal. We can write the equation as such:
$$x_1+x_2+2x_3=24$$
At first, I tried substituting $2x_3$ with $y$, and solving for
$$x_1+x_2+y=24$$
using the standard stars and bars method. However, that would result in over counting, because it does not account for restrictions on $y$, since $y$ has to be even.
Any suggestions on how to solve this sort of problem?
EDIT:
I realize that you can solve smaller numbers using cases, but what would be the approach if you had larger numbers (making it impractical to use cases)?
e.g.
$$x_1+x_2+x_3+x_4+2x_5=350$$
combinatorics
$endgroup$
How would one proceed in their thought process when trying to solve what appears to be a standard stars and bars equation, with $x_igeqslant$ 0, e.g.
$$x_1+x_2+x_3+x_4=24$$
Except, let's say that there is a restriction that two of the variables must be equal. We can write the equation as such:
$$x_1+x_2+2x_3=24$$
At first, I tried substituting $2x_3$ with $y$, and solving for
$$x_1+x_2+y=24$$
using the standard stars and bars method. However, that would result in over counting, because it does not account for restrictions on $y$, since $y$ has to be even.
Any suggestions on how to solve this sort of problem?
EDIT:
I realize that you can solve smaller numbers using cases, but what would be the approach if you had larger numbers (making it impractical to use cases)?
e.g.
$$x_1+x_2+x_3+x_4+2x_5=350$$
combinatorics
combinatorics
edited Nov 27 '18 at 15:59
James Smithson
asked Nov 27 '18 at 15:21
James SmithsonJames Smithson
163
163
$begingroup$
$24$ is very small...Just do it case by case for $yin {0,2,4,cdots, 24}$. You'll get the answer as a sum of binomial coefficients.
$endgroup$
– lulu
Nov 27 '18 at 15:30
$begingroup$
Note: actually, since there are only two variables other than $y$, you don't even need stars and bars for each case (specified $y$). If, say, $y=6$, then we are just trying to solve $x_1+x_2=18$ which has $19$ solutions in non-negative integers.
$endgroup$
– lulu
Nov 27 '18 at 15:49
$begingroup$
What happens with significantly larger numbers? I understand that you can solve by cases for small numbers, but I'm interested in how to solve the general case for this type of question. I'll edit the original question to reflect that. Thanks for your input!
$endgroup$
– James Smithson
Nov 27 '18 at 15:58
$begingroup$
Well, with four variables (as here) it is still trivial, for the reason I mentioned. In full generality? Not sure I expect a simple closed formula. I'd first work a lot of the simpler cases to see if anything suggestive appeared.
$endgroup$
– lulu
Nov 27 '18 at 15:59
$begingroup$
The second problem that you mentioned in your last edit is not equivalent to the original one. In other words: $x_1+x_2+x_3+x_4=24$ with the restriction that two variables are equal and $x_1+x_2+2x_3=24$ are not equivalent (have not the same number of combinations). The second problem was discussed multiple times on MSE: math.stackexchange.com/questions/2036049/…
$endgroup$
– Oldboy
Nov 28 '18 at 9:03
|
show 1 more comment
$begingroup$
$24$ is very small...Just do it case by case for $yin {0,2,4,cdots, 24}$. You'll get the answer as a sum of binomial coefficients.
$endgroup$
– lulu
Nov 27 '18 at 15:30
$begingroup$
Note: actually, since there are only two variables other than $y$, you don't even need stars and bars for each case (specified $y$). If, say, $y=6$, then we are just trying to solve $x_1+x_2=18$ which has $19$ solutions in non-negative integers.
$endgroup$
– lulu
Nov 27 '18 at 15:49
$begingroup$
What happens with significantly larger numbers? I understand that you can solve by cases for small numbers, but I'm interested in how to solve the general case for this type of question. I'll edit the original question to reflect that. Thanks for your input!
$endgroup$
– James Smithson
Nov 27 '18 at 15:58
$begingroup$
Well, with four variables (as here) it is still trivial, for the reason I mentioned. In full generality? Not sure I expect a simple closed formula. I'd first work a lot of the simpler cases to see if anything suggestive appeared.
$endgroup$
– lulu
Nov 27 '18 at 15:59
$begingroup$
The second problem that you mentioned in your last edit is not equivalent to the original one. In other words: $x_1+x_2+x_3+x_4=24$ with the restriction that two variables are equal and $x_1+x_2+2x_3=24$ are not equivalent (have not the same number of combinations). The second problem was discussed multiple times on MSE: math.stackexchange.com/questions/2036049/…
$endgroup$
– Oldboy
Nov 28 '18 at 9:03
$begingroup$
$24$ is very small...Just do it case by case for $yin {0,2,4,cdots, 24}$. You'll get the answer as a sum of binomial coefficients.
$endgroup$
– lulu
Nov 27 '18 at 15:30
$begingroup$
$24$ is very small...Just do it case by case for $yin {0,2,4,cdots, 24}$. You'll get the answer as a sum of binomial coefficients.
$endgroup$
– lulu
Nov 27 '18 at 15:30
$begingroup$
Note: actually, since there are only two variables other than $y$, you don't even need stars and bars for each case (specified $y$). If, say, $y=6$, then we are just trying to solve $x_1+x_2=18$ which has $19$ solutions in non-negative integers.
$endgroup$
– lulu
Nov 27 '18 at 15:49
$begingroup$
Note: actually, since there are only two variables other than $y$, you don't even need stars and bars for each case (specified $y$). If, say, $y=6$, then we are just trying to solve $x_1+x_2=18$ which has $19$ solutions in non-negative integers.
$endgroup$
– lulu
Nov 27 '18 at 15:49
$begingroup$
What happens with significantly larger numbers? I understand that you can solve by cases for small numbers, but I'm interested in how to solve the general case for this type of question. I'll edit the original question to reflect that. Thanks for your input!
$endgroup$
– James Smithson
Nov 27 '18 at 15:58
$begingroup$
What happens with significantly larger numbers? I understand that you can solve by cases for small numbers, but I'm interested in how to solve the general case for this type of question. I'll edit the original question to reflect that. Thanks for your input!
$endgroup$
– James Smithson
Nov 27 '18 at 15:58
$begingroup$
Well, with four variables (as here) it is still trivial, for the reason I mentioned. In full generality? Not sure I expect a simple closed formula. I'd first work a lot of the simpler cases to see if anything suggestive appeared.
$endgroup$
– lulu
Nov 27 '18 at 15:59
$begingroup$
Well, with four variables (as here) it is still trivial, for the reason I mentioned. In full generality? Not sure I expect a simple closed formula. I'd first work a lot of the simpler cases to see if anything suggestive appeared.
$endgroup$
– lulu
Nov 27 '18 at 15:59
$begingroup$
The second problem that you mentioned in your last edit is not equivalent to the original one. In other words: $x_1+x_2+x_3+x_4=24$ with the restriction that two variables are equal and $x_1+x_2+2x_3=24$ are not equivalent (have not the same number of combinations). The second problem was discussed multiple times on MSE: math.stackexchange.com/questions/2036049/…
$endgroup$
– Oldboy
Nov 28 '18 at 9:03
$begingroup$
The second problem that you mentioned in your last edit is not equivalent to the original one. In other words: $x_1+x_2+x_3+x_4=24$ with the restriction that two variables are equal and $x_1+x_2+2x_3=24$ are not equivalent (have not the same number of combinations). The second problem was discussed multiple times on MSE: math.stackexchange.com/questions/2036049/…
$endgroup$
– Oldboy
Nov 28 '18 at 9:03
|
show 1 more comment
1 Answer
1
active
oldest
votes
$begingroup$
If the two identical variables are equal to $x$, the rest of the sum is $n=24-2x$. You can pick positions of the two identical variables in ${4 choose 2 }$ different ways.
Now, you have to split $n$ between the two remaining variables and there are ($n+1=25-2x$) ways to do it in general but you have to be careful. Not all splits are valid.
Take for example $x=0$. You cannot choose (12, 12), (0,24) and (24,0) for the last two variable values because you will end up with two many identical variables. The same is true for $x=1,2,3,4,5,7,8$. In these cases you will have $n+1-3=22-2x$ available pairs for the last two variables.
Take now $x=6$ for example. There is only one pair of values that has to be avoided as values of the last two variables: (6,6). The same is true for $x=9,10,11$ (you can easily check that). In these cases you have exactly $n=24-2x$ choices to split $n$ between the last two variables.
You can drop $x=12$ because it leads to 12+12+0+0 which is illegal.
Possible values for $x$ are therefore 0, 1,2, ...,11. For each value of $x$ you can put two identical variables in ${4 choose 2 }$ different places. So that factor multiplies everything. For every single value of $x$ you have either $(22-2x)$ or $(24-2x)$ways to set the remaining two variables. So the final result is:
$$binom{4}{2}timesleft(sum_{xin{0,1,2,3,4,5,7,8}}(22-2x)+sum_{xin{6,9,10,11}}(24-2x)right)=$$
$$6timesleft(4times2+sum_{x=0}^{11}(22-2x)right)=$$
$$6timesleft(8+12times22-2sum_{x=0}^{11}xright)=6times(8+12times22-2times66)=840$$
$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%2f3015899%2fstars-and-bars-question-with-restriction-that-two-variables-must-be-equal%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
If the two identical variables are equal to $x$, the rest of the sum is $n=24-2x$. You can pick positions of the two identical variables in ${4 choose 2 }$ different ways.
Now, you have to split $n$ between the two remaining variables and there are ($n+1=25-2x$) ways to do it in general but you have to be careful. Not all splits are valid.
Take for example $x=0$. You cannot choose (12, 12), (0,24) and (24,0) for the last two variable values because you will end up with two many identical variables. The same is true for $x=1,2,3,4,5,7,8$. In these cases you will have $n+1-3=22-2x$ available pairs for the last two variables.
Take now $x=6$ for example. There is only one pair of values that has to be avoided as values of the last two variables: (6,6). The same is true for $x=9,10,11$ (you can easily check that). In these cases you have exactly $n=24-2x$ choices to split $n$ between the last two variables.
You can drop $x=12$ because it leads to 12+12+0+0 which is illegal.
Possible values for $x$ are therefore 0, 1,2, ...,11. For each value of $x$ you can put two identical variables in ${4 choose 2 }$ different places. So that factor multiplies everything. For every single value of $x$ you have either $(22-2x)$ or $(24-2x)$ways to set the remaining two variables. So the final result is:
$$binom{4}{2}timesleft(sum_{xin{0,1,2,3,4,5,7,8}}(22-2x)+sum_{xin{6,9,10,11}}(24-2x)right)=$$
$$6timesleft(4times2+sum_{x=0}^{11}(22-2x)right)=$$
$$6timesleft(8+12times22-2sum_{x=0}^{11}xright)=6times(8+12times22-2times66)=840$$
$endgroup$
add a comment |
$begingroup$
If the two identical variables are equal to $x$, the rest of the sum is $n=24-2x$. You can pick positions of the two identical variables in ${4 choose 2 }$ different ways.
Now, you have to split $n$ between the two remaining variables and there are ($n+1=25-2x$) ways to do it in general but you have to be careful. Not all splits are valid.
Take for example $x=0$. You cannot choose (12, 12), (0,24) and (24,0) for the last two variable values because you will end up with two many identical variables. The same is true for $x=1,2,3,4,5,7,8$. In these cases you will have $n+1-3=22-2x$ available pairs for the last two variables.
Take now $x=6$ for example. There is only one pair of values that has to be avoided as values of the last two variables: (6,6). The same is true for $x=9,10,11$ (you can easily check that). In these cases you have exactly $n=24-2x$ choices to split $n$ between the last two variables.
You can drop $x=12$ because it leads to 12+12+0+0 which is illegal.
Possible values for $x$ are therefore 0, 1,2, ...,11. For each value of $x$ you can put two identical variables in ${4 choose 2 }$ different places. So that factor multiplies everything. For every single value of $x$ you have either $(22-2x)$ or $(24-2x)$ways to set the remaining two variables. So the final result is:
$$binom{4}{2}timesleft(sum_{xin{0,1,2,3,4,5,7,8}}(22-2x)+sum_{xin{6,9,10,11}}(24-2x)right)=$$
$$6timesleft(4times2+sum_{x=0}^{11}(22-2x)right)=$$
$$6timesleft(8+12times22-2sum_{x=0}^{11}xright)=6times(8+12times22-2times66)=840$$
$endgroup$
add a comment |
$begingroup$
If the two identical variables are equal to $x$, the rest of the sum is $n=24-2x$. You can pick positions of the two identical variables in ${4 choose 2 }$ different ways.
Now, you have to split $n$ between the two remaining variables and there are ($n+1=25-2x$) ways to do it in general but you have to be careful. Not all splits are valid.
Take for example $x=0$. You cannot choose (12, 12), (0,24) and (24,0) for the last two variable values because you will end up with two many identical variables. The same is true for $x=1,2,3,4,5,7,8$. In these cases you will have $n+1-3=22-2x$ available pairs for the last two variables.
Take now $x=6$ for example. There is only one pair of values that has to be avoided as values of the last two variables: (6,6). The same is true for $x=9,10,11$ (you can easily check that). In these cases you have exactly $n=24-2x$ choices to split $n$ between the last two variables.
You can drop $x=12$ because it leads to 12+12+0+0 which is illegal.
Possible values for $x$ are therefore 0, 1,2, ...,11. For each value of $x$ you can put two identical variables in ${4 choose 2 }$ different places. So that factor multiplies everything. For every single value of $x$ you have either $(22-2x)$ or $(24-2x)$ways to set the remaining two variables. So the final result is:
$$binom{4}{2}timesleft(sum_{xin{0,1,2,3,4,5,7,8}}(22-2x)+sum_{xin{6,9,10,11}}(24-2x)right)=$$
$$6timesleft(4times2+sum_{x=0}^{11}(22-2x)right)=$$
$$6timesleft(8+12times22-2sum_{x=0}^{11}xright)=6times(8+12times22-2times66)=840$$
$endgroup$
If the two identical variables are equal to $x$, the rest of the sum is $n=24-2x$. You can pick positions of the two identical variables in ${4 choose 2 }$ different ways.
Now, you have to split $n$ between the two remaining variables and there are ($n+1=25-2x$) ways to do it in general but you have to be careful. Not all splits are valid.
Take for example $x=0$. You cannot choose (12, 12), (0,24) and (24,0) for the last two variable values because you will end up with two many identical variables. The same is true for $x=1,2,3,4,5,7,8$. In these cases you will have $n+1-3=22-2x$ available pairs for the last two variables.
Take now $x=6$ for example. There is only one pair of values that has to be avoided as values of the last two variables: (6,6). The same is true for $x=9,10,11$ (you can easily check that). In these cases you have exactly $n=24-2x$ choices to split $n$ between the last two variables.
You can drop $x=12$ because it leads to 12+12+0+0 which is illegal.
Possible values for $x$ are therefore 0, 1,2, ...,11. For each value of $x$ you can put two identical variables in ${4 choose 2 }$ different places. So that factor multiplies everything. For every single value of $x$ you have either $(22-2x)$ or $(24-2x)$ways to set the remaining two variables. So the final result is:
$$binom{4}{2}timesleft(sum_{xin{0,1,2,3,4,5,7,8}}(22-2x)+sum_{xin{6,9,10,11}}(24-2x)right)=$$
$$6timesleft(4times2+sum_{x=0}^{11}(22-2x)right)=$$
$$6timesleft(8+12times22-2sum_{x=0}^{11}xright)=6times(8+12times22-2times66)=840$$
edited Nov 27 '18 at 17:24
answered Nov 27 '18 at 16:39
OldboyOldboy
7,6851935
7,6851935
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%2f3015899%2fstars-and-bars-question-with-restriction-that-two-variables-must-be-equal%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
$begingroup$
$24$ is very small...Just do it case by case for $yin {0,2,4,cdots, 24}$. You'll get the answer as a sum of binomial coefficients.
$endgroup$
– lulu
Nov 27 '18 at 15:30
$begingroup$
Note: actually, since there are only two variables other than $y$, you don't even need stars and bars for each case (specified $y$). If, say, $y=6$, then we are just trying to solve $x_1+x_2=18$ which has $19$ solutions in non-negative integers.
$endgroup$
– lulu
Nov 27 '18 at 15:49
$begingroup$
What happens with significantly larger numbers? I understand that you can solve by cases for small numbers, but I'm interested in how to solve the general case for this type of question. I'll edit the original question to reflect that. Thanks for your input!
$endgroup$
– James Smithson
Nov 27 '18 at 15:58
$begingroup$
Well, with four variables (as here) it is still trivial, for the reason I mentioned. In full generality? Not sure I expect a simple closed formula. I'd first work a lot of the simpler cases to see if anything suggestive appeared.
$endgroup$
– lulu
Nov 27 '18 at 15:59
$begingroup$
The second problem that you mentioned in your last edit is not equivalent to the original one. In other words: $x_1+x_2+x_3+x_4=24$ with the restriction that two variables are equal and $x_1+x_2+2x_3=24$ are not equivalent (have not the same number of combinations). The second problem was discussed multiple times on MSE: math.stackexchange.com/questions/2036049/…
$endgroup$
– Oldboy
Nov 28 '18 at 9:03