Stars and Bars question with restriction that two variables must be equal












3












$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$$










share|cite|improve this question











$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


















3












$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$$










share|cite|improve this question











$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
















3












3








3


2



$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$$










share|cite|improve this question











$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






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








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




















  • $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












1 Answer
1






active

oldest

votes


















1












$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$$






share|cite|improve this answer











$endgroup$













    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
    });


    }
    });














    draft saved

    draft discarded


















    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









    1












    $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$$






    share|cite|improve this answer











    $endgroup$


















      1












      $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$$






      share|cite|improve this answer











      $endgroup$
















        1












        1








        1





        $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$$






        share|cite|improve this answer











        $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$$







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited Nov 27 '18 at 17:24

























        answered Nov 27 '18 at 16:39









        OldboyOldboy

        7,6851935




        7,6851935






























            draft saved

            draft discarded




















































            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.




            draft saved


            draft discarded














            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





















































            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







            Popular posts from this blog

            How to change which sound is reproduced for terminal bell?

            Can I use Tabulator js library in my java Spring + Thymeleaf project?

            Title Spacing in Bjornstrup Chapter, Removing Chapter Number From Contents