Square coloring problem only using 2 colors
up vote
2
down vote
favorite
"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
add a comment |
up vote
2
down vote
favorite
"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
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
add a comment |
up vote
2
down vote
favorite
up vote
2
down vote
favorite
"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
"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
combinatorics coloring polya-counting-theory
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
add a comment |
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
add a comment |
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.
New contributor
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
add a comment |
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.
add a comment |
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.
New contributor
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
add a comment |
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.
New contributor
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
add a comment |
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.
New contributor
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.
New contributor
edited 5 hours ago
New contributor
answered 7 hours ago
Todor Markov
562
562
New contributor
New contributor
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
add a comment |
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
add a comment |
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.
add a comment |
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.
add a comment |
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.
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.
edited 5 hours ago
answered 5 hours ago
Marko Riedel
38.1k338106
38.1k338106
add a comment |
add a comment |
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
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
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
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
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
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