Square coloring problem only using 2 colors











up vote
2
down vote

favorite
2













"We need to color $4×4$ square using $4$ black color and $12$ white color. Then, how many cases it may be? Flip is prohibited but rotating is ok"




I tried case by case (inner square and rest) anf obtained answer 389. But I don't know if it's correct. Help me please.










share|cite|improve this question




















  • 1




    How do you get an odd number? The only time $C_4$ will give an odd orbit is if it is a fixed point, but there are only 4 of them.
    – user10354138
    11 hours ago















up vote
2
down vote

favorite
2













"We need to color $4×4$ square using $4$ black color and $12$ white color. Then, how many cases it may be? Flip is prohibited but rotating is ok"




I tried case by case (inner square and rest) anf obtained answer 389. But I don't know if it's correct. Help me please.










share|cite|improve this question




















  • 1




    How do you get an odd number? The only time $C_4$ will give an odd orbit is if it is a fixed point, but there are only 4 of them.
    – user10354138
    11 hours ago













up vote
2
down vote

favorite
2









up vote
2
down vote

favorite
2






2






"We need to color $4×4$ square using $4$ black color and $12$ white color. Then, how many cases it may be? Flip is prohibited but rotating is ok"




I tried case by case (inner square and rest) anf obtained answer 389. But I don't know if it's correct. Help me please.










share|cite|improve this question
















"We need to color $4×4$ square using $4$ black color and $12$ white color. Then, how many cases it may be? Flip is prohibited but rotating is ok"




I tried case by case (inner square and rest) anf obtained answer 389. But I don't know if it's correct. Help me please.







combinatorics coloring polya-counting-theory






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited 11 hours ago









greedoid

33.8k114488




33.8k114488










asked 12 hours ago









scitamehtam

283




283








  • 1




    How do you get an odd number? The only time $C_4$ will give an odd orbit is if it is a fixed point, but there are only 4 of them.
    – user10354138
    11 hours ago














  • 1




    How do you get an odd number? The only time $C_4$ will give an odd orbit is if it is a fixed point, but there are only 4 of them.
    – user10354138
    11 hours ago








1




1




How do you get an odd number? The only time $C_4$ will give an odd orbit is if it is a fixed point, but there are only 4 of them.
– user10354138
11 hours ago




How do you get an odd number? The only time $C_4$ will give an odd orbit is if it is a fixed point, but there are only 4 of them.
– user10354138
11 hours ago










2 Answers
2






active

oldest

votes

















up vote
4
down vote



accepted










Assuming rotation is also prohibited, we have ${16 choose 4} = 1820$ ways to select the black tiles. However, we are allowed to rotate the board, so we need to account for overcounting.



We have counted most colorings four times, as, in general, each rotation will be counted separately. However, symmetry can change that.



There are ${4 choose 1} = 4$ colorings which are counted only once. These are the coloring that don't change after rotation. If we split the $4 times 4$ table into four $2 times 2$ tables, they will have one black tile in each of these $2 times 2$s placed symmetrically.



There are also colorings that are counted twice: these are the ones which change from a 90-degree rotation, but are preserved after 180-degree rotation. Let's look at the top two rows of the $4 times 4$ square. We can color any two tiles there, but then we'll need to color the two symmetrical ones (across the center, not across the horizontal line) to preserve the coloring after 180-degree rotation. There are ${8 choose 2} = 28$ ways to do that. From these, we need to subtract the four which have 4-way symmetry, and 24 are left. Now, these are double counted, so there are 12 distinct colorings (for example, the coloring where the two first column middle cells, and two last column middle cells are black, are the same as the coloring where the two first row middle cells and the two last row middle cells are black).



The remaining are counted four times, therefore there are $frac{1820 - 4 - 2 times 12}{4} = 448$ colorings remaining.



This gives us a total of 448 + 12 + 4 = 464 colorings.






share|cite|improve this answer










New contributor




Todor Markov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.














  • 3




    Please check carefully. The correct answer is $455+6+3=464$.
    – Andrew Woods
    6 hours ago






  • 1




    Let $a$ be the number of colourings without rotational symmetry, $b$ be the number of those with order 2 rotational symmetry only, and $c$ be the number of those with order 4. Then $tfrac14cdot 1820=455=tfrac14(a+b+c)$. But you need to find $tfrac14a+tfrac12b+c$.
    – Andrew Woods
    5 hours ago












  • Thanks, I forgot to divide by two the double counted.
    – Todor Markov
    5 hours ago


















up vote
4
down vote













We apply PET (Polya Enumeration Theorem) here and this needs the cycle
index. There are four rotations. The first is the identity which
contributes



$$a_1^{16}.$$



There are the rotations by $90$ degrees and by $270$ degrees, which
contribute



$$2 a_4^4.$$



The rotation by $180$ degrees contributes



$$a_2^8.$$



This yields the cycle index



$$Z(G) = frac{1}{4} (a_1^{16} + 2 a_4^4 + a_2^8).$$



We thus have for the desired quantity



$$[B^4 W^{12}] Z(G; B + W)
\ = [B^4 W^{12}]
frac{1}{4} ((B+W)^{16} + 2 (B^4+W^4)^4 + (B^2+W^2)^8)
\ = frac{1}{4} {16choose 4} +
frac{1}{2} [B W^3] (B+W)^4 + frac{1}{4} [B^2 W^6] (B+W)^8
\ = frac{1}{4} {16choose 4} + frac{1}{2} {4choose 1}
+ frac{1}{4} {8choose 2}.$$



This yields



$$bbox[5px,border:2px solid #00A000]{464}$$



confirming the data from the comment.






share|cite|improve this answer























    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',
    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%2f2996474%2fsquare-coloring-problem-only-using-2-colors%23new-answer', 'question_page');
    }
    );

    Post as a guest
































    2 Answers
    2






    active

    oldest

    votes








    2 Answers
    2






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes








    up vote
    4
    down vote



    accepted










    Assuming rotation is also prohibited, we have ${16 choose 4} = 1820$ ways to select the black tiles. However, we are allowed to rotate the board, so we need to account for overcounting.



    We have counted most colorings four times, as, in general, each rotation will be counted separately. However, symmetry can change that.



    There are ${4 choose 1} = 4$ colorings which are counted only once. These are the coloring that don't change after rotation. If we split the $4 times 4$ table into four $2 times 2$ tables, they will have one black tile in each of these $2 times 2$s placed symmetrically.



    There are also colorings that are counted twice: these are the ones which change from a 90-degree rotation, but are preserved after 180-degree rotation. Let's look at the top two rows of the $4 times 4$ square. We can color any two tiles there, but then we'll need to color the two symmetrical ones (across the center, not across the horizontal line) to preserve the coloring after 180-degree rotation. There are ${8 choose 2} = 28$ ways to do that. From these, we need to subtract the four which have 4-way symmetry, and 24 are left. Now, these are double counted, so there are 12 distinct colorings (for example, the coloring where the two first column middle cells, and two last column middle cells are black, are the same as the coloring where the two first row middle cells and the two last row middle cells are black).



    The remaining are counted four times, therefore there are $frac{1820 - 4 - 2 times 12}{4} = 448$ colorings remaining.



    This gives us a total of 448 + 12 + 4 = 464 colorings.






    share|cite|improve this answer










    New contributor




    Todor Markov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.














    • 3




      Please check carefully. The correct answer is $455+6+3=464$.
      – Andrew Woods
      6 hours ago






    • 1




      Let $a$ be the number of colourings without rotational symmetry, $b$ be the number of those with order 2 rotational symmetry only, and $c$ be the number of those with order 4. Then $tfrac14cdot 1820=455=tfrac14(a+b+c)$. But you need to find $tfrac14a+tfrac12b+c$.
      – Andrew Woods
      5 hours ago












    • Thanks, I forgot to divide by two the double counted.
      – Todor Markov
      5 hours ago















    up vote
    4
    down vote



    accepted










    Assuming rotation is also prohibited, we have ${16 choose 4} = 1820$ ways to select the black tiles. However, we are allowed to rotate the board, so we need to account for overcounting.



    We have counted most colorings four times, as, in general, each rotation will be counted separately. However, symmetry can change that.



    There are ${4 choose 1} = 4$ colorings which are counted only once. These are the coloring that don't change after rotation. If we split the $4 times 4$ table into four $2 times 2$ tables, they will have one black tile in each of these $2 times 2$s placed symmetrically.



    There are also colorings that are counted twice: these are the ones which change from a 90-degree rotation, but are preserved after 180-degree rotation. Let's look at the top two rows of the $4 times 4$ square. We can color any two tiles there, but then we'll need to color the two symmetrical ones (across the center, not across the horizontal line) to preserve the coloring after 180-degree rotation. There are ${8 choose 2} = 28$ ways to do that. From these, we need to subtract the four which have 4-way symmetry, and 24 are left. Now, these are double counted, so there are 12 distinct colorings (for example, the coloring where the two first column middle cells, and two last column middle cells are black, are the same as the coloring where the two first row middle cells and the two last row middle cells are black).



    The remaining are counted four times, therefore there are $frac{1820 - 4 - 2 times 12}{4} = 448$ colorings remaining.



    This gives us a total of 448 + 12 + 4 = 464 colorings.






    share|cite|improve this answer










    New contributor




    Todor Markov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.














    • 3




      Please check carefully. The correct answer is $455+6+3=464$.
      – Andrew Woods
      6 hours ago






    • 1




      Let $a$ be the number of colourings without rotational symmetry, $b$ be the number of those with order 2 rotational symmetry only, and $c$ be the number of those with order 4. Then $tfrac14cdot 1820=455=tfrac14(a+b+c)$. But you need to find $tfrac14a+tfrac12b+c$.
      – Andrew Woods
      5 hours ago












    • Thanks, I forgot to divide by two the double counted.
      – Todor Markov
      5 hours ago













    up vote
    4
    down vote



    accepted







    up vote
    4
    down vote



    accepted






    Assuming rotation is also prohibited, we have ${16 choose 4} = 1820$ ways to select the black tiles. However, we are allowed to rotate the board, so we need to account for overcounting.



    We have counted most colorings four times, as, in general, each rotation will be counted separately. However, symmetry can change that.



    There are ${4 choose 1} = 4$ colorings which are counted only once. These are the coloring that don't change after rotation. If we split the $4 times 4$ table into four $2 times 2$ tables, they will have one black tile in each of these $2 times 2$s placed symmetrically.



    There are also colorings that are counted twice: these are the ones which change from a 90-degree rotation, but are preserved after 180-degree rotation. Let's look at the top two rows of the $4 times 4$ square. We can color any two tiles there, but then we'll need to color the two symmetrical ones (across the center, not across the horizontal line) to preserve the coloring after 180-degree rotation. There are ${8 choose 2} = 28$ ways to do that. From these, we need to subtract the four which have 4-way symmetry, and 24 are left. Now, these are double counted, so there are 12 distinct colorings (for example, the coloring where the two first column middle cells, and two last column middle cells are black, are the same as the coloring where the two first row middle cells and the two last row middle cells are black).



    The remaining are counted four times, therefore there are $frac{1820 - 4 - 2 times 12}{4} = 448$ colorings remaining.



    This gives us a total of 448 + 12 + 4 = 464 colorings.






    share|cite|improve this answer










    New contributor




    Todor Markov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.









    Assuming rotation is also prohibited, we have ${16 choose 4} = 1820$ ways to select the black tiles. However, we are allowed to rotate the board, so we need to account for overcounting.



    We have counted most colorings four times, as, in general, each rotation will be counted separately. However, symmetry can change that.



    There are ${4 choose 1} = 4$ colorings which are counted only once. These are the coloring that don't change after rotation. If we split the $4 times 4$ table into four $2 times 2$ tables, they will have one black tile in each of these $2 times 2$s placed symmetrically.



    There are also colorings that are counted twice: these are the ones which change from a 90-degree rotation, but are preserved after 180-degree rotation. Let's look at the top two rows of the $4 times 4$ square. We can color any two tiles there, but then we'll need to color the two symmetrical ones (across the center, not across the horizontal line) to preserve the coloring after 180-degree rotation. There are ${8 choose 2} = 28$ ways to do that. From these, we need to subtract the four which have 4-way symmetry, and 24 are left. Now, these are double counted, so there are 12 distinct colorings (for example, the coloring where the two first column middle cells, and two last column middle cells are black, are the same as the coloring where the two first row middle cells and the two last row middle cells are black).



    The remaining are counted four times, therefore there are $frac{1820 - 4 - 2 times 12}{4} = 448$ colorings remaining.



    This gives us a total of 448 + 12 + 4 = 464 colorings.







    share|cite|improve this answer










    New contributor




    Todor Markov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.









    share|cite|improve this answer



    share|cite|improve this answer








    edited 5 hours ago





















    New contributor




    Todor Markov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.









    answered 7 hours ago









    Todor Markov

    562




    562




    New contributor




    Todor Markov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.





    New contributor





    Todor Markov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.






    Todor Markov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.








    • 3




      Please check carefully. The correct answer is $455+6+3=464$.
      – Andrew Woods
      6 hours ago






    • 1




      Let $a$ be the number of colourings without rotational symmetry, $b$ be the number of those with order 2 rotational symmetry only, and $c$ be the number of those with order 4. Then $tfrac14cdot 1820=455=tfrac14(a+b+c)$. But you need to find $tfrac14a+tfrac12b+c$.
      – Andrew Woods
      5 hours ago












    • Thanks, I forgot to divide by two the double counted.
      – Todor Markov
      5 hours ago














    • 3




      Please check carefully. The correct answer is $455+6+3=464$.
      – Andrew Woods
      6 hours ago






    • 1




      Let $a$ be the number of colourings without rotational symmetry, $b$ be the number of those with order 2 rotational symmetry only, and $c$ be the number of those with order 4. Then $tfrac14cdot 1820=455=tfrac14(a+b+c)$. But you need to find $tfrac14a+tfrac12b+c$.
      – Andrew Woods
      5 hours ago












    • Thanks, I forgot to divide by two the double counted.
      – Todor Markov
      5 hours ago








    3




    3




    Please check carefully. The correct answer is $455+6+3=464$.
    – Andrew Woods
    6 hours ago




    Please check carefully. The correct answer is $455+6+3=464$.
    – Andrew Woods
    6 hours ago




    1




    1




    Let $a$ be the number of colourings without rotational symmetry, $b$ be the number of those with order 2 rotational symmetry only, and $c$ be the number of those with order 4. Then $tfrac14cdot 1820=455=tfrac14(a+b+c)$. But you need to find $tfrac14a+tfrac12b+c$.
    – Andrew Woods
    5 hours ago






    Let $a$ be the number of colourings without rotational symmetry, $b$ be the number of those with order 2 rotational symmetry only, and $c$ be the number of those with order 4. Then $tfrac14cdot 1820=455=tfrac14(a+b+c)$. But you need to find $tfrac14a+tfrac12b+c$.
    – Andrew Woods
    5 hours ago














    Thanks, I forgot to divide by two the double counted.
    – Todor Markov
    5 hours ago




    Thanks, I forgot to divide by two the double counted.
    – Todor Markov
    5 hours ago










    up vote
    4
    down vote













    We apply PET (Polya Enumeration Theorem) here and this needs the cycle
    index. There are four rotations. The first is the identity which
    contributes



    $$a_1^{16}.$$



    There are the rotations by $90$ degrees and by $270$ degrees, which
    contribute



    $$2 a_4^4.$$



    The rotation by $180$ degrees contributes



    $$a_2^8.$$



    This yields the cycle index



    $$Z(G) = frac{1}{4} (a_1^{16} + 2 a_4^4 + a_2^8).$$



    We thus have for the desired quantity



    $$[B^4 W^{12}] Z(G; B + W)
    \ = [B^4 W^{12}]
    frac{1}{4} ((B+W)^{16} + 2 (B^4+W^4)^4 + (B^2+W^2)^8)
    \ = frac{1}{4} {16choose 4} +
    frac{1}{2} [B W^3] (B+W)^4 + frac{1}{4} [B^2 W^6] (B+W)^8
    \ = frac{1}{4} {16choose 4} + frac{1}{2} {4choose 1}
    + frac{1}{4} {8choose 2}.$$



    This yields



    $$bbox[5px,border:2px solid #00A000]{464}$$



    confirming the data from the comment.






    share|cite|improve this answer



























      up vote
      4
      down vote













      We apply PET (Polya Enumeration Theorem) here and this needs the cycle
      index. There are four rotations. The first is the identity which
      contributes



      $$a_1^{16}.$$



      There are the rotations by $90$ degrees and by $270$ degrees, which
      contribute



      $$2 a_4^4.$$



      The rotation by $180$ degrees contributes



      $$a_2^8.$$



      This yields the cycle index



      $$Z(G) = frac{1}{4} (a_1^{16} + 2 a_4^4 + a_2^8).$$



      We thus have for the desired quantity



      $$[B^4 W^{12}] Z(G; B + W)
      \ = [B^4 W^{12}]
      frac{1}{4} ((B+W)^{16} + 2 (B^4+W^4)^4 + (B^2+W^2)^8)
      \ = frac{1}{4} {16choose 4} +
      frac{1}{2} [B W^3] (B+W)^4 + frac{1}{4} [B^2 W^6] (B+W)^8
      \ = frac{1}{4} {16choose 4} + frac{1}{2} {4choose 1}
      + frac{1}{4} {8choose 2}.$$



      This yields



      $$bbox[5px,border:2px solid #00A000]{464}$$



      confirming the data from the comment.






      share|cite|improve this answer

























        up vote
        4
        down vote










        up vote
        4
        down vote









        We apply PET (Polya Enumeration Theorem) here and this needs the cycle
        index. There are four rotations. The first is the identity which
        contributes



        $$a_1^{16}.$$



        There are the rotations by $90$ degrees and by $270$ degrees, which
        contribute



        $$2 a_4^4.$$



        The rotation by $180$ degrees contributes



        $$a_2^8.$$



        This yields the cycle index



        $$Z(G) = frac{1}{4} (a_1^{16} + 2 a_4^4 + a_2^8).$$



        We thus have for the desired quantity



        $$[B^4 W^{12}] Z(G; B + W)
        \ = [B^4 W^{12}]
        frac{1}{4} ((B+W)^{16} + 2 (B^4+W^4)^4 + (B^2+W^2)^8)
        \ = frac{1}{4} {16choose 4} +
        frac{1}{2} [B W^3] (B+W)^4 + frac{1}{4} [B^2 W^6] (B+W)^8
        \ = frac{1}{4} {16choose 4} + frac{1}{2} {4choose 1}
        + frac{1}{4} {8choose 2}.$$



        This yields



        $$bbox[5px,border:2px solid #00A000]{464}$$



        confirming the data from the comment.






        share|cite|improve this answer














        We apply PET (Polya Enumeration Theorem) here and this needs the cycle
        index. There are four rotations. The first is the identity which
        contributes



        $$a_1^{16}.$$



        There are the rotations by $90$ degrees and by $270$ degrees, which
        contribute



        $$2 a_4^4.$$



        The rotation by $180$ degrees contributes



        $$a_2^8.$$



        This yields the cycle index



        $$Z(G) = frac{1}{4} (a_1^{16} + 2 a_4^4 + a_2^8).$$



        We thus have for the desired quantity



        $$[B^4 W^{12}] Z(G; B + W)
        \ = [B^4 W^{12}]
        frac{1}{4} ((B+W)^{16} + 2 (B^4+W^4)^4 + (B^2+W^2)^8)
        \ = frac{1}{4} {16choose 4} +
        frac{1}{2} [B W^3] (B+W)^4 + frac{1}{4} [B^2 W^6] (B+W)^8
        \ = frac{1}{4} {16choose 4} + frac{1}{2} {4choose 1}
        + frac{1}{4} {8choose 2}.$$



        This yields



        $$bbox[5px,border:2px solid #00A000]{464}$$



        confirming the data from the comment.







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited 5 hours ago

























        answered 5 hours ago









        Marko Riedel

        38.1k338106




        38.1k338106






























             

            draft saved


            draft discarded



















































             


            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2996474%2fsquare-coloring-problem-only-using-2-colors%23new-answer', 'question_page');
            }
            );

            Post as a guest




















































































            Popular posts from this blog

            How do I know what Microsoft account the skydrive app is syncing to?

            Grease: Live!

            When does type information flow backwards in C++?